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