查找算法总结
2019-04-13 本文已影响0人
北雁南飞_8854
二查查找树：
一颗二叉查找树是一个二叉树，其中每个节点都含有一个Comparable的键（以及相关联的值），且每个结点的键都大于左子树的任意结点的键二小于右子树的任意结点的键。
特点：
- 在由N个随机键构造的二叉查找树中，查找命中、查找未命中、插入操作平均所需的比较次数为1.39lgN；
- 在一棵二叉查找树中，所有操作在最坏情况下所需的时间都和树的高度成正比。
二叉查找树的基本实现的良好性能依赖于其中键的分布足够随机以消除路径长度。
红黑二叉查找树：
含有红黑链接、并满足以下条件的二叉查找树：
- 红链接均为左链接；
- 没有任何一个结点同时和两条红链接相连；
- 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。
优点：
二叉查找树高效的查找方法和2-3树高效的平衡插入算法。
保证最坏情况下的插入性能。
性质：
- 一颗大小为N的红黑树的高度不会超过2lgN；
- 一颗大小为N的红黑树中，根结点到任意结点的平局路径长度为lgN；
- 在一颗红黑树中，以下操作在最坏情况下的时间是对数级别的：查找、插入、查找最小键、查找最大键、删除等。
