經典算法系（21）-二分查找樹性能分析（Binary Search Tree Performance Analysis）https://www.douban.com/note/221942390/

?預言家?2012-06-25 21:43:34 二叉搜索樹（Binary Search Tree，BST）是一顆典型的二叉樹，同時任何節點的鍵值大于等于該節點左子樹中的所有鍵值，小于等于該節點右子樹中的所有鍵值，并且每個節點域中保存一個記錄以其為根節點的子樹中所有節點個數的屬性，這個屬性可用于支持貪婪算法的實現。

? 二叉搜索樹的建立是在樹的底部添加新的元素，搜索即從根元素開始到達樹底部的一條路徑，插入和搜索相似（注意對重復鍵的處理），排序按照節點訪問方式不同有前序、中序、后序三種
? 二叉搜索樹算法的運行時間取決于樹的形狀，最好情況下根節點與每個外部節點間有㏒N個節點，此時樹完全平衡，最壞情況下搜索路徑上有N個節點。由于創建二叉搜索樹的時候，第一個插入的元素總是作為根元素，所以元素插入的順序決定樹的形狀。在隨機情況下，極度平衡和極度不平衡的樹都很少出現，所以這種情況下二叉搜索樹算法有著良好的運行情況。
? 所以平均情況下，N個隨機生成的BST樹種，一次搜索，插入大約需要1.39㏒N此比較。如果鍵值不是隨機出現，則二叉搜索樹退化為N個節點的鏈表，一次操作為線性O(N)運行時間
? 使用BST樹存儲文件中每一個文本串，基于字符串的排序使得搜索變得容易

基于BST的構造、搜索、插入，選擇，刪除（Binary Tree Search）

? 算法原理：

? BottomUp插入策略：按照前序策略遍歷整個樹結構，首先查看當前節點是否為NULL，然后與關鍵值比較查看是否為目標值，不是的話就分別針對左右子樹遞歸調用搜索算法，然后進入下一個結構，注意在遞歸調用之間的銜接是由返回一個節點來實現的，所以如果已經到達樹底部，則返回一個新節點，這個節點正好位于上一級的子樹連接上，這樣正好形成整個樹結構；

? TopDown插入策略：在BottomUp插入策略的基礎上，將新插入的節點在遞歸回溯的時候逐層旋轉，知道根節點的位置；使用基于遞歸插入操作和旋轉操作的策略可以使得最近插入的元素接近BST樹的頂部，同時保持樹的平衡性。這種插入方式稱為從根部插入，實現策略：首先使用普通遞歸插入將在樹底部找到一個合適的位置插入新的節點，然后使用旋轉操作將這個新加入的節點旋轉到根節點處，不僅可以保持樹的平衡，而且由于最近插入的項被使用的概率大，靠近根節點則加速搜索效率；

? 旋轉操作：BST樹中從根部插入新節點：首要考慮的就是是否能夠保持BST樹的性質。現在使用基于旋轉（Rotation）的轉換策略，使得BST樹保持原有性質。旋轉實質上是交換根節點和一個孩子的角色，同時保持各節點的順序
?

?

? 選擇第Kth個值（最小或者最大）：利用Node節點中的count標記（此標記說明以當前節點為根節點的子樹的所有節點數），可以快速查找給定的序列中第Kth個最小或者最大值；當然前提是將給定的序列擴建成BST；從根節點開始，首先檢查其左子樹中節點個數，如果正好為K個則返回根節點本身，如果大于K個節點，則對左子樹遞歸調用算法，如果小于K個節點，則說明第K個最小鍵在根節點的右子樹中，變成查找右子樹中第K-t-1個最小鍵的項（t為左子樹所有節點，1為根節點自身）

? BST樹的節點刪除操作：被刪除的節點可以有三種情況，沒有子節點，有一個子節點，有兩個子節點。第一種情況可直接刪除；第二種情況需要臨時存儲子節點的索引，并讓被刪除節點的父節點指向這個這個索引；第三種情況需要維護BST樹的性質，所以一般性策略是選擇右子樹中最小的元素作為新的根節點（右子樹中最小的元素出現在最左邊，所以它至多只有一個子節點，可容易刪除），然而有時候也會選擇左子樹中的最大元素作為新的根節點（由于在左右子樹中任意選擇新的節點作為新的根節點，所以可能造成BST樹的不平衡）

? 算法代碼：

struct Node {
????????int value;
????????int count;
????????Node *left;
????????Node *right;
????????Node(int v, int c=1, Node* l=NULL, Node* r=NULL):
????????????????????????????????count(c), value(v), left(l), right(r) {

????????}
};
/**
?* 對root節點進行右旋轉操作，也就是：
?* 1. 讓root原來的左孩子變成newRoot；
?* 2. 讓root變成newRoot的右子節點；
?* 3. 讓root原來的左孩子的的右子節點變成root的左子節點
?* */
Node* rightRotate(Node *root) {
????????Node *newRoot=root->left;
????????root->left=root->left->right;
????????newRoot->right=root;
????????return newRoot;
}
/**
?* 對root節點進行左旋轉操作，也就是：
?* 1. 讓root原來的右孩子變成newRoot；
?* 2. 讓root變成newRoot的左子節點；
?* 3. 讓root原來的右孩子的左子節點變成root的右子節點
?* */
Node* leftRotate(Node *root) {
????????Node *newRoot=root->right;
????????root->right=root->right->left;
????????newRoot->left=root;
????????return newRoot;
}

Node* binaryTreeSearch(Node *root, int target) {

????????if(root==NULL)
????????????????return NULL;

????????if(target>root->value)
????????????????return binaryTreeSearch(root->right, target);
????????else if(target<root->value)
????????????????return binaryTreeSearch(root->left, target);
????????else
????????????????return root;
}

Node* binaryTreeInsert(Node *root, int target) {

????????if(root==NULL) {
????????????????return new Node(target);
????????}

????????if(target>root->value)
????????????????root->right=binaryTreeInsert(root->right, target);
????????else if(target<root->value)
????????????????root->left=binaryTreeInsert(root->left, target);

????????return root;
}
/**
?* 這樣可以將新插入的元素旋轉到為root；
?* 不僅可以保持BST的平衡性，而且可以保證
?* 新插入的元素的最大訪問延遲；
?* */
Node* binaryTreeInsertTopDown(Node *root, int target) {

????????if(root==NULL) {
????????????????return new Node(target);
????????}

????????if(target>root->value) {
????????????????root->right=binaryTreeInsert(root->right, target);
????????????????root=leftRotate(root);
????????}
????????else if(target<root->value) {
????????????????root->left=binaryTreeInsert(root->left, target);
????????????????root=rightRotate(root);
????????}

????????return root;
}

Node* binaryTreeInsertWithCount(Node *root, int target) {

????????if(root==NULL) {
????????????????return new Node(target);
????????}

????????if(target>root->value)
????????????????root->right=binaryTreeInsert(root->right, target);
????????else if(target<root->value)
????????????????root->left=binaryTreeInsert(root->left, target);
????????root->count++;
????????return root;
}
/**
?* 從一個序列中選定第K大的數字，
?* */
int binaryTreeSelect(Node *root, int k) {
????????/**
?????????* 如果當前root為NULL，則選擇失敗
?????????* */
????????if(root==NULL) {
????????????????printf("\nfind nothing-_-\n");
????????????????return -1;
????????}
????????/**
?????????* 如果root的左子節點為NULL
?????????* */
????????if(root->left==NULL) {
????????????????if(k==1)
????????????????????????return root->value;
????????????????return binaryTreeSelect(root->right, k-1);
????????}
????????/**
?????????* 如果root的左子節點不為NULL；
?????????* 1. 如果K<=leftCount，則Kth個節點在左子樹中
?????????* 2. 如果K==leftCount+1，則kth個節點就是root自身
?????????* 3. 如果k>leftCount+1，則Kth個節點就是右子樹中的k-1-leftCount個節點
?????????* */
????????int leftCount=root->left->count;
????????if(leftCount>=k)
????????????????return binaryTreeSelect(root->left, k);
????????else if(leftCount+1==k)
????????????????return root->value;
????????else
????????????????return binaryTreeSelect(root->right, k-1-leftCount);
}

/**
?* 將指定的元素target旋轉到根節點
?* */
Node* binaryTreeRotate(Node *root, int target) {

????????if(root==NULL)
????????????????return NULL;

????????if(target>root->value) {
????????????????root->right=binaryTreeRotate(root->right,target);
????????????????leftRotate(root);
????????} else if(target<root->value) {
????????????????root->left=binaryTreeRotate(root->left,target);
????????????????rightRotate(root);
????????}

????????return root;
}
/**
?* 此方法尋找root的左子樹中具有最大value的子節點，也就是最‘左邊’的子節點；
?* */
Node* subtreeRightMaximum(Node *root) {
????????Node *cur=root;
????????Node *pre;
????????while(cur!=NULL) {
????????????????pre=cur;
????????????????cur=cur->left;
????????}
????????return pre;
}
/**
?* 此方法尋找root的右子樹中具有最大value的子節點，也就是最‘左邊’的子節點；
?* */
Node* subTreeLeftMaximum(Node* root) {
????????Node *cur=root;
????????Node *pre;
????????while(cur!=NULL) {
????????????????pre=cur;
????????????????cur=cur->right;
????????}
????????return pre;
}

Node* binaryTreeDelete(Node *root, int target) {

????????if(root==NULL)
????????????????return NULL;
????????Node *temp;
????????Node *newRoot;
????????/**
?????????* 如果target比root->value大，則說明其位于root的
?????????* 右子樹，則繼續遞歸
?????????* 如果target比root->value小，則說明其位于root的
?????????* 左子樹，則繼續遞歸
?????????* 如果target等于root->value，則說明當前節點root
?????????* 就是需要刪除的節點，然后分三種情況討論：
?????????* 1. 如果root沒有左右子節點
?????????* 2. 如果root只有左節點或者只有右節點
?????????* 3. 如果root德爾左右子節點都存在；
?????????* */
????????if(target>root->value)
????????????????root->right=binaryTreeDelete(root->right, target);
????????else if(target<root->value)
????????????????root->left=binaryTreeDelete(root->left, target);
????????else {
????????????????if(root->left==NULL && root->right) {
????????????????????????delete root;
????????????????????????return NULL;
????????????????} else if(root->left==NULL) {
????????????????????????temp=root->right;
????????????????????????delete root;
????????????????????????return temp;
????????????????} else if(root->right==NULL) {
????????????????????????temp=root->left;
????????????????????????delete root;
????????????????????????return temp;
????????????????}
????????????????/**
?????????????????* 左右子節點都存在的情況，需要從左右子樹中尋找下一個根節點；
?????????????????* 這里是從右子樹中選取最小的一個節點作為新的根節點；
?????????????????* */
????????????????newRoot=subtreeRightMaximum(root->right);
????????????????/**
?????????????????* 由于右子樹中最小的節點必然至多只有一個右節點，所以其刪除操作
?????????????????* 較為簡單；然后將其的左右子樹替換成當前的左右子樹；
?????????????????* */
????????????????newRoot=binaryTreeDelete(root->right, newRoot->value);
????????????????newRoot->right=root->right;
????????????????newRoot->left=root->left;
????????????????delete root;
????????}

}

? 算法說明：

? BST中搜索和插入的策略都是一樣的，從傳入的樹節點開始，首先判斷其是否為NULL，如果是的話對于搜索來講表示失敗，對于插入來講表示需要插入新的節點；如果不是NULL的話，對于搜索來講比對是否為目標值，然后針對左右子樹遞歸調用，對于插入來講比對是否相同，表示樹中已經有同樣的節點算法說明。

? BST樹的構建和搜索也使用同樣的遍歷策略，所以插入與搜索一樣容易實現；旋轉可用于防止樹變得不平衡，實現刪除，合并和其他操作的輔助操作，BST樹的插入操作可以通過在樹的底部插入新元素，然后使用左旋和右旋將新元素帶到根節點處，防止樹的不平衡狀態。每次BST搜索命中的項也可以通過旋轉帶到根節點處

? 使用BST樹進行選擇算法最大的缺點就是計數域的出現導致額外的內存占用，樹結構改變時需要額外的維護操作，同時我們可以對查找到的節點元素使用旋轉操作，將其放到根節點的位置，下次使用的時候就能很快定位。
http://www.cnblogs.com/zhangchaoyang/articles/1808928.html
BST樹的性能特征：

? 二叉搜索樹算法的運行時間取決于樹的形狀，最好情況下樹可能完全平衡，這樣一次搜索過程就是一條路徑的長度㏒N，最差情況下樹退化為鏈表，這樣一次搜索過程路徑長度可能為N

? 使用插入操作構建BST樹的過程中，越是前面的節點對樹最終形狀的影響越是大，第一個元素就是樹根，對于隨機序列來講，最壞情況出現的概率很小，所以平均情況能保持較好的運行時間，㏒N

? 使用索引項來表示搜索節點，避免動態分配內存。當序列以隨機序列插入時，生成完全平衡樹的概率很小，但二叉樹路徑的長度和樹的高度與BST的搜索開銷聯系緊密。平均情況下一棵根據N個隨機鍵生成的BST樹中，搜索命中（插入和搜索失敗）大約需要1.39㏒N次比較。最壞情況下，可能需要N此比較（也就是順序搜索）http://www.cnblogs.com/zhangchaoyang/articles/1808928.html
https://www.douban.com/note/221942390/

總結

以上是生活随笔為你收集整理的二分查找树性能分析（Binary Search Tree Performance Analysis）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。