电竞比分网-中国电竞赛事及体育赛事平台

搜索
分享

二叉查找樹

 WUCANADA 2013-01-20

二叉查找樹

分類： 數(shù)據(jù)結(jié)構(gòu) 2012-10-11 07:25 208人閱讀 評(píng)論(0) 收藏 舉報(bào)

1.定義

二叉排序樹（Binary Sort Tree）又稱二叉查找樹。 它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹： （1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； （2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； （3）左、右子樹也分別為二叉排序樹；

2.節(jié)點(diǎn)結(jié)構(gòu)

2.1 擁有key值（排序）

2.2 擁有value值（實(shí)用）

2.3左子樹指針

2.4右子樹指針

2.5父親節(jié)點(diǎn)指針（刪除節(jié)點(diǎn)需要處理節(jié)點(diǎn)上界）

 

3.優(yōu)/缺點(diǎn)

假設(shè)一個(gè)BST是平衡的，那么CRUD一個(gè)元素的時(shí)間復(fù)雜度為 O(logN) 即為樹高。那么插入/刪除頻繁(很多動(dòng)態(tài)數(shù)據(jù))的處理性能會(huì)很好。

但是插入與刪除操作容易讓一棵樹不平衡：

插入：如果插入數(shù)據(jù)有序性較好，產(chǎn)生的樹將趨近于鏈表。 如 1,2,3,4,5  全部只有右節(jié)點(diǎn)。 只有當(dāng)插入很均勻的時(shí)候可能出現(xiàn)平衡（程序員不可控，后續(xù)文章會(huì)有平衡樹）

刪除：二叉查找樹一般的刪除策略（左右子節(jié)點(diǎn)都有的情況）是替換左子樹最大節(jié)點(diǎn)，或者右子樹最小節(jié)點(diǎn)。長期使用一種方式也會(huì)讓樹趨近鏈表。

 

4處理過程

插入：二分處理過程。相等則更新節(jié)點(diǎn)/不處理；小則往左走，大則往右走，直到發(fā)現(xiàn)一個(gè)空節(jié)點(diǎn)，創(chuàng)建并添加。添加一對(duì)指針關(guān)系：父親指向新節(jié)點(diǎn)/新節(jié)點(diǎn)指向父親。

查找：二分處理過程。

查找最大值：二分處理過程，不過一直往右走到底即可。

刪除：分情況：1.葉節(jié)點(diǎn)刪除，只考慮父節(jié)點(diǎn)對(duì)應(yīng)子指針。2.只有左/右子樹的節(jié)點(diǎn)刪除，把子樹往上“提”一層，類似于雙向鏈表刪除，考慮下刪除節(jié) 點(diǎn)是父親的左節(jié)點(diǎn)還是右節(jié)點(diǎn)。3.左右子樹都存在，找到左子樹最大值/右子樹最小值，與刪除節(jié)點(diǎn)進(jìn)行k,v交換，之后刪除找到的節(jié)點(diǎn)，即1,2的情況。

 

5.一個(gè)粗略的實(shí)現(xiàn)

  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4.   
  5. /////////////////////////////////////////////////////////////////////  
  6. //二叉查找樹(key,value都是int)  
  7. //性質(zhì)：  
  8. //1.按key有序二叉樹，如一個(gè)節(jié)點(diǎn)左小右大（等）==》中序遍歷可以順序輸出元素  
  9. //2.  
  10. struct BST_DATA{  
  11.     int key;  
  12.     int value;  
  13. };  
  14.   
  15. class BinarySearchTreeNode{  
  16. public:   
  17.     BinarySearchTreeNode(BST_DATA newdata)  
  18.     {  
  19.         key=newdata.key;  
  20.         value=newdata.value;  
  21.         left=NULL;  
  22.         right=NULL;  
  23.         parent=NULL;  
  24.     }  
  25. public:  
  26.     int key;  
  27.     int value;  
  28.     BinarySearchTreeNode * left;  
  29.     BinarySearchTreeNode * right;  
  30.     BinarySearchTreeNode * parent;  
  31. };  
  32.   
  33. ////////////////////////////////////////-----------普通插入，O(logN),樹高即可---------------------///////////////////////////////////  
  34. bool binarySearchTreeInsert(BinarySearchTreeNode ** ppNode, BST_DATA newdata,BinarySearchTreeNode *pParentNode)  
  35. {  
  36.     if(NULL == *ppNode){  
  37.         *ppNode= new BinarySearchTreeNode(newdata);  
  38.         (*ppNode)->parent=pParentNode;  
  39.         return true;  
  40.     }  
  41.   
  42.     if((newdata.key == (*ppNode)->key))//相等，不處理或更新，這里選擇更新  
  43.     {  
  44.         (*ppNode)->value=newdata.value;  
  45.         return true;  
  46.     }  
  47.     if((newdata.key < (*ppNode)->key))  
  48.     {  
  49.         return binarySearchTreeInsert( & ((*ppNode)->left), newdata, *ppNode );  
  50.     }  
  51.     else  
  52.     {  
  53.         return  binarySearchTreeInsert( & ((*ppNode)->right), newdata, *ppNode );  
  54.     }  
  55. }  
  56. //處理邊界+插入  
  57. bool insert(BinarySearchTreeNode ** ppNode, BST_DATA newdata){  
  58.     //結(jié)構(gòu)體不存在  
  59.     if(NULL==ppNode){return false;}  
  60.     //新節(jié)點(diǎn)作為根  
  61.     if(NULL==*ppNode){  
  62.         *ppNode= new BinarySearchTreeNode(newdata);  
  63.         return true;  
  64.     }  
  65.     //插入  
  66.     return binarySearchTreeInsert(ppNode, newdata,NULL);  
  67. }  
  68. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////  
  69.   
  70. ///////////////////////////////////////-----------遍歷，復(fù)雜度O(N),N為節(jié)點(diǎn)數(shù)--/////////////////////////////////  
  71. ///////////////-----------前序遍歷---------------------///////////////////////  
  72. void pre_scan(BinarySearchTreeNode ** ppNode){  
  73.     if(NULL!=ppNode && NULL !=*ppNode){  
  74.     //  printf("k%d-v%d#",(*ppNode)->key,(*ppNode)->value);  
  75.         printf("%d,",(*ppNode)->key);  
  76.         pre_scan(&((*ppNode)->left));  
  77.         pre_scan(&((*ppNode)->right));  
  78.     }  
  79. }  
  80. ///////////////-----------中序遍歷（按key順序）---------------------///////////////////////  
  81. void in_scan(BinarySearchTreeNode ** ppNode){  
  82.     if(NULL!=ppNode && NULL !=*ppNode){  
  83.         in_scan(&((*ppNode)->left));  
  84.     //  printf("k%d-v%d#",(*ppNode)->key,(*ppNode)->value);  
  85.         printf("%d,",(*ppNode)->key);  
  86.         in_scan(&((*ppNode)->right));  
  87.     }  
  88. }  
  89.   
  90.   
  91. ////////////////////////////////////////-----------查找(logN)---------------------///////////////////////////////////  
  92. //非遞歸  
  93. //根據(jù)data 查找  
  94. BinarySearchTreeNode * find_node(BinarySearchTreeNode ** ppNode,BST_DATA newdata)  
  95. {  
  96.     BinarySearchTreeNode * pHead = * ppNode;  
  97.     while(pHead!=NULL){  
  98.         if(pHead->key==newdata.key)  
  99.         {  
  100.             return pHead;  
  101.         }else if(pHead->key>newdata.key)  
  102.         {  
  103.             pHead=pHead->left;  
  104.         }else  
  105.         {  
  106.             pHead=pHead->right;  
  107.         }  
  108.     }  
  109.     return NULL;//未找到  
  110. }  
  111.   
  112. //查找最大節(jié)點(diǎn)  
  113. BinarySearchTreeNode * find_max_node(BinarySearchTreeNode ** ppNode)  
  114. {  
  115.     BinarySearchTreeNode * pHead = * ppNode;  
  116.     while(pHead->right!=NULL){pHead=pHead->right;}  
  117.     return pHead;  
  118. }  
  119.   
  120.   
  121. ///////////////-----------刪除所有O(N)---------------------///////////////////////  
  122. void delete_tree(BinarySearchTreeNode ** ppNode)  
  123. {  
  124.     if(NULL==ppNode || NULL==*ppNode){return ;}  
  125.     delete_tree(&((* ppNode)->left));  
  126.     delete_tree(&((* ppNode)->right));  
  127.     delete (*ppNode);  
  128. }  
  129. ///////////////-----------刪除一個(gè)****難點(diǎn)---------------------///////////////////////  
  130. //1.葉子節(jié)點(diǎn)刪除  
  131. //2.只有左子樹，或者右子樹，上移  
  132. //3.左子樹，右子樹都有***，替換左子樹最大值，或者右子樹最小值（問題，總是選擇左樹最大值，會(huì)讓左樹趨近直線，導(dǎo)致不平衡）  
  133.   
  134. bool delete_node_from_tree(BinarySearchTreeNode** ppNode, BST_DATA data)    
  135. {    
  136.       
  137.     if(NULL == ppNode || NULL == *ppNode) {return false;}//邊界  
  138.   
  139.     BinarySearchTreeNode *deleteNode = * ppNode;  
  140.     BinarySearchTreeNode * l_maxNode;  
  141.   
  142.     //確定刪除節(jié)點(diǎn)  
  143.     if(deleteNode->key==data.key)  
  144.     {  
  145.   
  146.         //1.左右都有，換左子樹最大值  
  147.         if(deleteNode->left!=NULL && deleteNode->right!=NULL)  
  148.         {  
  149.                 l_maxNode = find_max_node(&(deleteNode->left));  
  150.                 //////////////////////////////交換 a=a+b; b=a-b; a=a-b;  
  151.                 l_maxNode->key = l_maxNode->key + deleteNode->key;  
  152.                 deleteNode->key = l_maxNode->key - deleteNode->key;  
  153.                 l_maxNode->key = l_maxNode->key - deleteNode->key;  
  154.                 l_maxNode->value = l_maxNode->value + deleteNode->value;  
  155.                 deleteNode->value = l_maxNode->value - deleteNode->value;  
  156.                 l_maxNode->value = l_maxNode->value - deleteNode->value;  
  157.                 //////////////////////////////處理刪除節(jié)點(diǎn)下面  
  158.                 if(l_maxNode->parent->right==l_maxNode){  
  159.                         l_maxNode->parent->right=l_maxNode->left;  
  160.                 }else{//max父節(jié)點(diǎn)是根  
  161.                         l_maxNode->parent->left=l_maxNode->left;  
  162.                 }  
  163.                 //////////////////////////////處理刪除節(jié)點(diǎn)上面  
  164.                 if (NULL != l_maxNode->left) {   
  165.                     l_maxNode->left->parent = l_maxNode->parent;  
  166.                 }  
  167.   
  168.                 delete l_maxNode;  
  169.         }  
  170.         else{  
  171.             //2.只有左或右，上移  
  172.             //2.1只有左子樹  
  173.             if(deleteNode->left!=NULL)  
  174.             {  
  175.                 if(deleteNode->parent!=NULL)//不是根節(jié)點(diǎn)  
  176.                 {  
  177.                     //////////////////////////////處理刪除節(jié)點(diǎn)上面  
  178.                     if(deleteNode->parent->left==deleteNode)//是父親的左兒子  
  179.                     {  
  180.                         deleteNode->parent->left=deleteNode->left;  
  181.                     }else//右兒子  
  182.                     {  
  183.                         deleteNode->parent->right=deleteNode->left;  
  184.                     }  
  185.                 }  
  186.                 //////////////////////////////處理刪除節(jié)點(diǎn)下面  
  187.                 deleteNode->left->parent = deleteNode->parent;  
  188.             }  
  189.             //2.2只有右子樹  
  190.             else if(deleteNode->right!=NULL)  
  191.             {  
  192.                 if(deleteNode->parent!=NULL)  
  193.                 {  
  194.                     //////////////////////////////處理刪除節(jié)點(diǎn)上面  
  195.                     if(deleteNode->parent->left==deleteNode)  
  196.                     {  
  197.                         deleteNode->parent->left=deleteNode->right;  
  198.                     }else  
  199.                     {  
  200.                         deleteNode->parent->right=deleteNode->right;  
  201.                     }  
  202.                 }  
  203.                 //////////////////////////////處理刪除節(jié)點(diǎn)下面  
  204.                 deleteNode->right->parent = deleteNode->parent;  
  205.             }  
  206.             //3.左右都無  
  207.             else  
  208.             {  
  209.                 if(deleteNode->parent!=NULL)//不是根節(jié)點(diǎn)  
  210.                 {  
  211.                     //////////////////////////////處理刪除節(jié)點(diǎn)上面  
  212.                     if(deleteNode->parent->left==deleteNode)  
  213.                     {  
  214.                         deleteNode->parent->left=NULL;  
  215.                     }else  
  216.                     {  
  217.                         deleteNode->parent->right=NULL;  
  218.                     }  
  219.                 }  
  220.             }  
  221.       
  222.             delete deleteNode;  
  223.         }  
  224.         return true;  
  225.     }  
  226.     else if(deleteNode->key<data.key)  
  227.     {  
  228.         return delete_node_from_tree(&((*ppNode)->right),  data);    
  229.     }  
  230.     else  
  231.     {  
  232.         return delete_node_from_tree(&((*ppNode)->left),  data);   
  233.     }  
  234.   
  235.     return true;  
  236. }    
  237.   
  238. //////////////////////////////////////////////////////////////////////////////////////////////////////  
  239.   
  240. int main(void)  
  241. {  
  242.     int key_array[10] = {12,5,18,2,15,9,19,13,17,3}; //插入順序隨即（手動(dòng)）  
  243.     int value_array[10]={ 1,2, 3,4, 5,6, 7, 8, 9,10};  
  244.     BST_DATA bst_data_array[10]={0};  
  245.     for(int i=0;i<10;i++)  
  246.     {  
  247.         bst_data_array[i].key=key_array[i];  
  248.         bst_data_array[i].value=value_array[i];  
  249.     }  
  250.   
  251.     BinarySearchTreeNode * ppNode=NULL;  
  252.     for(int j=0;j<10;j++){  
  253.         insert(&ppNode, bst_data_array[j]);  
  254.     }  
  255.   
  256.   
  257.     pre_scan(&ppNode);  
  258.     printf("\n");  
  259.     in_scan(&ppNode);  
  260.     printf("\n");  
  261.       
  262.     BST_DATA td;  
  263.     td.key=1;  
  264.     td.value=2;  
  265.   
  266.     /* 
  267.     //測試find_node 
  268.     BinarySearchTreeNode * node =find_node(&ppNode,bst_data_array[3]); 
  269.     if(NULL!=node){printf("\nx %d\n ",node->key);} 
  270.     in_scan(&ppNode); 
  271.         printf("\n"); 
  272.     */  
  273.     /* 
  274.     //測試find_max_node 
  275.     BinarySearchTreeNode * node1 =  find_max_node(&ppNode); 
  276.     if(NULL!=node1){printf("\nx %d\n ",node1->key);} 
  277.     in_scan(&ppNode); 
  278.         printf("\n"); 
  279.     */  
  280.   
  281.   
  282.     //測試刪除delete_node_from_tree  
  283.     delete_node_from_tree(&ppNode,bst_data_array[1]);  
  284.     pre_scan(&ppNode);  
  285.     printf("\n");  
  286.     delete_tree(&ppNode);  
  287.    return 0;  
  288. }

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多