学习算法考试，我读到每个BST的高度都不是O(log n).这个事实与树的平衡有关吗?是否每个平衡BST树的高度都是O (log n)，而非平衡树的高度又是什么(如果是的话是什么)?
每个不平衡 BST的高度不是O(lg n)，因为想象一个键按增减顺序排列的树，其中树向一侧倾斜。这恰好是高度等于n的非平衡BST的O(n)最坏情况。
另一方面，对于平衡树，如AVL树，插入/删除期间的旋转允许这些树保持近似(不完美)的O(lg n)高度。
是的，因为树是不平衡的。考虑一下在树中插入一个排序的数字序列时会发生什么。每个数字都是前一个插入数字的子数字。树的高度是O(n)