二分搜索樹

1.二分搜索樹特點:
每個節點的鍵值大於左孩子; 每個節點的鍵值小於右孩子;以左右孩子為根的子樹仍為二分搜索樹 ;不是完全二叉樹
2.優勢:
高效,不僅可以查找數據;還可以高效的插入,刪除數據-動態維護數據
3.二分搜索樹的侷限性:
  1.二分搜索樹的排列不同,對應的時間複雜度不同:最差可以退化為鏈表的形式O(n)
  2.改造二叉樹(防止其變成鏈表):平衡二叉樹(如:紅黑樹,2-3樹,AVLL 樹,Splay樹)
  3.其他樹形問題(遞歸):
    歸併排序
    快速排序
    搜索問題(搜索樹,8皇后)
    數獨…
4.其他樹:
KD樹,區間樹,哈夫曼樹…
5.時間複雜度:

  查找元素 插入元素 刪除元素
普通數組 O(n) O(n) O(n)
順序數組 O(logn) O(n) O(n)
二分搜索樹 O(logn) O(logn) O(logn)

遍歷:時間複雜度O(n)
刪除:時間複雜度O(logn)
二分搜索樹實現代碼:

  1 #include <iostream>
  2 #include <queue>
  3 #include <cassert>
  4 using namespace std;
  5 
  6 template<typename Key ,typename Value>
  7 class BST{
  8 private:
  9         struct Node{
 10             Key key;
 11             Value  value;
 12             Node *left;
 13             Node *right;
 14             Node(Key key,Value value){
 15                 this->key = key;
 16                 this->value = value;
 17                 this->left = this->right = NULL;
 18             }
 19             Node(Node *node){
 20                 this->key = node->key;
 21                 this->value = node->value;
 22                 this->left = node->left;
 23                 this->right = node->right; 
 24             }
 25         };
 26     Node *root;
 27     int count;
 28 public:
 29         BST(){
 30             root = NULL;
 31             count = 0;
 32         }
 33         ~BST(){
 34             destroy(root); 
 35         }
 36         int size(){
 37             return count;
 38         }
 39         bool isEmpty(){
 40             return count == 0;
 41         }
 42         void insert(Key key,Value value){
 43             root =  insert(root,key,value) ;
 44         }
 45         bool contain(Key key){
 46             return contain(root,key);
 47         } 
 48         Value* search(Key key){
 49             return search(root,key);
 50         }
 51         //前序遍歷
 52         void preOrder(){
 53             preOrder(root);
 54         } 
 55         //中序遍歷
 56         void inOrder(){
 57             inOrder(root);
 58         } 
 59         //後序遍歷
 60         void postOrder(){
 61             postOrder(root);
 62         } 
 63         //層序遍歷
 64         void levelOrder(){
 65             queue<Node*> q;
 66             q.push(root);
 67             while( !q.empty()){
 68                 Node *node = q.front();
 69                 q.pop();
 70                 cout<<node->key<<endl;
 71                 if(node->left)
 72                     q.push(node->left);
 73                 if(node->right)
 74                     q.push(node->right);
 75             }
 76         } 
 77         
 78         //尋找最小的鍵值 
 79         Key minimum(){
 80             assert(count != 0);
 81             Node* minNode =  minimum(root);
 82             return minNode->key;
 83         }
 84         //尋找最大的鍵值 
 85         Key maximum(){
 86             assert(count != 0);
 87             Node* maxNode =  maximum(root);
 88             return maxNode->key;
 89         }  
 90         
 91         //從二叉樹中刪除最小值所在的節點
 92         void removeMin(){
 93             if (root)
 94             root = removeMin( root );
 95         }
 96         //從二叉樹中刪除最大值所在的節點
 97         void removeMax(){
 98             if (root)
 99             root = removeMax( root );
100         }  
101         //從二叉樹中刪除鍵值為key 的節點
102         void remove(Key key){
103         root =    remove(root,key);
104         } 
105          
106         private:
107             //向以node為根的二叉搜索樹中,插入節點(key,value) 
108             //返回插入新節點的二叉搜索樹的根 
109             Node* insert(Node *node,Key key,Value value){    
110                 if(node == NULL){
111                     count ++;
112                     return new Node(key,value);
113                 }
114                 if(key==node->key)
115                     node->value = value;
116                 else if (key < node->key)
117                     node->left = insert(node->left,key,value);
118                 else
119                     node->right = insert(node->right,key,value);
120                     return node;
121             }
122             //查看以node為根的二叉搜索樹中是否包含鍵值為key的節點 
123             bool contain(Node* node , Key key){
124                 if(key==node->key)
125                 return true;
126                 else if(key<node->key) 
127                     return contain(node->left,key);
128                 else 
129                     return contain(node->right,key);
130             }            
131             Value* search(Node* node,Key key){
132                 if(node ==NULL)
133                 return NULL;
134                 if(key == node->key)
135                     return &(node->value);
136                 else if(key < node->value)
137                     return search(node->left,key);
138                 else
139                     return search(node->right,key);
140             }
141             //對以node為根的二叉搜索樹進行前序遍歷 
142             void preOrder(Node* node){
143                 if(node != NULL)
144                 cout<<node->key<<endl;
145                 preOrder(node->left);
146                 preOrder(node->right);
147             }
148             //對以node為根的二叉搜索樹進行中序遍歷
149             void inOrder(Node* node){
150                 if(node != NULL){
151                     inOrder(node->left);
152                     cout<<node->key<<endl;
153                     inOrder(node->right);
154                 }
155             }
156             //對以node為根的二叉搜索樹進行後序遍歷
157             void postOrder(Node* node){
158                 if(node != NULL){
159                     postOrder(node->left);
160                     postOrder(node->right);
161                     cout<<node->key<<endl;
162                 }
163             }
164             //釋放內存 
165             void destroy(Node* node){
166                 if(node != NULL){
167                     destroy(node->left);
168                     destroy(node->right);
169                     delete node;
170                     count --;
171                 }
172             }
173             //在以node為根的二叉搜索樹中,返回最小鍵值的節點 
174             Node* minimum(Node* node){
175                 if(node->left == NULL)
176                 return node;
177             return minimum(node->left); 
178             }
179             
180             //在以node為根的二叉搜索樹中,返回最大鍵值的節點 
181             Node* maximum(Node* node){
182                 if(node->right == NULL)
183                 return node;
184             return maximum(node->right); 
185             }
186             //刪除掉以node為根的二分搜索樹中的最小節點 
187             //返回刪除節點後的二分搜索樹 
188             Node* removeMin(Node* node){
189                 if(node->left  == NULL){
190                     Node* rightNode  = node->right;
191                     delete node;
192                     return rightNode;
193                 } 
194                 node->left =  removeMin(node->left);
195                 return node;
196             }
197             //刪除掉以node為根的二分搜索樹中的最大節點 
198             //返回刪除節點後的二分搜索樹 
199             Node* removeMax(Node* node){
200                 if(node->right  == NULL){
201                     Node* leftNode  = node->left;
202                     delete node;
203                     return leftNode;
204                 } 
205                 node->right =  removeMax(node->right);
206                 return node;
207             }
208             //刪除掉以node為根的二分搜索樹中鍵值為key的節點 
209             //返回刪除節點後的二分搜索樹 
210             Node* remove(Node* node,Key key){
211                 if(node == NULL)
212                 return NULL;
213                 if(key < node->key){
214                     node->left = remove(node->left,key);
215                     return node;
216                 }
217                 else if (key > node->key){
218                     node->right = remove(node->right,key);
219                     return node;
220                 }
221                 else{  //key = node->key
222                         if(node->left ==NULL){
223                             Node *rightNode = node->right;
224                             delete node;
225                             count --;
226                             return rightNode;
227                         }
228                         
229                         if(node->right ==NULL){
230                             Node *leftNode = node->left;
231                             delete node;
232                             count --;
233                             return leftNode;
234                         }
235                         
236                         //:node的左右孩子都不為空
237                         Node *successor = new Node(minimum(node->right));
238                         count ++;
239                         successor->right = removeMin(node->right);
240                         successor->left = node->left;
241                         delete node;
242                         count --;
243                         return successor;
244                 }
245             }
246 }; 
247 int main(int argc, char** argv) {
248     return 0;
249 }

測試省略

關鍵詞:node key return right left if 搜索 value root null

相關推薦:

平衡二叉樹的java實現

鏈表<新>

Python鏈表

Splay模板講解及一些題目

bootstrap treetable 樹形網格,動態擴展,連數據庫

二分查找法

bootstrap treeview樹形菜單 動態擴展 連數據庫

Python與數據結構[0] -> 鏈表/LinkedList[1] -> 雙鏈表與循環雙鏈表的 Python 實現