二叉搜索树字符实现C++

Question

我正在尝试实现字符 BST。我无法理解插入字符的逻辑。所以假设这是在 main insert("a"); insert("b"); insert("c"); insert("d"); 什么时候 a 字母会小于 a ？那么我的树基本上都在右边吗？

像那样？因为永远不会有小于 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;
}

Answer 1

了解相同的数据可以多种方式存储在有效的二叉搜索树中。

像这样天真地构造二叉搜索树时，插入数据的顺序很重要。您发现的是您的插入算法有序数据会给您最坏的情况行为。尝试随机排列相同的字母，看看会得到什么。

这就是为什么二叉搜索树的实际实现在插入时使用更复杂的算法。 std::map<K,V> 的典型实现例如使用“red-black trees”，它仍然只是二叉搜索树，但插入和删除的方式是保证树不会最终变得过于不平衡，无论插入顺序。这些类型的数据结构称为“self-balancing 二叉搜索树”。

Answer 2

看起来奇怪的生成“树”可能感觉不对，但事实并非如此。您看到的是一棵 degenerate 二叉树，特别是已经转移到链表的二叉树。这是在没有重新平衡的情况下插入有序二叉树的惩罚。这也是平衡算法和 self-balancing 树存在的主要原因。没有它们，退化的条件就会浮出水面，这首先会消除拥有二叉树的所有辉煌：快速 O(logN) 搜索、插入和删除渐近复杂性。

例如，您的原始广告订单生成了这个：

显然这是下放给链表的。

但是现在，让我们再试一次，只是这一次，在每次插入之后，您检查以确保没有节点的 children 比 +1（或 -1）级别更不平衡。这是保持 AVL tree 平衡的一部分（但绝不是所有部分；它比您即将看到的要复杂得多）。我选择 AVL 来演示它只是因为它很容易理解。有了那个...

插入a

第一个节点a显然是微不足道的。它没有 children，所以 L/R 余额为 0/0，我们继续。

使用 b 插入，我们将有：

a
  \
    b

b为0/0，a节点为0/1，可以。现在插入 c

此时 b 的 L/R 余额为 0/1，但 a 的余额为 0/2。正是在这一点上会发生再平衡。对于这个微不足道的条件，left-rotation 大约 a 会发生。由

完成

分离 a 的权利 childb。
设置a的右child为原来的右child b的左child（其中有none, 所以...很简单。
将 b 的左侧 child 设置为 a
将之前指向 a 的人设置为现在指向 b。在这种情况下，这将是树的 'root' 指针。 IE。现在 b 是根。

结果如下所示：

   b
  / \
 a   c

太棒了。这太棒了。 a是0/0，b是1/1，c是0/0

插入d,

   b
  / \
 a   c
      \
       d

树仍然是“平衡的”，因为没有节点的 child 深度比其他节点 child 重 +1。具体来说，

a 是 0/0
b 是 1/2
c 是 0/1
d 是 0/0

哇哦。

继续这个例子，让我们看看当我们插入e时会发生什么。在重新平衡之前，它看起来像这样：

现在，从我们刚刚挂起 e 节点的地方向上工作：

e 是 0/0（显然）
d 是 0/1
c 是 0/2 <=== 检测到不平衡

停在那里片刻，我们看到我们应该向左旋转 c 就像我们之前对 a 所做的那样：

   b
  / \
 a   d
    / \
   c   e

现在我们的节点余额是：

a 是 0/0
b 是 1/2
c 是 0/0
d 是 1/1
e 是 0/0

没有节点在另一个 child 的任一方向上偏离 child-balance 超过 1。树是 once-again 平衡的。

作为最后一个例子，我们拿之前的树，这次再挂一个节点：f.

从 f 开始，我们看到：

f 是 0/0
e 是 0/1
d 是 1/2
b 是 1/3 <=== 检测到不平衡

哇哦。在我们再次做之前，我们已经完成了几次旋转机制：

分离 b 的权利 child d.
将 b 的右边 child 设置为原来的右边 child d 的左边 child c.
将 d 的左侧 child 设置为 b
将之前指向 b 的任何人设置为现在指向 d。在这种情况下，这将是树的 'root' 指针。 IE。现在 d 是根。

结果如下所示：

    d
   / \
  b   e
 / \   \  
a   c   f

最终平衡系数为：

a 是 0/0
b 是 1/1
c 是 0/0
d 是 2/2
e 是 0/1
f 是 0/0

有本书写了不同的树平衡机制。我在上面展示的示例在某种程度上使问题变得微不足道，但随着您继续学习树木以及保持树木高效的可用礼仪，这将很重要。有序标准容器（std::set、std::map 等）使用的常见 self-balancing 技术是 red-black trees。管理与我上面显示的有很大不同，但前提保持不变。保持任何单个树的深度（无论是整个树或整棵树中的任何 sub-tree）尽可能接近 logN 顺序，其中 N 是该树中包含的节点数。保持这一点是树可以提供的效率。

二叉搜索树字符实现C++

Binary search tree character implementation C++

c++

recursion

binary-search-tree