【Data Structure】二叉搜索树 [part 2]
二叉搜索树 [part 2]
●二叉搜索树的顺序性
●二叉搜索树的局限性
●一种特殊的平衡二叉树：红黑树
●平衡二叉树和堆的结合：Treap
●Trie树（字典树）
7 二叉搜索树的顺序性
1、容易找到一组数据中的min和max
2、容易找到一组数据中的前驱和后继（要找A的前驱和后继，首先A要是二叉搜索树中的一个节点）
3、容易找到一组数据中的floor和ceil（要找A的floor和ceil，A不要求是二叉搜索树中的一个节点）
4、容易对一组数据执行select和rank操作（select：寻找第几位的数字 rank：寻找某个数字排在第几位）
在每个节点中多存一个属性——以该节点为根的二叉搜索树的节点数
5、支持重复元素的二叉搜索树
为每个节点多存一个属性——该元素的重复个数
8 二叉搜索树的局限性
同样的数据，可以对应不同的二叉搜索树
二叉搜索树可能退化成链表，相应操作有O(logn) ->O(n)
二叉搜索树不能像堆一样，保证所有操作都是有固定时间复杂度，其与树的形状有很大的关系