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

Question

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

3

我正在尝试实现一个字符二叉搜索树。我无法理解插入字符的逻辑。假设这段代码在主函数中：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;
}

- Ahmad Safa

为什么是错的？如果你的比较逻辑是字符优先级，那么这就是正确的顺序。如果你有像1、2、3、4这样的数字而不是字符，那么你的树也会像这样。 - Ezio

strcmp works on strings (char*), not single chars. To compare chars use simply < or >: curr->getLetter() < letter. Or, if you really want to do three way comparison, C++20 has spaceship operator: curr->getLetter() <=> letter < 0 - Yksisarvinen

@Yksisarvinen 我最初是使用了一个完整的单词，所以我使用了 char *。但为了简单起见，我将其切换为 char。无论如何还是谢谢！ - Ahmad Safa

2个回答

1

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

在像这样天真地构建二叉搜索树时，插入数据的顺序很重要。你已经发现，对于你的插入算法，有序数据会导致最坏情况的行为。尝试一下相同字母的随机顺序，看看会发生什么。

这就是为什么实际的二叉搜索树实现在插入时使用更复杂的算法的原因。例如，std::map<K,V> 的典型实现使用 "red-black trees"，它们仍然只是二叉搜索树，但插入和删除是以一种保证树不会过于倾斜的方式进行的，无论插入顺序如何。这些类型的数据结构被称为“自平衡二叉搜索树”。

- jwezorek

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- WhozCraig · Accepted Answer

这棵看起来奇怪的生成的“树”可能感觉不对，但其实并不是。你看到的是一棵退化的二叉树，具体来说，它已经变成了一个链表。这就是在有序二叉树中进行插入操作而没有重新平衡的代价。这也是为什么平衡算法和自平衡树存在的主要原因。如果没有它们，就会出现退化情况，而丧失了二叉树本身快速的O(logN)搜索、插入和删除渐近复杂度的优点。

例如，你原始插入顺序生成了这个：

显然，这是一个链表。

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

插入a

第一个节点a显然是微不足道的。它没有子节点，因此L/R平衡为0/0，我们继续。

插入b后，我们将会有：

a
  \
    b

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

在这一点上，b的L/R平衡为0/1，但是a的平衡为0/2。在这一点上，将进行重新平衡。对于这个简单的情况，将围绕a左旋转。步骤如下：

分离a的右子节点b。
将a的右子节点设置为其以前的右子节点b的左子节点（没有左子节点，所以......够简单）。
将b的左子节点设置为a
将原本指向a的任何人，现在指向b。在这种情况下，这将是树的“根”指针。也就是说，现在b成为了根。

结果看起来像这样：

   b
  / \
 a   c

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

插入d，

   b
  / \
 a   c
      \
       d

树仍然是“平衡的”，也就是说没有任何一个节点的子节点深度比其它子节点深度大+1。具体来说：

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

继续上面的例子，现在我们插入 e，在重新平衡之前，树的状态如下：

现在，从我们刚刚挂上e节点的位置向上工作:

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

暂停一下，我们看到应该像之前关于a所做的那样对c进行左旋转:

   b
  / \
 a   d
    / \
   c   e

现在我们的节点平衡情况如下：

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

没有节点的子平衡超过另一个子方向的1个以上。树再次达到平衡状态。

最后一个例子，我们取之前的树，并这次增加一个节点：f。

从 f 开始，我们发现：

f 是 0/0
e 是 0/1
d 是 1/2
b 是 1/3 <=== 发现不平衡

哇。根据旋转机制，我们再进行以下步骤：

分离 b 的右子节点 d。
将 b 的右子节点设置为它以前的右子节点 d 的左子节点 c。
将 d 的左子节点设置为 b
将原来指向 b 的指针改为指向 d。在这种情况下，指向树的 'root' 指针会指向 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等）常用的一种自平衡技术是红黑树。管理方式与上文所示大不相同，但前提保持相同。保持任何单个树深度（无论是整棵树还是整棵树中的任何子树）尽可能接近logN顺序，其中N是该树包含的节点数。保持这一点是为什么树可以提供效率的原因。