二叉搜索樹字符實作C

我正在嘗試實作一個字符 BST。我無法理解插入字符的邏輯。所以讓我們說這是 maininsert("a"); insert("b"); insert("c"); insert("d"); 什么時候 a 字母會小于 a ？那么我的樹基本上都在右側嗎？

      a
        \
          b
            \
              c
                \
                  d

像那樣 ？因為永遠不會有小于 a 的字母。但這感覺不對，但我不確定我錯過了什么。

我的插入功能：

void insert(char letter, node * curr)
{
   int count{0};                                                                                                                                                                                                                                                                                             
   if ( strcmp(curr->getLetter(), letter) == 0)                                                                                                                 
       return 0;           
                                                                                                                                                                                                                                                                                  
   if (!curr->getRight() && strcmp(curr->getLetter(), letter) > 0)                                                                                          
   {                                                                                                                                                        
       curr->getRight() = new node(letter);                                                                                                                   
       return 1;                                                                                                                                        
   }                                                                                                                                                                                                                                                                                                         
   if (!curr->getLeft() && strcmp(curr->getLetter(), letter) < 0)                                                                                           
   {                                                                                                                                                        
      curr->getLeft() = new node(letter);                                                                                                                    
      return 1;                                                                                                                                        
   }                                                                                                                                                                                                                                                                                                         
   if (strcmp(letter, curr->getLetter() ) < 0)                                                                                                                  
      count  = insert(letter, curr->getLeft() );                                                                                                                                                                                                                                                              
   else                                                                                                                                                     
      count  = insert(letter, curr->getRight() );                                                                                                                                                                                                                                                             
      
   return count;
}

uj5u.com熱心網友回復：

奇怪的生成的“樹”可能感覺不對，但事實并非如此。你看到的是一棵退化的二叉樹，特別是一個已經轉移到鏈表的二叉樹。這是在沒有重新平衡的情況下插入有序二叉樹的懲罰。這也是平衡演算法和自平衡樹存在的主要原因。沒有它們，退化的條件就會浮出水面，這首先消除了擁有二叉樹的所有優點：快速 O(logN) 搜索、插入和洗掉漸近復雜性。

例如，您的原始廣告訂單生成了以下內容：

a
  \
    b
      \
        c
          \
            d

顯然，這被轉移到了一個鏈表。

但是現在，讓我們再試一次，只是這一次，在每次插入之后，您檢查以確保沒有節點的子節點的不平衡程度超過 1（或 -1）級別。這是保持AVL 樹平衡的一部分（但絕不是所有部分；它比您將要看到的要復雜得多）。我選擇 AVL 來演示這一點僅僅是因為它很容易理解。接著就，隨即...

插入a

a

第一個節點a顯然是微不足道的。它沒有孩子，所以 L/R 余額為 0/0，我們繼續。

通過b插入，我們將擁有：

a
  \
    b

b是0/0，a節點是0/1，沒關系。現在插入c

a
  \
    b
      \
        c

At this point b has a L/R balance of 0/1, but a has a balance of 0/2. It is at this point a rebalance would happen. For this trivial condition a left-rotation about a would transpire. It is done by

1. Detaching a's right childb.
2. Setting a's right child to it's former right child b's left child (of which there is none, so... simple enough.
3. Setting b's left child to be a
4. Set whomever was pointing to a to now point to b. In this case that would be whatever was the 'root' pointer of the tree. I.e. now b is the root.

The result looks like this:

   b
  / \
 a   c

Terrific. This is awesome. a is 0/0, b is 1/1, and c is 0/0

Insert d,

   b
  / \
 a   c
      \
       d

The tree is still "balanced", in that no node has a child depth heavier than 1 over its other child. Specifically,

• a is 0/0
• b is 1/2
• c is 0/1
• d is 0/0

Whoopee.

Continuing this example, let us see what happens when we insert e. Before rebalancing, it would look like this:

   b
  / \
 a   c
      \
       d
        \
         e

Now, working up from where we just hung that e node:

• e is 0/0 (obviously)
• d is 0/1
• c is 0/2 <=== imbalance detected

Stopping there for a moment, we see we should do left rotation about c like we did earlier about a:

   b
  / \
 a   d
    / \
   c   e

Now our node balances are:

• a is 0/0
• b is 1/2
• c is 0/0
• d is 1/1
• e is 0/0

No node has a child-balance off by more than 1 in either direction of the other child. the tree is once-again balanced.

As a final example, we take the tree we had before, and this time hang one more node: f.

   b
  / \
 a   d
    / \
   c   e
        \
         f

Working our way up from f we see that:

• f is 0/0
• e is 0/1
• d is 1/2
• b is 1/3 <=== imbalance detected

Whoa. Following the rotation mechanics we'v done several times before we do it again:

1. Detaching b's right child d.
2. Setting b's right child to its former right child d's left child c.
3. Setting d's left child to be b
4. Set whomever was pointing to b to now point to d. In this case that would be whatever was the 'root' pointer of the tree. I.e. now d is the root.

The result looks like this:

    d
   / \
  b   e
 / \   \  
a   c   f

The final balance factors are:

• a is 0/0
• b is 1/1
• c is 0/0
• d is 2/2
• e is 0/1
• f is 0/0

There are books written on different tree balancing mechanics. The example I've shown above somewhat trivializes the matter, but it will be important as you continuing learning about trees, and the manners available to keep them efficient. A common self-balancing technique used by ordered standard containers (std::set, std::map, etc.) are red-black trees. The management is considerably different than what I've shown above, but the premise remains the same. Keep any single tree depth (be it the whole tree, or any sub-tree within the whole tree) to be as close to logN order, where N is the number of nodes contained in that tree. Maintaining that is what provides the efficiencies trees can offer.

uj5u.com熱心網友回復：

了解相同的資料可以通過多種方式存盤在有效的二叉搜索樹中。

當像這樣天真地構建二叉搜索樹時，插入資料的順序很重要。您發現的是，對于您的插入演算法，有序資料會為您提供最壞情況下的行為。嘗試隨機排列相同的字母，看看你會得到什么。

這就是為什么當您插入二叉搜索樹時，實際實作會使用更復雜的演算法。例如，典型的實作std::map<K,V>使用“紅黑樹”，它仍然只是二叉搜索樹，但插入和洗掉是以這樣一種方式完成的，即無論插入順序如何，都可以保證樹不會過于不平衡。這些型別的資料結構被稱為“自平衡二叉搜索樹”。

標籤：C 递归 二叉搜索树

上一篇：在Python中，您可以將兩個引數傳遞給一個函式，其中一個引數是從另一個引數推斷出來的嗎？

下一篇：使用遞回的數字的每個磁區