你好,游客 登录 注册 搜索
背景:
阅读新闻

算法导论------二叉搜索树

[日期:2014-12-05] 来源:CSDN博客  作者:chenxun2009 [字体: ]

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

 

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

    二叉查找树的概念及操作。主要内容包括二叉查找树的性质,如何在二叉查找树 中查找最大值、最小值和给定的值,如何找出某一个元素的前驱和后继,如何在二叉查找树中进行插入和删除操作。在二叉查找树上执行这些基本操作的时间与树的 高度成正比,一棵随机构造的二叉查找树的期望高度为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. public
  4.     T elem; 
  5.     BinarySearchTreeNode<T> *parent; 
  6.     BinarySearchTreeNode<T> *left; 
  7.     BinarySearchTreeNode<T> *right; 
  8. }; 
  9.  
  10. template<class T> 
  11. class BinarySearchTree 
  12. public
  13.     BinarySearchTree(); 
  14.     void tree_insert(const T& elem); 
  15.     int tree_remove(const T& elem); 
  16.     BinarySearchTreeNode<T> *tree_search(const T& elem) const
  17.     T tree_minmum(BinarySearchTreeNode<T>* root) const
  18.     T tree_maxmum(BinarySearchTreeNode<T>* root) const
  19.     T tree_successor(const T& elem) const
  20.     T tree_predecessor(const T& elem) const
  21.     int empty() const
  22.     void inorder_tree_walk() const
  23.     BinarySearchTreeNode<T>* get_root() { return root; } 
  24.  
  25. private
  26.     BinarySearchTreeNode<T>* root; 
  27. }; 


 完整程序如下所示:

 

[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. public
  13.     T elem; 
  14.     BinarySearchTreeNode<T> *parent; 
  15.     BinarySearchTreeNode<T> *left; 
  16.     BinarySearchTreeNode<T> *right; 
  17. }; 
  18.  
  19. template<class T> 
  20. class BinarySearchTree 
  21. public
  22.     BinarySearchTree(); 
  23.     void tree_insert(const T& elem); 
  24.     int tree_remove(const T& elem); 
  25.     BinarySearchTreeNode<T> *tree_search(const T& elem) const
  26.     T tree_minmum(BinarySearchTreeNode<T>* root) const
  27.     T tree_maxmum(BinarySearchTreeNode<T>* root) const
  28.     T tree_successor(const T& elem) const
  29.     T tree_predecessor(const T& elem) const
  30.     int empty() const
  31.     void inorder_tree_walk() const
  32.     BinarySearchTreeNode<T>* get_root() { return root; } 
  33.  
  34. private
  35.     BinarySearchTreeNode<T>* root; 
  36. }; 
  37.  
  38. //构造函数,初始化二叉查找树。 
  39. template <class T> 
  40. BinarySearchTree<T>::BinarySearchTree() 
  41.     root = NULL; 
  42.  
  43.  
  44. template <class T> 
  45. void BinarySearchTree<T>::tree_insert(const T& elem) 
  46.     if (!empty()) 
  47.     { 
  48.         BinarySearchTreeNode<T> *p_node = root; 
  49.         BinarySearchTreeNode<T> *q_node = NULL; 
  50.         BinarySearchTreeNode<T> *new_node = new BinarySearchTreeNode<T>; 
  51.  
  52.         new_node->elem = elem; 
  53.         new_node->left = NULL; 
  54.         new_node->right = NULL; 
  55.         new_node->parent = NULL; 
  56.  
  57.         while (p_node) 
  58.         { 
  59.             q_node = p_node; 
  60.             if (p_node->elem > elem) 
  61.                 p_node = p_node->left; 
  62.             else 
  63.                 p_node = p_node->right; 
  64.         }//当p_node为空的时候,q_node正好是正确的插入位置的父节点,且q_node是叶节点. 
  65.  
  66.         if (q_node->elem > elem) 
  67.             q_node->left = new_node; 
  68.         else 
  69.             q_node->right = new_node; 
  70.         new_node->parent = q_node; 
  71.     } 
  72.     else 
  73.     { 
  74.         root = new BinarySearchTreeNode<T>; 
  75.         root->elem = elem; 
  76.         root->parent = NULL; 
  77.         root->left = NULL; 
  78.         root->right = NULL; 
  79.     } 
  80.  
  81. //二叉查找树节点的删除 
  82. template <class T> 
  83. int BinarySearchTree<T>::tree_remove(const T& elem) 
  84.     BinarySearchTreeNode<T> *z = tree_search(elem); 
  85.     BinarySearchTreeNode<T> *x, *y; 
  86.  
  87.     if (z != NULL) 
  88.     { 
  89.         //用y来表示实际要删除的节点 
  90.         if (z->left == NULL || z->right == NULL)//最多只有一个儿子节,要么没有儿子节点 
  91.             y = z; 
  92.         else 
  93.             y = tree_search(tree_successor(elem));//有两个儿子的时候实际删除的是后继节点 
  94.  
  95.         //因为有上面的if语句,所以y要么只有一个儿子,要么没有儿子。后继节点只有右儿子或者没有儿子 
  96.         //所以x要么是儿子节点,要么是空节点 
  97.         if (y->left != NULL) 
  98.             x = y->left; 
  99.         else 
  100.             x = y->right; 
  101.  
  102.         if (x != NULL) 
  103.             x->parent = y->parent; 
  104.  
  105.         if (y->parent == NULL) 
  106.             root = x; 
  107.         else if (y == y->parent->left) 
  108.             y->parent->left = x; 
  109.         else 
  110.             y->parent->right = x; 
  111.  
  112.         //处理后继节点的情况,因为y表示后继的时候y!=z; 
  113.         if (y != z) 
  114.             z->elem = y->elem; 
  115.         delete y; 
  116.     } 
  117.  
  118.     return -1; 
  119.  
  120.  
  121. //  BinarySearchTreeNode<T>* 返回类型,返回查找元素elem的节点 
  122. template <class T> 
  123. BinarySearchTreeNode<T>* BinarySearchTree<T>::tree_search(const T& elem) const 
  124.     BinarySearchTreeNode<T> *pnode = root; 
  125.     while (pnode) 
  126.     { 
  127.         if (pnode->elem == elem) 
  128.             break
  129.         else if (pnode->elem > elem) 
  130.             pnode = pnode->left; 
  131.         else 
  132.             pnode = pnode->right; 
  133.     } 
  134.  
  135.     return pnode; 
  136.  
  137. //返回最小关键字的元素,可以参考书上用递归方法的写 
  138. template <class T> 
  139. T BinarySearchTree<T>::tree_minmum(BinarySearchTreeNode<T>* root) const 
  140.     BinarySearchTreeNode<T> *pnode = root; 
  141.      
  142.     while (pnode->left) 
  143.         pnode = pnode->left; 
  144.     return pnode->elem; 
  145.  
  146. //返回最大关键字的元素,可以改用递归,不过效率降低 
  147. template <class T> 
  148. T BinarySearchTree<T>::tree_maxmum(BinarySearchTreeNode<T>* root) const 
  149.     BinarySearchTreeNode<T> *pnode = root; 
  150.  
  151.     while (pnode->right != NULL) 
  152.         pnode = pnode->right; 
  153.  
  154.     return pnode->elem; 
  155.  
  156.  
  157. //后继节点 
  158. template <class T> 
  159. T BinarySearchTree<T>::tree_successor(const T& elem) const 
  160.     BinarySearchTreeNode<T>* pnode = tree_search(elem); 
  161.     BinarySearchTreeNode<T>* parentnode; 
  162.     if (pnode != NULL) 
  163.     { 
  164.         if (pnode->right) 
  165.             return tree_minmum(pnode->right); 
  166.         parentnode = pnode->parent; 
  167.         while (parentnode && pnode == parentnode->right) 
  168.         { 
  169.             pnode = parentnode; 
  170.             parentnode = parentnode->parent; 
  171.         } 
  172.         if (parentnode) 
  173.             return parentnode->elem; 
  174.         else 
  175.             return T(); 
  176.     } 
  177.     return T(); 
  178.  
  179. //前继节点 
  180. template <class T> 
  181. T BinarySearchTree<T>::tree_predecessor(const T& elem)const 
  182.     BinarySearchTreeNode<T>* pnode = tree_search(elem); 
  183.     BinarySearchTreeNode<T>* parentnode; 
  184.     if (pnode != NULL) 
  185.     { 
  186.         if (pnode->right) 
  187.             return tree_maxmum(pnode->right); 
  188.         parentnode = pnode->parent; 
  189.         while (parentnode && pnode == parentnode->left) 
  190.         { 
  191.             pnode = parentnode; 
  192.             parentnode = pnode->parent; 
  193.         } 
  194.         if (parentnode) 
  195.             return parentnode->elem; 
  196.         else 
  197.             return T(); 
  198.     } 
  199.     return T(); 
  200.  
  201. template <class T> 
  202. int BinarySearchTree<T>::empty() const 
  203.     return (NULL == root); 
  204.  
  205.  
  206. //按照大小顺序输出二叉查找树,即中根遍历的方法输出二叉查找树.使用stack功能的实现。 
  207. template <class T> 
  208. void BinarySearchTree<T>::inorder_tree_walk() const 
  209.     if (NULL != root) 
  210.     { 
  211.         stack<BinarySearchTreeNode<T>*> s; 
  212.         BinarySearchTreeNode<T> *P_temp; 
  213.         P_temp = root; 
  214.         while (NULL != P_temp || !s.empty()) 
  215.         { 
  216.             if (NULL != P_temp) 
  217.             { 
  218.                 s.push(P_temp); 
  219.                 P_temp = P_temp->left; 
  220.             } 
  221.             else 
  222.             { 
  223.                 P_temp = s.top(); 
  224.                 s.pop(); 
  225.                 cout << P_temp->elem << " "
  226.                 P_temp = P_temp->right; 
  227.             } 
  228.         } 
  229.     } 
  230.  
  231. int main() 
  232.     BinarySearchTree<int> bstree; 
  233.     BinarySearchTreeNode<int>* ptnode, *proot; 
  234.     bstree.tree_insert(32); 
  235.     bstree.tree_insert(21); 
  236.     bstree.tree_insert(46); 
  237.     bstree.tree_insert(54); 
  238.     bstree.tree_insert(16); 
  239.     bstree.tree_insert(38); 
  240.     bstree.tree_insert(70); 
  241.     cout << "inorder tree walk is: "
  242.     bstree.inorder_tree_walk(); 
  243.     proot = bstree.get_root(); 
  244.     cout << "\nmax value is: " << bstree.tree_maxmum(proot) << endl; 
  245.     cout << "min value is: " << bstree.tree_minmum(proot) << endl; 
  246.     ptnode = bstree.tree_search(38); 
  247.     if (ptnode) 
  248.         cout << "the element 38 is exist in the binary tree.\n"
  249.     else 
  250.         cout << "the element 38 is not exist in the binary tree.\n"
  251.     cout << "the successor of 38 is: " << bstree.tree_successor(38) << endl; 
  252.     cout << "the predecessor of 38 is:" << bstree.tree_predecessor(38) << endl; 
  253.     if (bstree.tree_remove(46) == 0) 
  254.         cout << "delete 46 successfully" << endl; 
  255.     else 
  256.         cout << "delete 46 failed" << endl; 
  257.     cout << "inorder tree walk is: "
  258.     bstree.inorder_tree_walk(); 
  259.     exit(0); 

程序测试结果如下所示:

    二叉查找上各种基本操作的运行时间都是O(h),h为树的高度。但是在元素插入和删除过程中,树的高度会发生改变。如果n个元素按照严格增长的顺序插入, 那个构造出的二叉查找树的高度为n-1。例如按照先后顺序插入7、15、18、20、34、46、59元素构造二叉查找树,二叉查找树结构如下所示:

原文链接:http://blog.csdn.net/chenxun_2010/article/details/41709801





收藏 推荐 打印 | 录入:Cstor | 阅读:
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款