热线电话：13121318867

登录
首页精彩阅读算法导论_二叉搜索树_数据分析师
算法导论_二叉搜索树_数据分析师
2014-12-10
收藏

算法导论_二叉搜索树_数据分析师

先上二叉树查找树的删除的代码，因为删除是二叉查找树最复杂的操作：

 

[cpp] view plaincopy
  1. int BinarySearchTree<T>::tree_remove(const T& elem) 
  2. { 
  3.     BinarySearchTreeNode<T> *z = tree_search(elem);//根据元素查找到要删除的节点 
  4.     BinarySearchTreeNode<T> *x, *y; 
  5.  
  6.     if (z != NULL) 
  7.     { 
  8.         //用y来表示实际要删除的节点 
  9.         if (z->left == NULL || z->right == NULL)//最多只有一个儿子节，要么没有儿子节点 
  10.             y = z; 
  11.         else 
  12.             y = tree_search(tree_successor(elem));//有两个儿子的时候实际删除的是后继节点 
  13.  
  14.         //因为有上面的if语句，所以y要么只有一个儿子，要么没有儿子。后继节点只有右儿子或者没有儿子 
  15.         //所以x要么是儿子节点，要么是空节点 
  16.         if (y->left != NULL) 
  17.             x = y->left; 
  18.         else 
  19.             x = y->right; 
  20.  
  21.         if (x != NULL)//判断y节点有没有儿子节点，有的花就把y节点的父节点变成x的父节点。 
  22.             x->parent = y->parent; 
  23.  
  24.         //y是根节点或者不是根节点的情况 
  25.         if (y->parent == NULL) 
  26.             root = x; 
  27.         else if (y == y->parent->left)//如果y节点不是根节点的情况该怎么处理呢？ 
  28.             y->parent->left = x; 
  29.         else 
  30.             y->parent->right = x; 
  31.  
  32.         //处理后继节点的情况，因为y表示后继的时候y！=z； 
  33.         if (y != z) 
  34.             z->elem = y->elem; 
  35.         delete y; 
  36.     } 
  37.  
  38.     return -1; 
  39. } 

    二叉查找树的概念及操作。主要内容包括二叉查找树的性质，如何在二叉查找树 中查找最大值、最小值和给定的值，如何找出某一个元素的前驱和后继，如何在二叉查找树中进行插入和删除操作。在二叉查找树上执行这些基本操作的时间与树的 高度成正比，一棵随机构造的二叉查找树的期望高度为O(lgn)，从而基本动态集合的操作平均时间为θ(lgn)。

1、二叉查找树

　　二叉查找树是按照二叉树结构来组织的，因此可以用二叉链表结构表示。二叉查找树中的关键字的存储方式满足的特征是：设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点，则key[y]≤key[x]。如果y是x的右子树中的一个结点，则key[x]≤key[y]。根据二叉查找树的特征可知，采用中根遍历一棵二叉查找树，可以得到树中关键字有小到大的序列。

一棵二叉树查找及其中根遍历结果如下图所示：

    书中给出了一个定理：如果x是一棵包含n个结点的子树的根，则其中根遍历运行时间为θ(n)。

    问题：二叉查找树性质与最小堆之间有什么区别？能否利用最小堆的性质在O(n)时间内，按序输出含有n个结点的树中的所有关键字？

2、查询二叉查找树

　　二叉查找树中最常见的操作是查找树中的某个关键字，除了基本的查询，还支持最大值、最小值、前驱和后继查询操作，书中就每种查询进行了详细的讲解。

（1）查找SEARCH

　　在二叉查找树中查找一个给定的关键字k的过程与二分查找很类似，根据二叉查找树在的关键字存放的特征，很容易得出查找过程：首先是关键字k与树根的关 键字进行比较，如果k大比根的关键字大，则在根的右子树中查找，否则在根的左子树中查找，重复此过程，直到找到与遇到空结点为止。例如下图所示的查找关键 字13的过程：（查找过程每次在左右子树中做出选择，减少一半的工作量）

    书中给出了查找过程的递归和非递归形式的伪代码：

 

[cpp] view plaincopy
  1. TREE_SEARCH(x,k) 
  2.   if x=NULL or k=key[x] 
  3.       then return x 
  4.   if(k<key[x]) 
  5.       then return TREE_SEARCH(left[x],k) 
  6.    else 
  7.       then return TREE_SEARCH(right[x],k) 

[cpp] view plaincopy
  1. ITERATIVE_TREE_SEARCH(x,k) 
  2.   while x!=NULL and k!=key[x] 
  3.       do if k<key[x] 
  4.               then x=left[x] 
  5.            else 
  6.               then x=right[x] 
  7.    return x 


（2）查找最大关键字和最小关键字

　　根据二叉查找树的特征，很容易查找出最大和最小关键字。查找二叉树中的最小关键字：从根结点开始，沿着各个节点的left指针查找下去，直到遇到 NULL时结束。如果一个结点x无左子树，则以x为根的子树中，最小关键字就是key[x]。查找二叉树中的最大关键字：从根结点开始，沿着各个结点的 right指针查找下去，直到遇到NULL时结束。书中给出了查找最大最小关键字的伪代码：

 

[cpp] view plaincopy
  1. TREE_MINMUM(x) 
  2.  
  3. hile left[x] != NULL 
  4.  
  5. do x=left[x] 
  6.  
  7. eturn x 

 

 

[cpp] view plaincopy
  1. TREE_MAXMUM(x) 
  2.  
  3. while right[x] != NULL 
  4.  
  5. do x= right[x] 
  6.  
  7. return x 


（3）前驱和后继

　　给定一个二叉查找树中的结点，找出在中序遍历顺序下某个节点的前驱和后继。如果树中所有关键字都不相同，则某一结点x的前驱就是小于key[x]的所 有关键字中最大的那个结点，后继即是大于key[x]中的所有关键字中最小的那个结点。根据二叉查找树的结构和性质，不用对关键字做任何比较，就可以找到 某个结点的前驱和后继。

　　查找前驱步骤：先判断x是否有左子树，如果有则在left[x]中查找关键字最大的结点，即是x的前驱。如果没有左子树，则从x继续向上执行此操作，直到遇到某个结点是其父节点的右孩子结点。例如下图查找结点7的前驱结点6过程：

　　查找后继步骤：先判断x是否有右子树，如果有则在right[x]中查找关键字最小的结点，即使x的后继。如果没有右子树，则从x的父节点开始向上查找，直到遇到某个结点是其父结点的左儿子的结点时为止。例如下图查找结点13的后继结点15的过程：

    书中给出了求x结点后继结点的伪代码:

 

[cpp] view plaincopy
  1. TREE_PROCESSOR(x) 
  2.     if right[x] != NULL 
  3.         then return TREE_MINMUM(right(x)) 
  4.     y=parent[x] 
  5.     while y!= NULL and x ==right[y] 
  6.            do x = y 
  7.                y=parent[y] 
  8.     return y  

    定理：对一棵高度为h的二叉查找，动态集合操作SEARCH、MINMUM、MAXMUM、SUCCESSOR、PROCESSOR等的运行时间均为O(h)。

3、插入和删除

　　插入和删除会引起二叉查找表示的动态集合的变化，难点在在插入和删除的过程中要保持二叉查找树的性质。插入过程相当来说要简单一些，删除结点比较复杂。

（1）插入

　　插入结点的位置对应着查找过程中查找不成功时候的结点位置，因此需要从根结点开始查找带插入结点位置，找到位置后插入即可。下图所示插入结点过程：

    书中给出了插入过程的伪代码：

 

[cpp] view plaincopy
  1. TREE_INSERT(T,z) 
  2.     y = NULL; 
  3.     x =root[T] 
  4.     while x != NULL 
  5.         do y =x 
  6.             if key[z] < key[x] 
  7.                  then x=left[x] 
  8.                  else  x=right[x] 
  9.      parent[z] =y 
  10.      if y=NULL 
  11.         then root[T] =z 
  12.         else if key[z]>key[y] 
  13.                    then  keft[y]  = z 
  14.                    else   right[y] =z 


插入过程运行时间为O(h)，h为树的高度。

（2）删除

　　从二叉查找树中删除给定的结点z，分三种情况讨论：

<1>结点z没有左右子树，则修改其父节点p[z]，使其为NULL。删除过程如下图所示：

<2>如果结点z只有一个子树（左子树或者右子树），通过在其子结点与父节点建立一条链来删除z。删除过程如下图所示：

<3>如果z有两个子女，则先删除z的后继y（y没有左孩子），在用y的内容来替代z的内容。

书中给出了删除过程的伪代码：

 

[cpp] view plaincopy
  1. TREE_DELETE(T,z) 
  2.     if left[z] ==NULL or right[z] == NULL 
  3.        then y=z 
  4.        else  y=TREE_SUCCESSOR(z) 
  5.    if left[y] != NULL 
  6.        then x=left[y] 
  7.        else  x=right[y] 
  8.    if x!= NULL 
  9.        then parent[x] = parent[y] 
  10.    if p[y] ==NULL 
  11.       then root[T] =x 
  12.       else if y = left[[prarnt[y]] 
  13.                   then left[parent[y]] = x 
  14.                   else  right[parent[y]] =x 
  15.     if y!=z 
  16.         then key[z] = key[y] 
  17.               copy y's data into z 
  18.      return y 

定理：对高度为h的二叉查找树，动态集合操作INSERT和DELETE的运行时间为O(h)。

4、实现测试

　　采用C++语言实现一个简单的二叉查找树，支持动态集合的基本操作：search、minmum、maxmum、predecessor、successor、insert和delete。设计的二叉查找树结构如下所示：

 

[cpp] view plaincopy
  1. template<class T> 
  2. class BinarySearchTreeNode 
  3. { 
  4. public: 
  5.     T elem; 
  6.     BinarySearchTreeNode<T> *parent; 
  7.     BinarySearchTreeNode<T> *left; 
  8.     BinarySearchTreeNode<T> *right; 
  9. }; 
  10.  
  11. template<class T> 
  12. class BinarySearchTree 
  13. { 
  14. public: 
  15.     BinarySearchTree(); 
  16.     void tree_insert(const T& elem); 
  17.     int tree_remove(const T& elem); 
  18.     BinarySearchTreeNode<T> *tree_search(const T& elem) const; 
  19.     T tree_minmum(BinarySearchTreeNode<T>* root) const; 
  20.     T tree_maxmum(BinarySearchTreeNode<T>* root) const; 
  21.     T tree_successor(const T& elem) const; 
  22.     T tree_predecessor(const T& elem) const; 
  23.     int empty() const; 
  24.     void inorder_tree_walk() const; 
  25.     BinarySearchTreeNode<T>* get_root() { return root; } 
  26.  
  27. private: 
  28.     BinarySearchTreeNode<T>* root; 
  29. }; 


 完整程序如下所示：

 

[cpp] view plaincopy
  1. #include<iostream> 
  2. #include<stack> 
  3.  
  4. using namespace std; 
  5. /*-----------------------------------------------------------------------------------------------*/ 
  6. /*采用C++语言实现一个简单的二叉查找树，支持动态集合的基本操作：                                      */ 
  7. /*search、minmum、maxmum、predecessor、successor、insert和delete。设计的二叉查找树结构如下所示：    */ 
  8. /*------------------------------------------------------------------------------------------------*/ 
  9.  
  10. template<class T> 
  11. class BinarySearchTreeNode 
  12. { 
  13. public: 
  14.     T elem; 
  15.     BinarySearchTreeNode<T> *parent; 
  16.     BinarySearchTreeNode<T> *left; 
  17.     BinarySearchTreeNode<T> *right; 
  18. }; 
  19.  
  20. template<class T> 
  21. class BinarySearchTree 
  22. { 
  23. public: 
  24.     BinarySearchTree(); 
  25.     void tree_insert(const T& elem); 
  26.     int tree_remove(const T& elem); 
  27.     BinarySearchTreeNode<T> *tree_search(const T& elem) const; 
  28.     T tree_minmum(BinarySearchTreeNode<T>* root) const; 
  29.     T tree_maxmum(BinarySearchTreeNode<T>* root) const; 
  30.     T tree_successor(const T& elem) const; 
  31.     T tree_predecessor(const T& elem) const; 
  32.     int empty() const; 
  33.     void inorder_tree_walk() const; 
  34.     BinarySearchTreeNode<T>* get_root() { return root; } 
  35.  
  36. private: 
  37.     BinarySearchTreeNode<T>* root; 
  38. }; 
  39.  
  40. //构造函数，初始化二叉查找树。 
  41. template <class T> 
  42. BinarySearchTree<T>::BinarySearchTree() 
  43. { 
  44.     root = NULL; 
  45. } 
  46.  
  47.  
  48. template <class T> 
  49. void BinarySearchTree<T>::tree_insert(const T& elem) 
  50. { 
  51.     if (!empty()) 
  52.     { 
  53.         BinarySearchTreeNode<T> *p_node = root; 
  54.         BinarySearchTreeNode<T> *q_node = NULL; 
  55.         BinarySearchTreeNode<T> *new_node = new BinarySearchTreeNode<T>; 
  56.  
  57.         new_node->elem = elem; 
  58.         new_node->left = NULL; 
  59.         new_node->right = NULL; 
  60.         new_node->parent = NULL; 
  61.  
  62.         while (p_node) 
  63.         { 
  64.             q_node = p_node; 
  65.             if (p_node->elem > elem) 
  66.                 p_node = p_node->left; 
  67.             else 
  68.                 p_node = p_node->right; 
  69.         }//当p_node为空的时候，q_node正好是正确的插入位置的父节点，且q_node是叶节点. 
  70.  
  71.         if (q_node->elem > elem) 
  72.             q_node->left = new_node; 
  73.         else 
  74.             q_node->right = new_node; 
  75.         new_node->parent = q_node; 
  76.     } 
  77.     else 
  78.     { 
  79.         root = new BinarySearchTreeNode<T>; 
  80.         root->elem = elem; 
  81.         root->parent = NULL; 
  82.         root->left = NULL; 
  83.         root->right = NULL; 
  84.     } 
  85. } 
  86.  
  87. //二叉查找树节点的删除 
  88. template <class T> 
  89. int BinarySearchTree<T>::tree_remove(const T& elem) 
  90. { 
  91.     BinarySearchTreeNode<T> *z = tree_search(elem); 
  92.     BinarySearchTreeNode<T> *x, *y; 
  93.  
  94.     if (z != NULL) 
  95.     { 
  96.         //用y来表示实际要删除的节点 
  97.         if (z->left == NULL || z->right == NULL)//最多只有一个儿子节，要么没有儿子节点 
  98.             y = z; 
  99.         else 
  100.             y = tree_search(tree_successor(elem));//有两个儿子的时候实际删除的是后继节点 
  101.  
  102.         //因为有上面的if语句，所以y要么只有一个儿子，要么没有儿子。后继节点只有右儿子或者没有儿子 
  103.         //所以x要么是儿子节点，要么是空节点 
  104.         if (y->left != NULL) 
  105.             x = y->left; 
  106.         else 
  107.             x = y->right; 
  108.  
  109.         if (x != NULL) 
  110.             x->parent = y->parent; 
  111.  
  112.         if


CDA数据分析师考试相关入口一览（建议收藏）：

▷ 想报名CDA认证考试，点击>>>   “CDA报名” 了解CDA考试详情；

▷ 想加入CDA考试题库，点击>>> “CDA题库” 了解CDA考试详情；

▷ 想学习CDA考试教材，点击>>> “CDA教材” 了解CDA考试详情；

▷ 想查询CDA考试成绩，点击>>> “CDA成绩” 了解CDA考试详情；

▷ 想了解CDA考试含金量，点击>>> “CDA含金量” 了解CDA考试详情；

▷ 想获取CDA考试时间/费用/条件/大纲/通过率，点击 >>>“CDA考试官网” 了解CDA考试详情；

特征 表结构 数据分析

数据分析咨询请扫描二维码

上一篇图论在大数据分析中的作用！
下一篇CDA认证再升一档！与国家共同推进大数据人才培养标准教育事业！
CDA考试动态
CDA报考指南
热门栏目
最新资讯
更多
Copyright © 2015-present 北京国富如荷网络科技有限公司 All Rights Reserved.
京ICP备11001960号-9   京公网安备 11010802034615号   经营许可证编号：京B2-20210330
客服在线
立即咨询