随机插入的二叉树vs红黑树

Question

我读过关于红黑树的书，我知道他们试图解决树变得不平衡的问题。但是，如果您使用随机插入会怎样呢？例如：

考虑以下需要插入的排序数字：

1,2,3,4,5,6,7,8,9,10

如果我们天真地插入到BST中，树将看起来像:1 2 3 .

在这种情况下，树将是超不平衡的，搜索将是线性的O(N)

然而，如果我们随机插入，它可能看起来更平衡(但在平均情况下可能不像红黑树那样平衡？)。如果我们使用红黑树，它将保证一个接近平衡的BST，但有一点开销。除了“在线算法”( self balancing binary search trees )，什么时候需要额外的开销来提高效率，而不是使用随机插入BST呢？

Answer 1

有这样一条线。您一直记得使用任何类型的动态数据结构(如BST和Red-Black Tree)的动机。动机很简单--保持数据的某种形状(在BST的情况下是有序的)。所以，如果你不想保留它，你可以使用像排序数组这样的东西。数组排序可以在O(n log n)上完成。而且你可以对排序后的数据做任何事情(就像固定时间的min/max/nth)！这真是太快了！但是，如果你打算在排序数组中添加一个新值，该怎么办呢？这就是事情变得有趣的地方。因此，您必须移动您的数组并在适当的位置插入一个新值。它需要O(n)。这听起来不像是正确的方式。但是，好消息是。有一些树可以在O(log n)时间内处理插入和删除。

那么line呢？我会说。如果您只打算将新元素插入到树中。并且输入值是随机的。因此，BST对于这项任务来说是完全可以的。但是，如果你打算做一些删除，你应该像RBTree一样创建新的自平衡树，因为BST由于删除而不平衡( BST上的删除操作是非对称的，它会生成高度为sqrt(n)的树)。

还有第三种情况。您可以尝试为BST找到一种对称的删除算法( 50年后仍未解决)，并成为计算机科学的巨星。祝你这些东西好运！

Answer 2

使用AVL树进行平衡。1在AVL树中，任何节点的两个子子树的高度最多相差一个；如果在任何时候它们相差超过一个，则重新平衡以恢复这一特性。在平均和最坏情况下，查找、插入和删除都需要O(log )时间，其中n是操作之前树中的节点数。插入和删除可能需要通过一个或多个树旋转来重新平衡树。

维基百科上有一篇文章here。