我读过红黑树，我知道他们试图解决树变得不平衡的问题。但是，如果您要使用随机插入怎么办。例如：
考虑以下需要插入的排序数字：
1,2,3,4,5,6,7,8,9,10
如果我们天真地插入 BST，树看起来像：1 2 3 ..
在这种情况下，树将是超级不平衡的，搜索将是线性的 O(N)
但是，如果我们将插入随机化，它可能看起来更平衡（但在一般情况下可能不像红黑树那样平衡？）。如果我们使用红黑树，它将保证接近平衡的 BST，但会产生一些开销。除了“在线算法”（自平衡二叉搜索树）之外，什么时候需要这种额外的开销来提高效率与使用随机插入 BST
有这样一条线。您总是记得使用任何类型的动态数据结构（如 BST 和红黑树）的动机。动机非常简单 - 将数据保持在某种形状（在 BST 的情况下排序）。所以，如果你不想保留它，你可以使用排序数组之类的东西。数组排序可以在O(n log n). 您可以在恒定时间内对已排序的数据（如min// max）做任何事情！nth这是极快的！但是，如果您打算将新值添加到已排序的数组中怎么办。这就是事情变得有趣的地方。因此，您必须移动数组并在适当的位置插入一个新值。它需要O(n). 而且这听起来不像是正确的方法。但是，好消息。有些树可以及时处理插入和移除O(log n)。
那么线呢。我会说。如果您打算只将新元素插入树中。并且输入值是随机的。因此，BST 非常适合这项任务。但是，如果您打算进行一些移除，那么您应该新建像 RBTree 这样的自平衡树，因为 BST 由于移除而导致不平衡（BST 上的移除操作是非对称的，它会生成高度为 的树sqrt(n)）。
还有第三种情况。您可以尝试找到 BST 的对称删除算法（50 年仍未解决）并成为计算机科学的摇滚明星。祝你好运！