1.查找算法概述
查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。
（1）查找定义
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
（2）查找算法分类
1）静态查找和动态查找
注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2）无序查找和有序查找
无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列。
（3）查找算法分析
平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。
Pi：查找表中第i个数据元素的概率。
Ci：找到第i个数据元素时已经比较过的次数。
2.树表查找
2.1二叉树查找算法-- 最简单的树表查找算法
（1）基本思想
二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：
1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）任意节点的左、右子树也分别为二叉查找树。
（2）二叉查找树性质
对二叉查找树进行中序遍历，即可得到有序的数列。
不同形态的二叉查找树如下图所示：
不同形体的二叉查找树
有关二叉查找树的查找、插入、删除等操作的详细讲解，请移步浅谈算法和数据结构: 七 二叉查找树。
（3）复杂度分析
它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡（比如，我们查找上图（b）中的“93”，我们需要进行n次查找操作）。我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。
下图为二叉树查找和顺序查找以及二分查找性能的对比图：
二叉树查找和顺序查找以及二分查找性能的对比
基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。
（4）二叉树查找算法C语言源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ /*头文件:biTree.h*/ #ifndef CHIYX_BITREE #define CHIYX_BITREE #ifndef NULL #define NULL 0 #endif typedef int DataType; //二叉树的节点结构 typedef struct BiTreeNode { DataType data; struct BiTreeNode *parent; struct BiTreeNode *left; struct BiTreeNode *right; }BiTreeNode, *BiTree; //查找：返回第一个等于data域等于key的节点，不存在返回NULL BiTreeNode *search(BiTree *biTree, DataType key); //返回二叉树的最小节点,空树返回NULL BiTreeNode *minImum(BiTree *biTree); //返回二叉树的最大节点,空树返回NULL BiTreeNode *maxImum(BiTree *biTree); //返回节点x的后继节点,不存在后继（节点x为最大节点）返回NULL BiTreeNode *successor(BiTreeNode *x); //返回节点x的前驱节点，不存在前驱（节点x为最小节点）返回NULL BiTreeNode *predecessor(BiTreeNode *x); //将值data插入到二叉树中（生成一个值为data的节点） void insertNode(BiTree *biTree, DataType data); //删除一个值为data的节点 void deleteNode(BiTree *biTree, DataType data); //中序遍历二叉树 void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node)); #endif |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ /*c文件:biTree.c*/ #include <stdlib.h> #include "biTree.h" //查找：返回第一个等于data域等于key的节点，不存在返回NULL BiTreeNode *search(BiTree *biTree, DataType key) { BiTreeNode *curNode = *biTree; while (curNode != NULL && curNode->data != key) { if (key < curNode->data) { curNode = curNode->left; } else { curNode = curNode->right; } } return curNode; } //返回二叉树的最小节点,空树返回NULL BiTreeNode *minImum(BiTree *biTree) { BiTreeNode *curNode = *biTree; while (curNode != NULL && curNode->left != NULL) { curNode = curNode->left; } return curNode; } //返回二叉树的最大节点,空树返回NULL BiTreeNode *maxImum(BiTree *biTree) { BiTreeNode *curNode = *biTree; while (curNode != NULL && curNode->right != NULL) { curNode = curNode->right; } return curNode; } //返回节点x的后继节点,不存在后继（节点x为最大节点）返回NULL BiTreeNode *successor(BiTreeNode *x) { if (x == NULL) return NULL; //存在右子树，则后继节点为其右子树中最小的节点 if (x != NULL && x->right != NULL) { return minImum(&(x->right)); } while (x->parent != NULL && x->parent->right == x) { x = x->parent; } return x->parent; //错误版本为 x， 此处应该返回父结点 } //返回节点x的前驱节点，不存在前驱（节点x为最小节点）返回NULL BiTreeNode *predecessor(BiTreeNode *x) { if (x == NULL) return NULL; //存在左子树，则后继节点为其左子树中最大的节点 if (x != NULL && x->left != NULL) { return maxImum(&(x->left)); } while (x->parent != NULL && x->parent->left == x) { x = x->parent; } return x->parent; //错误版本为 x， 此处应该返回父结点 } void insertNode(BiTree *biTree, DataType data) { //创建节点 BiTreeNode *targetNode; targetNode = (BiTreeNode *)malloc(sizeof(BiTreeNode)); //没有足够内存 if (targetNode == NULL) return; targetNode->data = data; targetNode->parent = NULL; targetNode->left = NULL; targetNode->right = NULL; BiTreeNode *p, *y; p = *biTree; y = NULL; while (p != NULL ) { y = p; if (targetNode->data < p->data) { p = p->left; } else { p = p->right; } } //空树，将新节点置为树根 if (y == NULL) { *biTree = targetNode; } else { if (targetNode->data < y->data) { y->left = targetNode; } else { y->right = targetNode; } } targetNode->parent = y; } //删除一个值为data的节点 void deleteNode(BiTree *biTree, DataType data) { //查找待删除的节点 BiTreeNode *targetNode, *x, *y; targetNode = search(biTree, data); if (targetNode == NULL) return; //找出真正的删除节点，如果目标节点最多只有一个子树，则其为真正删除的节点 //否则其后继节点（最多只有一个子树，想想为什么）为真正删除的节点，然后将后继节点的值赋给目标节点 if (targetNode->left == NULL || targetNode->right == NULL) { y = targetNode; } else { y = successor(targetNode); } if (y->left != NULL) { x = y->left; } else { x = y->right; } if (x != NULL) { x->parent = y->parent; } //如果y是根节点, 则根节点变为x if (y->parent == NULL) { *biTree = x; } else { if (y->parent->right == y) { y->parent->right = x; } else { y->parent->left = x; } } if (y != targetNode) { targetNode->data = y->data; } //释放y占有的空间 free(y); } //中序遍历二叉树 void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node)) { BiTreeNode *curNode; curNode = *biTree; if (curNode != NULL) { //遍历左子树 inorderTraversal(&(curNode->left), visitor); //访问节点 visitor(curNode); //遍历右子树 inorderTraversal(&(curNode->right), visitor); } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ #include <stdio.h> #include <stdlib.h> #include "biTree.h" #define N 10 // 打印输出各个节点的信息 void printNode(BiTreeNode *node) { printf("%d\t", node->data); } int main(int argc, char *argv[]) { BiTreeNode *root; int i; root = NULL; int data[N] = {10, 23, 11, 98, 111, 87, 34, 11, 33, 8}; for (i = 0; i < N; i++) { insertNode(&root, data[i]); } printf("before delete:\n"); inorderTraversal(&root, printNode); printf("\n"); deleteNode(&root, 11); deleteNode(&root, 8); printf("after delete:\n"); inorderTraversal(&root, printNode); printf("\n"); exit(0); } |
（5）二叉树查找算法C++源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ // BSTree.h--二叉查找树 #ifndef _BINARY_SEARCH_TREE_ #define _BINARY_SEARCH_TREE_ #include <iostream> using namespace std; template<typename T> //树结点结构 class BSTNode{ public: T _key; //关键在字（键值） BSTNode *_lchild; //左孩 BSTNode *_rchild; //右孩 BSTNode *_parent; // 双亲 //构造函数 BSTNode(T key ,BSTNode *lchild,BSTNode *rchild,BSTNode *parent): _key(key),_lchild(lchild),_rchild(rchild),_parent(parent){}; }; template<typename T> class BSTree{ private: BSTNode<T> *_Root ; //根结点 public: BSTree():_Root(NULL){}; ~BSTree(){}; void insert (T key);//二叉树的插入 BSTNode<T>* search (T key) ;//二叉树的查找 void preOrder() ; //先序输出 void inOrder() ; //中序输出 void postOrder() ; //后序输出 BSTNode<T>* minimumNode();//查找最小的节点 BSTNode<T>* maximumNode ();//查找最大的节点 T minimumKey();//查找最小的键值 T maximumKey();//查找最小的键值 void print();//打印二叉树 void remove(T key); BSTNode<T>* predecessor(BSTNode<T>* x);//查找某个结点的前驱 BSTNode<T>* sucessor(BSTNode<T>* x); //查找某个结点的后继 void destory (); //内部使用函数，供外部接口调用 private: void insert(BSTNode<T>* &tree,BSTNode<T>* z); BSTNode<T>* search(BSTNode<T>* &tree,T key) const; void preOrder(BSTNode<T>*&tree) const; void inOrder(BSTNode<T>*&tree) const; void postOrder(BSTNode<T>*&tree) const; BSTNode<T>* minimumNode(BSTNode<T> *&tree); BSTNode<T>* maximumNode (BSTNode<T> *&tree); void print(BSTNode<T>*& tree); BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z); void destory(BSTNode<T>*& tree); }; /* *插入操作 *非递归实现 *内部使用函数 */ template<typename T> void BSTree<T> ::insert(BSTNode<T>* &tree,BSTNode<T>* z) { BSTNode<T>* parent = NULL; BSTNode<T>* temp = tree; //寻找插入点 while(temp!=NULL) { parent= temp; if(z->_key>temp->_key) temp= temp->_rchild; else temp=temp->_lchild; } z->_parent = parent; if(parent==NULL) //如果树本来就是空树，则直接把z节点插入根节点 tree = z; else if(z->_key>parent->_key) //如果z的值大于其双亲，则z为其双亲的右孩 parent->_rchild = z; else parent->_lchild = z; } /* * *接口 */ template <typename T> void BSTree<T>::insert(T key) { //创建一个新的节点，使用构造函数初始化 BSTNode<T>* z= new BSTNode<T>(key,NULL,NULL,NULL); if(!z) //如果创建失败则返回 return ; //调用内部函数进行插入 insert(_Root,z); } /* *查找操作 *非递归实现 *内部使用函数 */ template <typename T> BSTNode<T>* BSTree<T>::search(BSTNode<T>* &tree,T key) const { BSTNode<T>* temp = tree; while(temp != NULL) { if(temp->_key == key) return temp; else if(temp->_key>key)d temp = temp->_lchild; else temp = temp->_rchild; } return NULL; } ////查找算法的递归实现 //template<typename T> //BSTNode<T>* BSTree<T>::search( BSTNode<T>* &tree,T key) const //{ // if(!tree) // { // if(tree->_key==key) // return tree; // if(tree->_key>key) // return search(tree->_lchild,key); // if(tree->_key<z->_key) // return search(tree->_rchild,key); // } // return NULL; //} /* *接口 */ template <typename T> BSTNode<T> * BSTree<T>::search(T key) { return search(_Root,key); } /* * *前序遍历算法 *外部使用接口 * */ template<typename T> void BSTree<T>::preOrder(BSTNode<T>*&tree) const { if(tree) { cout<<tree->_key<<" "; preOrder(tree->_lchild); preOrder(tree->_rchild); } } template <typename T> void BSTree<T>::inOrder(BSTNode<T>*&tree) const { if(tree) { inOrder(tree->_lchild); cout<<tree->_key<<" "; inOrder(tree->_rchild); } } template <typename T> void BSTree<T>::postOrder(BSTNode<T>*&tree) const { if(tree) { postOrder(tree->_lchild); postOrder(tree->_rchild); cout<<tree->_key<<" "; } } /* *遍历算法 *分别为前序、中序、后序 *BSTree 类外部接口函数 * */ template<typename T> void BSTree<T>::preOrder() { preOrder(_Root); } template<typename T> void BSTree<T>::inOrder() { inOrder(_Root); } template<typename T> void BSTree<T>::postOrder() { postOrder(_Root); } /* * *查找最小的结点 *内部调用函数 * */ template <typename T> BSTNode<T>* BSTree<T>::minimumNode(BSTNode<T>*&tree) { BSTNode<T>* temp = tree; while(temp->_lchild) { temp= temp->_lchild; } return temp; } /* *接口 */ template<typename T> BSTNode<T>* BSTree<T>::minimumNode() { return minimumNode(_Root); } /* * *查找键值最大的节点 *内部调用函数 *非递归实现 */ template<typename T> BSTNode<T>* BSTree<T>::maximumNode(BSTNode<T>* &tree) { BSTNode<T>* temp=tree; while(temp->_rchild) {er temp= temp->_rchild; } return temp; } /* *接口 */ template<typename T> BSTNode<T>* BSTree<T>::maximumNode() { return maximumNode(_Root); } /* * *查找最小的键值 *外部接口函数 *调用内部函数minimumNode实现 */ template<typename T> T BSTree<T>::minimumKey() { BSTNode<T> *temp = minimumNode(_Root); return temp->_key; } /* * *查找最大的键值 *外部接口函数 *调用内部函数maximumKey */ template<typename T> T BSTree<T>::maximumKey() { BSTNode<T> *temp = maximumNode(_Root); return temp->_key; } /* * *打印函数 *打印出平衡二叉树 *BStree内部函数 */ template<typename T> void BSTree<T>::print(BSTNode<T>*& tree) { if(tree) //如果tree不为空 { if(tree->_lchild) //结点有左孩子 { cout<<"节点"<<tree->_key<<"有左孩子为"<<tree->_lchild->_key<<endl; } else cout<<"节点"<<tree->_key<<"无左孩子"<<endl; if(tree->_rchild) { cout<<"节点"<<tree->_key<<"有右孩子为"<<tree->_rchild->_key<<endl; } else cout<<"节点"<<tree->_key<<"无右孩子"<<endl; print(tree->_lchild); print(tree->_rchild); } } /* *接口 */ template<typename T> void BSTree<T>::print() { print(_Root); } /* *查找某个节点x的前驱 * *外部函数调用 * */ template <typename T> BSTNode<T>* BSTree<T>::predecessor(BSTNode<T>* x) { //如果x是最小的结点，则它没有前驱 if(x->_key == minimumNode(_Root)->_key) return NULL; //否则 //先获取二叉树中键值与x的键值相同的结点y BSTNode <T> * y = NULL; y = search(_Root,x->_key); if(y==NULL) return NULL; //如果y有左孩子，则x的前驱为“以x的左孩为根的子树的最大结点” if(y->_lchild!=NULL) return maximumNode(y->_lchild); //如果y没有左孩子，则x有两种可能： //1.y是一个右孩子，此时x的前驱为其双亲节点 BSTNode<T>* parent = y->_parent; if(parent->_rchild == y) return parent; //2.y是一个左孩子，则其前驱为其双亲结点中“第一个拥有右孩子结点”的结点 while(parent!=NULL&&parent->_rchild==NULL) { parent=parent->_parent; } return parent; } /* *查找某个节点x的后继 * *外部调用接口 * */ template <typename T> BSTNode<T>* BSTree<T>::sucessor(BSTNode<T>* x) { //如果x是键值最大的，则x没有后继结点 if(x->_key==maximumNode(_Root)->_key) return NULL; //获取x在二叉树中的结点y BSTNode<T>* y = NULL; y = search(_Root,x->_key); if(!y) //若二叉树没有此结点 return NULL; //如果y有右孩子，则y的后继为其右孩子的最小结点 if(y->_rchild!=NULL) return minimumNode(y->_rchild); //如果y没有右孩子，则可分为两种情况： //1.y 是左孩子。此时y的后继为y的父结点 BSTNode <T>* parent = y->_parent; if(y->_parent->_lchild == y) return parent; //2.y是右孩子。此时y的后继结点为“第一个拥有左孩且不是y的直接双亲”的结点 while(parent!=NULL) { if(parent->_lchild!=NULL&&parent!=y->_parent) return parent; parent=parent->_parent; } return NULL; } /* * *删除结点 *BSTree类内部调用函数 * */ template <class T> BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z) { BSTNode<T> *x=NULL; BSTNode<T> *y=NULL; if ((z->_lchild == NULL) || (z->_rchild == NULL) ) y = z; else y = sucessor(z); if (y->_lchild != NULL) x = y->_lchild; else x = y->_rchild; if (x != NULL) x->_parent = y->_parent; if (y->_parent == NULL) tree = x; else if (y == y->_parent->_lchild) y->_parent->_lchild = x; else y->_parent->_rchild= x; if (y != z) z->_key = y->_key; return y; } /* * 接口 */ template<typename T> void BSTree<T>::remove(T key) { BSTNode<T> *z, *node; if ((z = search(_Root, key)) != NULL) if ( (node = remove(_Root, z)) != NULL) delete node; } /* * *销毁查找二叉树 *内部调用函数 * */ template<typename T> void BSTree<T>::destory(BSTNode<T>*& tree) { if(tree->_lchild!=NULL) destory(tree->_lchild); if(tree->_rchild!=NULL) destory(tree->_rchild); if(tree->_lchild==NULL&&tree->_rchild==NULL) { delete(tree);<span id="transmark" style="display: none; width: 0px; height: 0px;"></span> tree = NULL; } } /* *接口 */ template<typename T> void BSTree<T>::destory() { destory(_Root); } #endif |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ // BSTree.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include <iostream> #include "BSTree.h" using namespace std; int main() { BSTree<int> s ; int a ; cout<<"请输入二叉树结点以构造二叉查找树："<<endl; while(cin>>a ) s.insert(a); cin.clear(); cout<<"前序遍历二叉查找树:"<<endl; s.postOrder(); cout<<endl; cout<<"中序遍历二叉查找树:"<<endl; s.inOrder(); cout<<endl; cout<<"后序遍历二叉查找树:"<<endl; s.postOrder(); cout<<endl; cout<<"打印二叉查找树"<<endl; s.print(); cout<<"请输入要查找的数："<<endl; while(cin>>a) { BSTNode<int>* findnode = s.search(a); if(!findnode) { cout<<"查找失败"<<endl; s.insert(a); cout<<"已经将"<<a<<"插入二叉查找树,现在二叉查找树为："<<endl; s.inOrder(); cout<<endl; } else { cout<<findnode->_key<<"查找成功"<<endl; } } cin.clear(); cout<<"请输入结点以查找其前驱节点"<<endl; BSTNode<int>* findPreNode= new BSTNode<int>(1,NULL,NULL,NULL); while(cin>>findPreNode->_key) { BSTNode<int>* preNode ; if((preNode= s.predecessor(findPreNode))!=NULL) { cout<<"其前驱结点为："; cout<<preNode->_key<<endl; } else cout<<"没有前驱结点"<<endl; if((preNode= s.sucessor(findPreNode))!=NULL) { cout<<"其后继结点为："; cout<<preNode->_key<<endl; } else cout<<"没有后继结点"<<endl; } cin.clear(); cout<<"请输入要删除的结点："<<endl; while(cin >>a) { s.remove(a); cout<<"删除后的二叉排序树："<<endl; s.inOrder(); } BSTNode<int>* maxNode = s.minimumNode(); if(!maxNode) cout<<"最小的节点为："<<maxNode->_key<<endl; BSTNode<int>* minNode = s.maximumNode(); if(!minNode) cout<<"最大的节点为："<<minNode->_key<<endl; cout<<"销毁二叉树"<<endl; s.destory(); s.inOrder(); system("pause"); return 0; } |
2.2平衡查找树之2-3查找树（2-3 Tree）
（1）2-3查找树定义
和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：
1）要么为空，要么：
2）对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。
3）对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。
平衡查找树之2-3查找树
（2）2-3查找树的性质
1）如果中序遍历2-3查找树，就可以得到排好序的序列；
2）在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。（这也是平衡树中“平衡”一词的概念，根节点到叶节点的最长距离对应于查找算法的最坏情况，而平衡树中根节点到叶节点的距离都一样，最坏情况也具有对数复杂度。
2-3查找树的性质
（3）复杂度分析
2-3树的查找效率与树的高度是息息相关的。
- 在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN
- 在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于631lgN
距离来说，对于1百万个节点的2-3树，树的高度为12-20之间，对于10亿个节点的2-3树，树的高度为18-30之间。
对于插入来说，只需要常数次操作即可完成，因为他只需要修改与该节点关联的节点即可，不需要检查其他节点，所以效率和查找类似。下面是2-3查找树的效率：
2.3平衡查找树之红黑树（Red-Black Tree）
2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgn，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，于是就有了一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。
基本思想：红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。
红黑树示意图
（1）红黑树的定义
红黑树是一种具有红色和黑色链接的平衡查找树，同时满足：
- 红色节点向左倾斜
- 一个节点不可能有两个红色链接
- 整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同。
下图可以看到红黑树其实是2-3树的另外一种表现形式：如果我们将红色的连线水平绘制，那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。
红黑树--2-3查找树-水平红树比较
（2）红黑树的性质
整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同（2-3树的第2）性质，从根节点到叶子节点的距离都相等）。
（3）复杂度分析
最坏的情况就是，红黑树中除了最左侧路径全部是由3-node节点组成，即红黑相间的路径长度是全黑路径长度的2倍。
下图是一个典型的红黑树，从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍：
红黑树最长路径与最短路径比较
红黑树的平均高度大约为logn。
下图是红黑树在各种情况下的时间复杂度，可以看出红黑树是2-3查找树的一种实现，它能保证最坏情况下仍然具有对数的时间复杂度。
红黑树的复杂度
红黑树这种数据结构应用十分广泛，在多种编程语言中被用作符号表的实现，如：
- Java中的util.TreeMap,java.util.TreeSet；
- C++ STL中的：map,multimap,multiset；
- .NET中的：SortedDictionary,SortedSet 等。
2.4 B树和B+树（B Tree/B+ Tree）
（1）B树的定义
平衡查找树中的2-3树以及其实现红黑树。2-3树种，一个节点最多有2个key，而红黑树则使用染色的方式来标识这两个key。
维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。
B树定义：
- B树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。
- 根节点至少有两个子节点
- 每个节点有M-1个key，并且以升序排列
- 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
- 其它节点至少有M/2个子节点
下图是一个M=4 阶的B树:
M=4 阶的B树
可以看到B树是2-3树的一种扩展，他允许一个节点有多于2个的元素。B树的插入及平衡化操作和2-3树很相似，这里就不介绍了。
（2）B+树定义
B+树是对B树的一种变形树，它与B树的差异在于：
- 有k个子结点的结点必然有k个关键码；
- 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
- 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
如下图，是一个B+树:
B+树
（3）B和B+树的区别
区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
B+ 树的优点在于：
- 由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
- B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。
下面是B 树和B+树的区别图：
B 树和B+树的区别图
B/B+树常用于文件系统和数据库系统中，它通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中，如：
- Windows：HPFS文件系统；
- Mac：HFS，HFS+文件系统；
- Linux：ResiserFS，XFS，Ext3FS，JFS文件系统；
- 数据库：ORACLE，MYSQL，SQLSERVER等中。
有关B/B+树在数据库索引中的应用，请看张洋的MySQL索引背后的数据结构及算法原理这篇文章，这篇文章对MySQL中的如何使用B+树进行索引有比较详细的介绍，推荐阅读。
（4）B和B+树C/C++源代码
A.头文件：Btree.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ //头文件：Btree.h #ifndef _BTREE_ #define _BTREE_ #define m 3 /*m 路Btree*/ #define L 3 /*B+ Tree 元素节点最大长度*/ #include <iostream> #include <math.h> #include <stack> using namespace std; class TreeNode { friend class Btree; friend class Result; friend class BPlusTree; public: TreeNode()/*用于区分是否为BPlus 树的叶子节点 即数据节点*/ { keynum=0;/*是数据节点*/ } TreeNode(TreeNode* p1,int k,TreeNode *p2)/*构造根节点*/ { keynum=1; key[1]=k; parent=0; fill(ptr,ptr+m+1,(TreeNode*)0); ptr[0]=p1; ptr[1]=p2; /* 设置子树的父节点*/ if (p1) p1->parent=this; if(p2) p2->parent=this; } TreeNode(TreeNode* p,int *keyarry,TreeNode**ptrarry)/*分裂的新节点*/ { parent=p; fill(ptr,ptr+m+1,(TreeNode*)0); int temp=ceil(m/2.0);//向上取整 ptr[0]=ptrarry[temp]; if(ptr[0])/*分裂后节点的父节点改变*/ ptr[0]->parent=this; for (int i=1;i+temp<=m;i++) { key[i]=keyarry[temp+i]; ptr[i]=ptrarry[temp+i]; if (ptr[i])/*分裂后节点的父节点改变*/ ptr[i]->parent=this; keyarry[temp+i]=0; ptrarry[temp+i]=0; } keyarry[temp]=0; ptrarry[temp]=0; keynum=m-temp; } protected: int keynum;/*关键字个数 keynum <=m-1*/ TreeNode *parent;/*父节点指针*/ TreeNode *ptr[m+1];/*子树指针 0...m */ int key[m+1];/*1...m 多一个单元可以保证当溢出时也可直接插入 之后在进行分裂*/ }; class Result { friend class Btree; public: Result(TreeNode*p=0,int i=0,bool r=0) { ResultPtr=p; index=i; Resultflag=r; } TreeNode * ResultPtr; int index; bool Resultflag; }; class Btree { public: Btree() { root=0; } void InsertBtree(int k); Result Find(int k); void DeleteBtree(int k); void Insert(int k,TreeNode* node,TreeNode* p);/*关键字：k 该关键字k的右子树指针 插入节点a */ protected: void BorrowOrCombine(TreeNode *a,int i,int type,stack<int> &s);/*待处理关键字是a 节点的 i type 标志此次操作的前一次是 对其左 -1 右 1 无0 孩子进行操作*/ //void Insert(int k,TreeNode* node,TreeNode* p);/*关键字：k 该关键字k的右子树指针 插入节点a */ TreeNode *root; }; /*B+Tree */ class DataNode: public TreeNode { friend class BPlusTree; public: DataNode(int k)/*构造第一个数据节点*/ { data[1]=k; parent=0; pre=next=0; datanum=1; }; DataNode(TreeNode* Parent,DataNode*Pre,DataNode* Next,int *dataArray)/*分裂数据节点*/ { parent=Parent; pre=Pre; next=Next; int temp=ceil(L/2.0); // copy(dataArray+1+temp,dataArray+L+1,data+1); for (int i=1;i<=L+1-temp;i++) { data[i]=dataArray[i+temp]; dataArray[i+temp]=0; } datanum=L+1-temp; Pre->datanum=temp; } private: DataNode *pre; DataNode *next; int data[L+2]; int datanum; }; class BPlusTree :public Btree { public: BPlusTree() { root=0; header=0; } void InsertBplustree(int k);/*插入关键字*/ void InsertData(int k,DataNode* dn); void DeleteBPlustree(int k);/*删除关键字k*/ private: DataNode* header; }; #endif |
B.头文件：Btree.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ //头文件：Btree.cpp #include "Btree.h" #include <iostream> #include <math.h> #include <stack> using namespace std; void Btree::InsertBtree(int k) { if (!root) { root=new TreeNode(0,k,0); return ; } TreeNode *a=root;/*当前节点*/ int i=1;/*k关节字 要插入节点a 的位置索引*/ /*找到插入节点*/ while(a) { i=1; /*在a 中找到第一个比关键字k大的关键字的位置 i */ while(i<=a->keynum) { if (k<=a->key[i]) break; else i++; } /* 判断是否继续向下 还是已经到达子节点 */ if (!a->ptr[i-1])/* 已是叶子节点无需向下 直接插入 */ break; else/*不是叶子节点*/ a=a->ptr[i-1]; } if (a->key[i]==k)/*该关键字节点已存在 */ return ; Insert(k,0,a);/*在叶子节点中插入关键字k*/ } void Btree::Insert(int k,TreeNode* node,TreeNode* a)/*关键字：k 该关键字k的右子树指针 插入节点a */ { int i=1; /*在a 中找到第一个比关键字k大的关键字的位置 i */ while(i<=a->keynum) { if (k<=a->key[i]) break; else i++; } /*插入节点为 a 索引为 i */ for (int j=a->keynum;j>=i;j--)/*向后移动以便插入新关键字*/ { a->key[j+1]=a->key[j];/* 关键字*/ a->ptr[j+1]=a->ptr[j];/*子树指针*/ } a->key[i]=k; a->ptr[i]=node; a->keynum++; if (a->keynum<=m-1) return; else {/*分裂节点然后插入父节点 |1 2 3 ...|ceil(m)(向上取整)|... m| */ int midkey=a->key[(int)ceil(m/2.0)];/*中间关键字及 NewNode 要插入父节点*/ TreeNode* NewNode=new TreeNode(a->parent,a->key,a->ptr);/*和a同parent*/ /* for (int i=0;i<=NewNode->keynum;i++) { if (NewNode->ptr[i]) NewNode->ptr[i]->parent=NewNode; }*/ a->keynum=m-ceil(m/2.0); TreeNode * tempa=a;/*记录当前节点*/ a=a->parent;/*父节点*/ if (!a)/*无父节点*/ { TreeNode *NewRoot=new TreeNode(tempa,midkey,NewNode); tempa->parent=NewRoot; NewNode->parent=NewRoot; root=NewRoot; return; } else Insert(midkey,NewNode,a); } } Result Btree::Find(int k) { if (!root) { cout<<"the tree is null !"<<endl; return Result(0,0,0); } TreeNode* a=root; int i=1; while(a) { i=1; while(i<=a->keynum) { if (k<=a->key[i]) { break; } else { i++; } } if (k==a->key[i]) { return Result(a,i,1); } else { if (!a->ptr[i-1]) { return Result(a,i,0); } else { a=a->ptr[i-1]; } } } } void Btree::DeleteBtree(int k) { if (!root) { cout<<"The tree is null !"<<endl; return; } /*转化为删除叶子节点中的关键字 找其右子树的最小关键字*/ stack<int> s;/*记录路径上的 所有 index */ TreeNode *delnode=root;//待删除关键字k所在节点 int i=1; while (delnode&&delnode->keynum)/*delnode->keynum ==0 是对B+树而言*/ { i=1; while(i<=delnode->keynum) { if (k<=delnode->key[i]) { break; } else { i++; } } if (k==delnode->key[i]) { break;/*找到了*/ } else { if (delnode->ptr[i-1]==0) { /*无此关键字*/ cout<<"no this key :"<<k<<endl; return ; } else { /*向下一层*/ delnode=delnode->ptr[i-1]; s.push(i-1);/*通过该索引的指针向下一层查找*/ } } } /* delnode i parent可以提供回去的路 */ TreeNode *p=delnode;/*当前节点*/ if (delnode->ptr[i]&&delnode->ptr[i]->keynum)/*delnode 不是叶子节点*//*B+tree 的元素节点*/ { s.push(i); p=delnode->ptr[i]; while(p->ptr[0]&&p->ptr[0]->keynum)/* p到达delnode 的右子树中最小关键字节点*/ { p=p->ptr[0]; if (!p->ptr[0]->keynum) break; s.push(0); } } if (p!=delnode) { /*将删除操作到对叶子节点的关键字的删除*/ delnode->key[i]=p->key[1]; i=1; } /* p, i 删除关键字由delnode i 转换为 p i */ BorrowOrCombine(p,i,0,s); } void Btree::BorrowOrCombine(TreeNode *a,int i,int type,stack<int> &s)/*待处理关键字是a 节点的 i type 标志此次操作的前一次是 对其左 -1 右 1 无0 孩子进行操作 即这是对叶子节点的操作*/ { if (a==root&&root->keynum==1) { TreeNode * oldroot=root; if (type==-1) { if (root->ptr[i]) root=root->ptr[i]; else root=0; } else if (type==1) { if (root->ptr[i-1]) root=root->ptr[i-1]; else root=0; } else/*不是由下层传递而来*/ { root=0; } if(root) root->parent=0; delete oldroot; return; } int minnum=ceil(m/2.0)-1; TreeNode *la,*ra;/*a 的左右兄弟节点*/ // if (!a->ptr[0])/*a 为叶子节点*/ // { TreeNode *pflag=a->ptr[i-1];/*对B+树 判断哪个元素节点被合并掉了 指针为0*/ if (a->keynum>minnum||a==root) { for (int j=i;j<a->keynum;j++) { a->key[j]=a->key[j+1]; if (type==-1) { a->ptr[j-1]=a->ptr[j]; } else if (type==1) { a->ptr[j]=a->ptr[j+1]; } else { /*这是对叶子节点的操作 B+树 而言*/ if (pflag) { a->ptr[j]=a->ptr[j+1]; } else { a->ptr[j-1]=a->ptr[j]; } } } if (!type&&!pflag) { a->ptr[j-1]=a->ptr[j]; } if (type==-1) { a->ptr[j-1]=a->ptr[j]; } a->key[j]=0; a->ptr[j]=0; a->keynum--; return; } else {/* aa->keynum=minnum */ int index=s.top(); s.pop(); /*能借则借 借优先*/ if (index)/*有左兄弟*/ { la=a->parent->ptr[index-1]; if (la->keynum>minnum)/*左兄弟关键字足够多可以借*/ { /* 从左兄弟借 */ /*向后移动覆盖 i */ for (int j=i;j>1;j--) { a->key[j]=a->key[j-1]; if (type==-1) { a->ptr[j-2]=a->ptr[j-1]; } else if (type==1) { a->ptr[j-1]=a->ptr[j]; } else { if (pflag) { a->ptr[j-1]=a->ptr[j]; } else { a->ptr[j-2]=a->ptr[j-1]; } } } if (!type&&pflag) { a->ptr[j-1]=a->ptr[j]; } if (type==1) { a->ptr[j-1]=a->ptr[j]; } a->key[j]=a->parent->key[index]; a->ptr[0]=la->ptr[la->keynum];/*左兄弟的最右子树*/ /*父节点改变*/ la->ptr[la->keynum]->parent=a; a->parent->key[index]=la->key[la->keynum]; la->key[la->keynum]=0; la->ptr[la->keynum]=0; la->keynum--; return; } } if (index<a->keynum)/*有右兄弟index<=a->keynum*/ { ra=a->parent->ptr[index+1]; if (ra->keynum>minnum)/*右兄弟关键字足够多可以借*/ { /* 从右兄弟借 */ /*向前移动覆盖 i */ for (int j=i;j<a->keynum;j++) { a->key[j]=a->key[j+1]; if (type==-1) { a->ptr[j-1]=a->ptr[j]; } else if (type==1) { a->ptr[j]=a->ptr[j+1]; } else { if (pflag) { a->ptr[j]=a->ptr[j+1]; } else { a->ptr[j-1]=a->ptr[j]; } } } if (!type&&!pflag) { a->ptr[j-1]=a->ptr[j]; } if (type==-1) { a->ptr[j-1]=a->ptr[j]; } a->key[j]=a->parent->key[index+1]; a->ptr[j]=ra->ptr[0];/*右兄弟的最左子树*/ if (ra->ptr[0]) /*叶子节点的 -》ptr【0】==0*/ ra->ptr[0]->parent=a; a->parent->key[index+1]=ra->key[1]; /*右兄弟关键字去头 前移*/ for (int t=1;t<ra->keynum;t++) { ra->ptr[t-1]=ra->ptr[t]; ra->key[t]=ra->key[t+1]; } /*t= ra->keynum */ ra->ptr[t-1]=ra->ptr[t]; ra->key[t]=0; ra->ptr[t]=0; ra->keynum--; return; } } /*合并可能会使 不完善节点向上传递*/ if (index)/*有左兄弟*/ { la=a->parent->ptr[index-1]; if (la->keynum==minnum)/*左兄弟关键字不够多*/ { /* 合并到左兄弟 */ la->key[la->keynum+1]=a->parent->key[index]; /*a 中的关键字填充到其左兄弟中 0 1 2 .... i-1 | i | i+1 ...... kyenum */ for (int l=1;l<=i-1;l++) { la->key[la->keynum+l+1]=a->key[l]; la->ptr[la->keynum+l]=a->ptr[l-1]; /*子树的父节点改变*/ if(a->ptr[l-1]) a->ptr[l-1]->parent=la; } if (type==-1) { la->ptr[la->keynum+l]=a->ptr[l]; if(a->ptr[l]) a->ptr[l]->parent=la; } else if(type==1) { la->ptr[la->keynum+l]=a->ptr[l-1]; if(a->ptr[l-1]) a->ptr[l-1]->parent=la; } else { if (pflag) { la->ptr[la->keynum+l]=a->ptr[l-1]; if(a->ptr[l-1]) a->ptr[l-1]->parent=la; } else { la->ptr[la->keynum+l]=a->ptr[l]; if(a->ptr[l]) a->ptr[l]->parent=la; } } for (l=i;l<a->keynum;l++) { la->key[la->keynum+l+1]=a->key[l+1]; la->ptr[la->keynum+l+1]=a->ptr[l+1]; if(a->ptr[l+1]) a->ptr[l+1]->parent=la; } la->keynum=m-1; TreeNode *tempp=a->parent; tempp->ptr[index]=0; delete a; BorrowOrCombine(tempp,index,1,s); return; } } if (index<a->keynum)/*有右兄弟index<=a->keynum*/ { ra=a->parent->ptr[index+1]; if (ra->keynum==minnum)/*右兄弟关键字不够多*/ { /*合并到右兄弟 */ /* 右兄弟关键字右移 让出合并位置*/ for (int k=ra->keynum;k>0;k--) { ra->key[k+a->keynum]=ra->key[k]; ra->ptr[k+a->keynum]=ra->ptr[k]; } ra->ptr[a->keynum]=ra->ptr[0]; ra->key[a->keynum]=a->parent->key[index+1]; /*a 中的关键字填充到其右兄弟中 0 1 2 .... i-1 | i | i+1 ...... kyenum */ for (int l=1;l<=i-1;l++) { ra->ptr[l-1]=a->ptr[l-1]; ra->key[l]=a->key[l]; /*子树的父节点改变*/ if(a->ptr[l-1]) a->ptr[l-1]->parent=ra; } if (type==-1) { ra->ptr[l-1]=a->ptr[l]; if(a->ptr[l]) a->ptr[l]->parent=ra; } else if (type==1) { ra->ptr[l-1]=a->ptr[l-1]; if(a->ptr[l-1]) a->ptr[l-1]->parent=ra; } else { if (pflag) { ra->ptr[l-1]=a->ptr[l-1]; if(a->ptr[l-1]) a->ptr[l-1]->parent=ra; } else { ra->ptr[l-1]=a->ptr[l]; if(a->ptr[l]) a->ptr[l]->parent=ra; } } /*叶子节点无所谓 都是 0 */ for (l=i+1; l<=a->keynum;l++) { ra->key[l]=a->key[l]; ra->ptr[l]=a->ptr[l]; if(a->ptr[l]) a->ptr[l]->parent=ra; } ra->keynum=m-1; TreeNode *tempp=a->parent; tempp->ptr[index]=0; delete a;/*删除节点a */ /**/ BorrowOrCombine(tempp,index+1,-1,s); return; } } } } /* * ************************************************************** * B+tree */ void BPlusTree::InsertBplustree(int k) { if (!root) { if (!header) { header=new DataNode(k); } else { InsertData(k,header); } return; } /*find the data node where to insert the key */ TreeNode *inode=root; while(inode->keynum)/*不是叶子节点就继续向下*/ { int i=1; while(i<inode->keynum) { if (k>inode->key[i]) { i++; } else break; } if (k<inode->key[i]) { /*左子树*/ inode=inode->ptr[i-1]; } else { /*右子树*/ inode=inode->ptr[i]; } } /*找到相应的叶子节点 inode */ InsertData(k,(DataNode*)inode); } void BPlusTree::InsertData(int k,DataNode* dn) { int i=1; while (i<=dn->datanum) { if (k>dn->data[i]) { i++; } else break; } /**/ if (k==dn->data[i]) { /*关键字已存在*/ return ; } else { /*数据后移以便插入关键字*/ for (int j=L;j>=i;j--) { dn->data[j+1]=dn->data[j]; } dn->data[i]=k; dn->datanum++; if (dn->datanum>L)/*溢出需分裂*/ { /*分裂为前后 两段 dn NewNode*/ DataNode *NewNode=new DataNode(dn->parent,dn,dn->next,dn->data); if (dn->next)/*存在下一个数据节点*/ dn->next->pre=NewNode; dn->next=NewNode; if(!root)/*第一次分裂*/ { root=new TreeNode(dn,NewNode->data[1],NewNode);/*后半段的第一个关键字放在插入其父节点*/ dn->parent=root; NewNode->parent=root; } else { Insert(NewNode->data[1],NewNode,NewNode->parent); } } } } void BPlusTree::DeleteBPlustree(int k) { /*仅有header 无 root*/ if(!root) { if (!header) { cout<<"B+tree is null !"<<endl; return; } else { int i=1; while (i<=header->datanum) { if (k==header->data[i]) { for (int j=i;j<header->datanum;j++) { header->data[j]=header->data[j+1]; } header->datanum--; if(!header->datanum) header=0; return; } else { i++; if(i==header->datanum) { cout<<"No this key :"<<k<<endl; return ; } } } } } /*找到关键字k在的元素节点 d（elete）node */ TreeNode *dnode=root; int i=1; while (dnode->keynum)/*不是元素节点则继续向下查找*/ { i=1; while(i<=dnode->keynum) { if (k>=dnode->key[i]) { i++; } else break; } /*左子树*/ dnode=dnode->ptr[i-1]; } /* 找到相应的元素节点 dnode */ int index=i; int minnum=ceil(L/2);/*元素节点最少关键字数目*/ DataNode *datanode=(DataNode*) dnode; DataNode *la,*ra;/*该元素节点的左右节点*/ if (datanode->datanum>minnum)/*关键字足够多 ，移动覆盖即可*/ { int i=1; while (i<=datanode->datanum) { if (datanode->data[i]==k) { for (int j=i;j<datanode->datanum;j++) { datanode->data[j]=datanode->data[j+1]; } datanode->data[j]=0; datanode->datanum--; return; } else { if (i==datanode->datanum) { cout<<"No this key"<<k<<endl; return; } else i++; } } } else/*元素不够多 从左右邻居节点借或者合并 由上面查找过程知*/ /*index 是该元素节点的索引*/ { /*查找该关键字*/ int i=1; while (i<=datanode->datanum) { /*找到并覆盖*/ if (datanode->data[i]==k) { for (int j=i;j<datanode->datanum;j++) { datanode->data[j]=datanode->data[j+1]; } datanode->data[j]=0; datanode->datanum--; break; } else { if (i==datanode->datanum) { cout<<"No this key"<<k<<endl; return; } else i++; } } /*删除后节点不完善*/ /*借*/ if (index-1)/*有左兄弟*/ { la=(DataNode*)datanode->parent->ptr[index-2]; if (la->datanum>minnum)/*左兄弟的关键字足够多可以借*/ { for (int j=datanode->datanum;j>=1;j--) { datanode->data[j+1]=datanode->data[j]; } datanode->data[1]=la->data[la->datanum];/*最大关键字*/ datanode->parent->key[index-1]=la->data[la->datanum]; la->data[la->datanum]=0; la->datanum--; datanode->datanum++; return; } } if (index<=datanode->parent->keynum)/*有右兄弟*/ { ra=(DataNode*)datanode->parent->ptr[index]; if (ra->datanum>minnum)/*右兄弟的关键字足够多可以借*/ { /*加在datanode末尾*/ datanode->data[datanode->datanum+1]=ra->data[1]; datanode->datanum++; datanode->parent->key[index]=ra->data[2]; /*右兄弟移动覆盖*/ for (int j=1;j<ra->datanum;j++) { ra->data[j]=ra->data[j+1]; } ra->data[j]=0; ra->datanum--; return; } } /*邻居节点的关键字不够多 合并*/ if (index-1)/*有左兄弟*/ { /*关键字合并到左兄弟尾部 并且删除对应搜索节点的关键字*/ la=(DataNode*)datanode->parent->ptr[index-2]; for (int j=1;j<=datanode->datanum;j++) { la->data[la->datanum+1]=datanode->data[j]; } la->parent->ptr[index-1]=0; la->next=datanode->next; if (datanode->next)/*是尾节点*/ datanode->next->pre=la; delete datanode; DeleteBtree(la->parent->key[index-1]); return; } if (index<=datanode->parent->keynum)/*有右兄弟*/ { /*关键字合并到右兄弟头部 并且删除对应搜索节点的关键字*/ ra=(DataNode*)datanode->parent->ptr[index]; /*右兄弟关键字后移出位置以便合并*/ for (int j=ra->datanum;j>=1;j--) { ra->data[j+datanode->datanum]=ra->data[j]; } /*填充到右兄弟节点头部*/ for (int l=1;l<=datanode->datanum;l++) { ra[l]=datanode[l]; } ra->datanum+=datanode->datanum; /*数据节点链操作 注意首尾的处理*/ ra->pre=datanode->pre; if (datanode->pre) { datanode->pre->next=ra; } else { /*datanode 为 header*/ header=ra; } ra->parent->ptr[index-1]=0; delete datanode; DeleteBtree(ra->parent->key[index]); return; } } } |
C.主函数文件：main.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */<span id="transmark" style="display: none; width: 0px; height: 0px;"></span> #include "Btree.h" #include <iostream> #include <math.h> using namespace std; void main() { /* int a=5; cout<<ceil(a/2.0)<<endl;*/ /*B树*/ Btree b; b.InsertBtree(33); b.InsertBtree(44); b.InsertBtree(28); b.InsertBtree(73); b.InsertBtree(52); b.InsertBtree(218); b.InsertBtree(71); b.DeleteBtree(44); b.DeleteBtree(33); b.DeleteBtree(73); b.DeleteBtree(28); b.DeleteBtree(52); b.DeleteBtree(218); b.DeleteBtree(44); b.DeleteBtree(71); b.DeleteBtree(44); /*B+树*/ /* BPlusTree bp; bp.InsertBplustree(2); bp.InsertBplustree(3); bp.InsertBplustree(32); bp.InsertBplustree(13); bp.InsertBplustree(62); bp.InsertBplustree(93); bp.InsertBplustree(27); bp.InsertBplustree(83); bp.InsertBplustree(392); bp.InsertBplustree(173); bp.InsertBplustree(652); bp.InsertBplustree(923); bp.DeleteBPlustree(13); bp.DeleteBPlustree(27); bp.DeleteBPlustree(3); bp.DeleteBPlustree(2); */ } |
2.5树表查找总结：
二叉查找树平均查找性能不错，为O(logn)，但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化，我们可以使用平衡查找树。平衡查找树中的2-3查找树，这种数据结构在插入之后能够进行自平衡操作，从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难，红黑树是2-3树的一种简单高效的实现，他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树，应用非常广泛，很多编程语言的内部实现都或多或少的采用了红黑树。
除此之外，2-3查找树的另一个扩展——B/B+平衡树，在文件系统和数据库系统中有着广泛的应用。
