为什么每个二叉搜索树的高度不是 O(log n)

Question

在准备算法考试时，我读到每个 BST 的高度都不是 O(log n)。这个事实与树的平衡有关吗？每个平衡 BST O (log n) 和不平衡树的高度是其他东西吗（如果是的话，它是什么）？

Answer 1

每个不平衡BST的高度并不是O(lg n)因为想象一棵树的键按递增/递减顺序排列，其中该树会向一侧倾斜。这恰好是O(n)高度等于 的不平衡 BST 的最坏情况n。

另一方面，对于平衡树（例如 AVL 树），插入/删除期间的旋转允许这些树保持近似（不完美）的O(lg n)高度。