现在的位置: 首页 > 面试题 > 正文

二分搜索树的特性

2022年01月10日 面试题 ⁄ 共 312字 ⁄ 字号 暂无评论
博客主机

一、顺序性

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

 

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

 

二、局限性

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

 

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

 

 

 

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

Wopus问答

Wopus问答

给我留言

留言无头像?


×