熱線電話：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考試詳情；

特征 表結構 數據分析

數據分析咨詢請掃描二維碼

若不方便掃碼，搜微信號：CDAshujufenxi

上一篇圖論在大數據分析中的作用！
下一篇CDA認證再升一檔！與國家共同推進大數據人才培養標準教育事業！
數據分析師考試動態
CDA報考指南
數據分析學習
數據分析師資訊
更多

CDA教育閉環

常見問題

關于我們

CDA數據分析師公眾號

  • CDA數據分析師公眾號

CDA考試中心小程序

  • CDA考試中心服務號

CDA數據分析師App下載

  • CDA數據分析師App下載
Copyright © 2015-2021, www.ruiqisteel.com All Rights Reserved. CDA數據分析師(北京國富如荷網絡科技有限公司) 版權所有 京ICP備11001960號-9 京公網安備 11010802034615號 經營許可證編號：京B2-20210330
聯系電話：13321103290 (微信同號)

OK
客服在線
立即咨詢
日韩人妻系列无码专区视频,先锋高清无码,无码免费视欧非,国精产品一区一区三区无码
客服在線
立即咨詢