Binary Search Tree

如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为

,其查找效率为

，近似于折半查找。如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。