我读过红黑树，我知道他们试图解决树变得不平衡的问题。但是，如果您要使用随机插入怎么办。例如：
考虑以下需要插入的排序数字：
1,2,3,4,5,6,7,8,9,10
如果我们天真地插入一个BST，树看起来会是这样的:1 2 3..
在这种情况下，树将是超级不平衡的，搜索将是线性O（N）
然而，如果我们随机化插入，它可能看起来更平衡(但在一般情况下可能不像红黑树那样平衡？) .如果我们使用红黑树，它将保证一个接近平衡的BST，但有一点开销。除了“在线算法”(自平衡二分搜索法树)之外，什么时候才能划清为了效率与使用随机插入BST的额外开销的界限
有这样一条线。你一直记得使用任何类型的动态数据结构（如BST和红黑树）的动机。动机非常简单 - 将数据保持在某种形状（在 BST 的情况下排序）。所以，如果你不想保留它，你可以使用排序数组之类的东西。数组排序可以在 O（n log n） 上完成。您可以在恒定时间内对排序的数据（如最小/最大/第 n 个）执行任何操作！这是非常快的！但是，如果您计划将新值添加到排序数组中怎么办。这就是事情变得有趣的地方。因此，您必须移动数组并在适当的位置插入一个新值。它需要 O（n）。这听起来不像是一个正确的方式。但是，好消息。有些树可以在 O（log n） 时间内处理插入和删除。
那么线呢？我会说。如果你只打算在树中插入新元素。输入值是随机的。所以，BST完全可以完成这项任务。但是，如果你打算做一些删除，你应该像RBTree这样的新自平衡树，因为BST由于删除而不平衡（BST上的删除操作是不对称的，它会生成高度为sqrt（n）的树）。
还有第三种情况。您可以尝试找到BST的对称去除算法（50年来仍未解决），并成为计算机科学的摇滚明星。这些东西运气好！
使用AVL树进行平衡..AVL树是一种自平衡二叉查找树，它是第一个发明的此类数据结构。1在AVL树中，任何节点的两个子树的高度最多相差1；如果在任何时候它们相差一个以上，就要进行重新平衡以恢复该属性。在平均和最坏的情况下，查找、插入和删除都需要O(log n)时间，其中n是操作之前树中的节点数。插入和删除可能需要通过一次或多次树循环来重新平衡树。
维基百科在这里有一篇文章。
