复习:AVL树/红黑树/B树/B+树原理及应用
一、AVL树
二叉查找树的一个局限性就是有可能退化成一个链表,这种情况下二叉查找树的效率就会急剧下降变成0(n)。而AVL树可以很好地解决BST的这种困境。
1、什么是AVL树
任何两个子树的高度差最大是1,这样的二叉树叫做AVL树。
2、AVL树的特点
(1)AVL的左右子树高度之差的绝对值不超过1。
(2)树中的每个左子树和右子树都是AVL。
(3)每个节点都有一个平衡因子,任一节点的平衡因子至多为1。
(4)平衡二叉树的高度和结点数量之间的关系是O(logn)。
3、平衡因子
平衡因子 = | 左子树高度 - 右子树高度 |
4、维持自平衡性
AVL树为了维持自身平衡性,在插入元素时,计算了每个节点的平衡因子是否大于1,如果大于,那么就将进行相应的旋转操作以维持平衡性。
二、红黑树
一种二叉查找树,但是在每个节点增加一个存储位表示节点的颜色,可以是红色或者黑色,通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条 路径会比其他路径长两倍。是一种弱平衡二叉树(由于是弱平衡,相同节点的情况下,AVL树的高度低于红黑树),相对于严格要求的AVL树而言,红黑树旋转的次数变少,因此在搜索、删除、插入操作多的情况,可以使用红黑树。
1、红黑树的性质:
算法导论:一棵有n个内节点的红黑树高度至多为2lg(n+1),则h=O(log(n))
0)在红黑树中,叶子结点指空结点NULL。
1)每个结点要么是红的,要么是黑的。
2)根结点是黑的。
3)每个叶结点,即空结点(NIL)是黑的。(首尾必黑)
4)如果一个结点是红的,那么它的俩个儿子都是黑的。(不存在连续2红)
5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。(黑色完美平衡)
5-1)右5知,如果一个结点存在黑子结点,那么该结点肯定有两个子结点
2、红黑树与AVL树的比较:
-
AVL是严格的平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多;
-
红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。红黑树能够以O(logn) 的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。
类型 | 平衡度 | 调整频率 | 适用场景 |
---|---|---|---|
AVL树 | 高 | 高 | 查询多,增/删少 |
红黑树 | 低 | 低 | 增/删频繁 |
所以简单说,如果你的应用中,搜索的次数远远大于插入和删除,那么选择AVL树,Windows NT内核中广泛存在.
如果搜索,插入删除次数几乎差不多,应选择红黑树。即,有时仅为了排序(建立-遍历-删除),不查找或查找次数很少,R-B树合算一些。
3、红黑树的应用
-
广泛用于C++的STL中,map和set都是用红黑树实现的.
-
著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.
-
IO多路复用epoll的实现采用红黑树组织管理sockfd,以支持快速的增删改查.
-
ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.
-
java中TreeMap、hashmap、concurrenthashmap(1.8)的实现.
三、B树(B-树与B树等同)
b树(balance tree)和b+树应用在数据库索引,可以认为是m叉的多路平衡查找树,但是从理论上讲,二叉树查找速度和比较次数都是最小的,为什么不用二叉树呢?
因为我们要考虑磁盘IO的影响,它相对于内存来说是很慢的。数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘页(对应索引树的节点)。所以我们要减少IO次数,对于树来说,IO次数就是树的高度,而“矮胖”就是b树的特征之一,它的每个节点最多包含m个孩子,m称为b树的阶,m的大小取决于磁盘页的大小。
1、一个M阶的b树具有如下几个特征:
- 定义任意非叶子结点最多只有M个儿子,且M>2;
- 根结点的儿子数为[2, M];
- 除根结点以外的非叶子结点的儿子数为[M/2, M],向上取整(下边界怎么理解??);
- 非叶子结点的关键字个数=儿子数-1(2刀切3段,7刀切8段);
- 所有叶子结点位于同一层;
- k个关键字把节点拆成k+1段,分别指向k+1个儿子,同时满足查找树的大小关系。
2、有关b树的一些特性,注意与后面的b+树区分:
- 关键字集合分布在整颗树中;
- 任何一个关键字出现且只出现在一个结点中;
- 搜索有可能在非叶子结点结束;
- 其搜索性能等价于在关键字全集内做一次二分查找;
3、如图是一个3阶b树,顺便讲一下查询元素5的过程:
第一次磁盘IO,把9所在节点读到内存,9节点中含有value,刚好要搜索结点9,则在此处返回了不必再深入树的下层。然而目标是5,小于9,跳转到小于9对应的节点;
第二次磁盘IO,还是读节点到内存,在内存中把5依次和2、6比较,定位到2、6中间区域对应的节点;
第三次磁盘IO就不上图了,跟第二步一样,然后就找到了目标5。
- 可以看到,b树在查询时的比较次数并不比二叉树少,尤其是节点中的数非常多时,但是内存的比较速度非常快,耗时可以忽略,所以只要树的高度低,IO少,就可以提高查询性能,这是b树的优势之一。
四、B+树
b+树,是b树的一种变体,查询性能更好。
1、m阶的b+树的特征:
- 有n棵子树的非叶子结点中含有n个关键字(b树是n-1个),这些关键字key没有数据value,结点中仅含其子树中的最大(或最小)关键字的结点指针,所有数据value都保存在叶子节点(b树是每个关键字都保存数据)。
- 所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
- 所有关键字都在叶子节点出现(稠密索引). (且链表中的关键字恰好是有序的);
- 非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层.
- 同一个数字会在不同节点中重复出现,根节点的最大元素就是b+树的最大元素。
2、b+树相比于b树的查询优势:
- b+树的中间节点不保存数据,所以磁盘页能容纳更多节点元素,更“矮胖”;
- b+树查询必须查找到叶子节点,b树只要匹配到即可不用管元素位置,因此b+树查找更稳定(并不慢);
- 对于区间查找和范围查找来说,b+树只需遍历叶子节点链表即可,b树却需要重复地中序遍历,
3、B/B+树的共同优点:
考虑磁盘IO的影响,它相对于内存来说是很慢的。数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘页(对应索引树的节点)。所以我们要减少IO次数,对于树来说,IO次数就是树的高度,而“矮胖”就是b树的特征之一,m的大小取决于磁盘页的大小。