99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話：13121318867

登錄
首頁精彩閱讀算法導論_二叉搜索樹_數(shù)據(jù)分析師
算法導論_二叉搜索樹_數(shù)據(jù)分析師
2014-12-10
收藏

算法導論_二叉搜索樹_數(shù)據(jù)分析師

先上二叉樹查找樹的刪除的代碼，因為刪除是二叉查找樹最復雜的操作：

 

[cpp] view plaincopy
  1. int BinarySearchTree<T>::tree_remove(const T& elem) 
  2. { 
  3.     BinarySearchTreeNode<T> *z = tree_search(elem);//根據(jù)元素查找到要刪除的節(jié)點 
  4.     BinarySearchTreeNode<T> *x, *y; 
  5.  
  6.     if (z != NULL) 
  7.     { 
  8.         //用y來表示實際要刪除的節(jié)點 
  9.         if (z->left == NULL || z->right == NULL)//最多只有一個兒子節(jié)，要么沒有兒子節(jié)點 
  10.             y = z; 
  11.         else 
  12.             y = tree_search(tree_successor(elem));//有兩個兒子的時候?qū)嶋H刪除的是后繼節(jié)點 
  13.  
  14.         //因為有上面的if語句，所以y要么只有一個兒子，要么沒有兒子。后繼節(jié)點只有右兒子或者沒有兒子 
  15.         //所以x要么是兒子節(jié)點，要么是空節(jié)點 
  16.         if (y->left != NULL) 
  17.             x = y->left; 
  18.         else 
  19.             x = y->right; 
  20.  
  21.         if (x != NULL)//判斷y節(jié)點有沒有兒子節(jié)點，有的花就把y節(jié)點的父節(jié)點變成x的父節(jié)點。 
  22.             x->parent = y->parent; 
  23.  
  24.         //y是根節(jié)點或者不是根節(jié)點的情況 
  25.         if (y->parent == NULL) 
  26.             root = x; 
  27.         else if (y == y->parent->left)//如果y節(jié)點不是根節(jié)點的情況該怎么處理呢？ 
  28.             y->parent->left = x; 
  29.         else 
  30.             y->parent->right = x; 
  31.  
  32.         //處理后繼節(jié)點的情況，因為y表示后繼的時候y！=z； 
  33.         if (y != z) 
  34.             z->elem = y->elem; 
  35.         delete y; 
  36.     } 
  37.  
  38.     return -1; 
  39. } 

    二叉查找樹的概念及操作。主要內(nèi)容包括二叉查找樹的性質(zhì)，如何在二叉查找樹 中查找最大值、最小值和給定的值，如何找出某一個元素的前驅(qū)和后繼，如何在二叉查找樹中進行插入和刪除操作。在二叉查找樹上執(zhí)行這些基本操作的時間與樹的 高度成正比，一棵隨機構(gòu)造的二叉查找樹的期望高度為O(lgn)，從而基本動態(tài)集合的操作平均時間為θ(lgn)。

1、二叉查找樹

　　二叉查找樹是按照二叉樹結(jié)構(gòu)來組織的，因此可以用二叉鏈表結(jié)構(gòu)表示。二叉查找樹中的關(guān)鍵字的存儲方式滿足的特征是：設x為二叉查找樹中的一個結(jié)點。如果y是x的左子樹中的一個結(jié)點，則key[y]≤key[x]。如果y是x的右子樹中的一個結(jié)點，則key[x]≤key[y]。根據(jù)二叉查找樹的特征可知，采用中根遍歷一棵二叉查找樹，可以得到樹中關(guān)鍵字有小到大的序列。

一棵二叉樹查找及其中根遍歷結(jié)果如下圖所示：

    書中給出了一個定理：如果x是一棵包含n個結(jié)點的子樹的根，則其中根遍歷運行時間為θ(n)。

    問題：二叉查找樹性質(zhì)與最小堆之間有什么區(qū)別？能否利用最小堆的性質(zhì)在O(n)時間內(nèi)，按序輸出含有n個結(jié)點的樹中的所有關(guān)鍵字？

2、查詢二叉查找樹

　　二叉查找樹中最常見的操作是查找樹中的某個關(guān)鍵字，除了基本的查詢，還支持最大值、最小值、前驅(qū)和后繼查詢操作，書中就每種查詢進行了詳細的講解。

（1）查找SEARCH

　　在二叉查找樹中查找一個給定的關(guān)鍵字k的過程與二分查找很類似，根據(jù)二叉查找樹在的關(guān)鍵字存放的特征，很容易得出查找過程：首先是關(guān)鍵字k與樹根的關(guān) 鍵字進行比較，如果k大比根的關(guān)鍵字大，則在根的右子樹中查找，否則在根的左子樹中查找，重復此過程，直到找到與遇到空結(jié)點為止。例如下圖所示的查找關(guān)鍵 字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）查找最大關(guān)鍵字和最小關(guān)鍵字

　　根據(jù)二叉查找樹的特征，很容易查找出最大和最小關(guān)鍵字。查找二叉樹中的最小關(guān)鍵字：從根結(jié)點開始，沿著各個節(jié)點的left指針查找下去，直到遇到 NULL時結(jié)束。如果一個結(jié)點x無左子樹，則以x為根的子樹中，最小關(guān)鍵字就是key[x]。查找二叉樹中的最大關(guān)鍵字：從根結(jié)點開始，沿著各個結(jié)點的 right指針查找下去，直到遇到NULL時結(jié)束。書中給出了查找最大最小關(guān)鍵字的偽代碼：

 

[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）前驅(qū)和后繼

　　給定一個二叉查找樹中的結(jié)點，找出在中序遍歷順序下某個節(jié)點的前驅(qū)和后繼。如果樹中所有關(guān)鍵字都不相同，則某一結(jié)點x的前驅(qū)就是小于key[x]的所 有關(guān)鍵字中最大的那個結(jié)點，后繼即是大于key[x]中的所有關(guān)鍵字中最小的那個結(jié)點。根據(jù)二叉查找樹的結(jié)構(gòu)和性質(zhì)，不用對關(guān)鍵字做任何比較，就可以找到 某個結(jié)點的前驅(qū)和后繼。

　　查找前驅(qū)步驟：先判斷x是否有左子樹，如果有則在left[x]中查找關(guān)鍵字最大的結(jié)點，即是x的前驅(qū)。如果沒有左子樹，則從x繼續(xù)向上執(zhí)行此操作，直到遇到某個結(jié)點是其父節(jié)點的右孩子結(jié)點。例如下圖查找結(jié)點7的前驅(qū)結(jié)點6過程：

　　查找后繼步驟：先判斷x是否有右子樹，如果有則在right[x]中查找關(guān)鍵字最小的結(jié)點，即使x的后繼。如果沒有右子樹，則從x的父節(jié)點開始向上查找，直到遇到某個結(jié)點是其父結(jié)點的左兒子的結(jié)點時為止。例如下圖查找結(jié)點13的后繼結(jié)點15的過程：

    書中給出了求x結(jié)點后繼結(jié)點的偽代碼:

 

[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的二叉查找，動態(tài)集合操作SEARCH、MINMUM、MAXMUM、SUCCESSOR、PROCESSOR等的運行時間均為O(h)。

3、插入和刪除

　　插入和刪除會引起二叉查找表示的動態(tài)集合的變化，難點在在插入和刪除的過程中要保持二叉查找樹的性質(zhì)。插入過程相當來說要簡單一些，刪除結(jié)點比較復雜。

（1）插入

　　插入結(jié)點的位置對應著查找過程中查找不成功時候的結(jié)點位置，因此需要從根結(jié)點開始查找?guī)Р迦虢Y(jié)點位置，找到位置后插入即可。下圖所示插入結(jié)點過程：

    書中給出了插入過程的偽代碼：

 

[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）刪除

　　從二叉查找樹中刪除給定的結(jié)點z，分三種情況討論：

<1>結(jié)點z沒有左右子樹，則修改其父節(jié)點p[z]，使其為NULL。刪除過程如下圖所示：

<2>如果結(jié)點z只有一個子樹（左子樹或者右子樹），通過在其子結(jié)點與父節(jié)點建立一條鏈來刪除z。刪除過程如下圖所示：

<3>如果z有兩個子女，則先刪除z的后繼y（y沒有左孩子），在用y的內(nèi)容來替代z的內(nèi)容。

書中給出了刪除過程的偽代碼：

 

[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的二叉查找樹，動態(tài)集合操作INSERT和DELETE的運行時間為O(h)。

4、實現(xiàn)測試

　　采用C++語言實現(xiàn)一個簡單的二叉查找樹，支持動態(tài)集合的基本操作：search、minmum、maxmum、predecessor、successor、insert和delete。設計的二叉查找樹結(jié)構(gòu)如下所示：

 

[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++語言實現(xiàn)一個簡單的二叉查找樹，支持動態(tài)集合的基本操作：                                      */ 
  7. /*search、minmum、maxmum、predecessor、successor、insert和delete。設計的二叉查找樹結(jié)構(gòu)如下所示：    */ 
  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. //構(gòu)造函數(shù)，初始化二叉查找樹。 
  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正好是正確的插入位置的父節(jié)點，且q_node是葉節(jié)點. 
  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. //二叉查找樹節(jié)點的刪除 
  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來表示實際要刪除的節(jié)點 
  97.         if (z->left == NULL || z->right == NULL)//最多只有一個兒子節(jié)，要么沒有兒子節(jié)點 
  98.             y = z; 
  99.         else 
  100.             y = tree_search(tree_successor(elem));//有兩個兒子的時候?qū)嶋H刪除的是后繼節(jié)點 
  101.  
  102.         //因為有上面的if語句，所以y要么只有一個兒子，要么沒有兒子。后繼節(jié)點只有右兒子或者沒有兒子 
  103.         //所以x要么是兒子節(jié)點，要么是空節(jié)點 
  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

數(shù)據(jù)分析咨詢請掃描二維碼

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

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進行初始化 // 參數(shù)1：配置參數(shù) // 參數(shù)2：回調(diào)，回調(diào)的第一個參數(shù)驗證碼對象，之后可以使用它調(diào)用相應的接口 initGeetest({ // 以下 4 個配置參數(shù)為必須，不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺檢測極驗服務器是否宕機 new_captcha: data.new_captcha, // 用于宕機時表示是新驗證碼的宕機 product: "float", // 產(chǎn)品形式，包括：float，popup width: "280px", https: true // 更多配置參數(shù)說明請參見：http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計時完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請輸入'+oInput.attr('placeholder')+'！'; var errTxt = '請輸入正確的'+oInput.attr('placeholder')+'！'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }