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-> 23 this->right = node->right; 24 25 }; 26 Node *root; 27 int count; 28 public 29 BST(){ 30 root = 31 count = 0; 32 } 33 ~BST(){ 34 destroy(root); 35 36 size(){ 37 return 38 39 bool isEmpty(){ 40 return count == 41 42 void insert(Key key,1)"> 43 root = insert(root,key,value) ; 44 45 contain(Key key){ 46 contain(root,key); 47 } 48 Value* search(Key key){ 49 search(root,1)"> 50 51 //前序遍历 52 preOrder(){ 53 preOrder(root); 54 55 中序遍历 56 inOrder(){ 57 inOrder(root); 58 59 后序遍历 60 postOrder(){ 61 postOrder(root); 62 63 层序遍历 64 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 right) 74 q.push(node->right); 75 76 77 78 寻找最小的键值 79 Key minimum(){ 80 assert(count != ); 81 Node* minNode = minimum(root); 82 return minNode-> 83 84 寻找最大的键值 85 Key maximum(){ 86 assert(count != 87 Node* maxNode = maximum(root); 88 return maxNode-> 89 } 90 91 从二叉树中删除最小值所在的节点 92 removeMin(){ 93 if (root) 94 root = removeMin( root ); 95 96 从二叉树中删除最大值所在的节点 97 removeMax(){ 98 99 root = removeMax( root ); 100 101 从二叉树中删除键值为key 的节点 102 remove(Key key){ 103 root = remove(root,1)">104 105 106 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 =116 else if (key < node->117 node->left = insert(node->left,1)">118 else 119 node->right = insert(node->right,1)">120 node; 121 122 查看以node为根的二叉搜索树中是否包含键值为key的节点 123 bool contain(Node* node,Key key){ 124 125 true126 if(key<node->key) 127 return contain(node->128 else 129 130 } 131 Value* search(Node*132 NULL) 133 134 if(key == node->135 return &(node->value); 136 if(key < node->value) 137 return search(node->138 139 140 141 对以node为根的二叉搜索树进行前序遍历 142 void preOrder(Node* node){ 143 if(node != NULL) 144 cout<<node->key<<145 preOrder(node->146 preOrder(node->147 148 对以node为根的二叉搜索树进行中序遍历 149 void inOrder(Node*150 151 inOrder(node->152 cout<<node->key<<153 inOrder(node->154 155 156 对以node为根的二叉搜索树进行后序遍历 157 void postOrder(Node*158 159 postOrder(node->160 postOrder(node->161 cout<<node->key<<162 163 164 释放内存 165 void destroy(Node*166 167 destroy(node->168 destroy(node->169 delete170 count --171 172 173 在以node为根的二叉搜索树中，返回最小键值的节点 174 Node* minimum(Node*175 if(node->left ==176 177 return minimum(node->left); 178 179 180 在以node为根的二叉搜索树中，返回最大键值的节点 181 Node* maximum(Node*182 if(node->right ==183 184 return maximum(node->right); 185 186 删除掉以node为根的二分搜索树中的最小节点 187 返回删除节点后的二分搜索树 188 Node* removeMin(Node*189 if(node->left ==190 Node* rightNode = node->191 192 rightNode; 193 } 194 node->left = removeMin(node->195 196 197 删除掉以node为根的二分搜索树中的最大节点 198 199 Node* removeMax(Node*200 if(node->right ==201 Node* leftNode = node->202 203 leftNode; 204 205 node->right = removeMax(node->206 207 208 删除掉以node为根的二分搜索树中键值为key的节点 209 210 Node* remove(Node*211 212 213 key){ 214 node->left = remove(node->215 216 217 if (key > node->218 node->right = remove(node->219 220 221 else{ key = node->key 222 NULL){ 223 Node *rightNode = node->224 225 count --226 227 } 228 229 230 Node *leftNode = node->231 232 count --233 234 235 236 :node的左右孩子都不为空 237 Node *successor = new Node(minimum(node->right)); 238 count ++239 successor->right = removeMin(node->240 successor->left = node->241 242 count --243 successor; 244 245 246 }; 247 int main(int argc,char** argv) { 248 return 249 }
测试省略
原文链接：/algorithms/997823.html