二分搜索树的特性

一、顺序性

二分搜索树可以当做查找表的一种实现。

我们使用二分搜索树的目的是通过查找 key 马上得到 value。minimum、maximum、successor(后继)、predecessor(前驱)、floor(地板)、ceil(天花板、rank(排名第几的元素)、select(排名第n的元素是谁)这些都是二分搜索树顺序性的表现。

二、局限性

二分搜索树在时间性能上是具有局限性的。

如下图所示,元素节点一样,组成两种不同的二分搜索树,都是满足定义的:

二叉搜索树可能退化成链表,相应的,二叉搜索树的查找操作是和这棵树的高度相关的,而此时这颗树的高度就是这颗树的节点数 n,同时二叉搜索树相应的算法全部退化成 O(n) 级别。