为了插入二叉搜索树的时间效率，
我知道插入的最佳/平均情况是O（log n），其中最坏的情况是O（N） .
我想知道的是，除了实施AVL（ balancer BST）之外，是否有任何方法可以确保我们在插入时始终具有最佳/平均情况？
谢谢！
如果不 balancer 二叉搜索树，则无法保证 log n 复杂性 . 在搜索/插入/删除时，您必须在树中导航才能将自己定位在正确的位置并执行操作 . 关键问题是 - 获得正确位置所需的步骤数量是多少？如果BST是 balancer 的，您可以预期 2^(i-1) 级别的平均节点 2^(i-1) . 这进一步意味着，如果树具有 k 级别（ k 称为树的高度），则树中预期的节点数为 1 + 2 + 4 + .. + 2^(k-1) = 2^k - 1 = n ，这将给出 k = log n ，这是从根导航到所需的平均步数叶子 .
log n
2^(i-1)
k
1 + 2 + 4 + .. + 2^(k-1) = 2^k - 1 = n
k = log n
话虽如此，有各种 balancer BST的实现 . 你提到AVL，另一个非常受欢迎的是red-black tree，它可以用于例如在C中实现 std::map 或在Java中实现 TreeMap .
std::map
TreeMap
最糟糕的情况是 O(n) ，当您不 balancer BST并且您的树退化为链接列表时，可能会发生这种情况 . 很明显，为了定位在列表的末尾（这是最坏的情况），你必须遍历整个列表，这需要 n 步骤 .
O(n)
n
1 回答
如果不 balancer 二叉搜索树，则无法保证
log n复杂性 . 在搜索/插入/删除时，您必须在树中导航才能将自己定位在正确的位置并执行操作 . 关键问题是 - 获得正确位置所需的步骤数量是多少？如果BST是 balancer 的，您可以预期2^(i-1)级别的平均节点2^(i-1). 这进一步意味着，如果树具有k级别（k称为树的高度），则树中预期的节点数为1 + 2 + 4 + .. + 2^(k-1) = 2^k - 1 = n，这将给出k = log n，这是从根导航到所需的平均步数叶子 .话虽如此，有各种 balancer BST的实现 . 你提到AVL，另一个非常受欢迎的是red-black tree，它可以用于例如在C中实现
std::map或在Java中实现TreeMap.最糟糕的情况是
O(n)，当您不 balancer BST并且您的树退化为链接列表时，可能会发生这种情况 . 很明显，为了定位在列表的末尾（这是最坏的情况），你必须遍历整个列表，这需要n步骤 .