本文介绍: 数据库-数据结构

一、B-树、B+树、B*树

搜索树:左子节点<节点<右子节点。
B-树:多路搜索树。
B+树:B-树的变体,更适用于文件系统,如mysql数据库。具体的,适合通过叶子节点的链指针进行区间查找。
B*树:B+树变体,提高了空间使用率

1

/

2

2

/

3

1/2→2/3

1/22/3
参考文章:一文详解 B-树,B+树,B*树

1 B-树

在这里插入图片描述

对于一颗m阶B-树(上图m=3)
特点:

  1. 根节点至少有2个子节点,或者为空树。
  2. 非叶子节点的子节点数k:

    m

    /

    2

    k

    m

    lceil m/2rceil ≤k≤m

    m/2km。当一个节点满了,分配一个新节点,把原节点一半的数据移动到新节点,并将该新节点加入到父节点中。此时改动只有该满的节点和其父节点。

  3. 非叶子节点的关键字数j:

    j

    =

    k

    1

    j=k-1

    j=k1

  4. 叶子节点在同一层。
  5. 对于某个节点的关键字K[1],K[2]…K[M-1],K[i]<K[i+1]。
  6. 对于某个非叶子节点的指针P[1],P[2]…P[M],P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其他的P[i]指向关键字在范围(K[i],K[i+1])的子树。
  7. 关键字分布在整棵树。
  8. 搜索过程中可能在非叶子节点结束。时间复杂度等于一次二分查找。

2 B+树

在这里插入图片描述
对于一颗m阶B+树(上图m=3)
与B-树的不同:

  1. 应文件系统所需的B-树变体。
  2. 非叶子节点的关键字个数j:

    j

    =

    k

    j=k

    j=k

  3. 关键字不保存数据,仅用于索引。数据保存在叶子节点。
  4. 对于某个非叶子节点的指针P[1],P[2]…P[M],P[i]指向关键字在范围[K[i],K[i+1])的子树。
  5. 所有叶子节点由一个链指针链接起来。
  6. 关键字分布在叶子节点。
  7. 搜索过程中得到叶子节点才结束。时间复杂度仍然等于一次二分查找。

3 B*树

在这里插入图片描述

对于一颗m阶B*树(上图m=3)
与B+树的不同:

  1. 在非根非叶子节点的层增加了兄弟指针。
  2. 非叶子节点的子节点数k:

    2

    m

    /

    3

    k

    m

    lceil 2m/3rceil ≤k≤m

    2m/3km,原先是

    m

    /

    2

    k

    m

    lceil m/2rceil ≤k≤m

    m/2km,提高了块的最低使用率。当一个节点满了,根据兄弟指针检查兄弟节点是否满了,未满则将一部分数据移动到兄弟节点;如果满了则分配一个新节点,把原节点和兄弟节点各自

    1

    /

    3

    1/3

    1/3的数据移动到新节点,并将该新节点加入到父节点中。此时改动有该满的节点、其父节点、兄弟节点、兄弟指针。

二、AVL树

搜索树:左子节点<节点<右子节点。有些有序的数据搭建成二叉搜索树后,可能会退化成了一个链表。AVL树通过控制平衡因子在[-1,1]内来避免退化。
AVL树:平衡二叉搜索树。即左右子树的高度差小于等于1,并且其子树也是平衡二叉树。
平衡因子:节点的左子树高度 – 节点的右子树高度。用于判断节点的平衡状态。
影响平衡因子的操作:删除节点、添加节点。
2种基础的平衡化操作:左旋、右旋。
4种需要平衡操作的情况:LL、RR、LR、RL。

需要平衡的情况 状态 操作
LL 平衡因子为2,左子树平衡因子为1 右旋
RR 平衡因子为-2,右子树平衡因子为-1 左旋
LR 平衡因子为2,左子树平衡因子为-1 对左子树左旋、再对该节点右旋
RL 平衡因子为-2,右子树平衡因子为1 对右子树右旋、再对该节点左旋

参考文章:详解 AVL 树(基础篇)

1 左旋

在这里插入图片描述
逆时针旋转,如果节点B有左子树。则将B的左子树作为A的右子树。

2 右旋

在这里插入图片描述
顺时针旋转,如果节点B有右子树。则将B的右子树作为C的左子树。

3 LL

在这里插入图片描述
状态:节点n的平衡因子为2,左节点i的平衡因子为1。
平衡操作:对节点n进行一次右旋操作。

4 RR

状态和操作与LL对称。

5 LR

在这里插入图片描述
状态:节点n的平衡因子为2,左节点i的平衡因子为-1。
平衡操作:1先对节点i进行一次左旋操作,2再对节点n进行一次右旋操作。

6 RL

状态和操作与LR对称。

三、红黑树

搜索树:左子节点<节点<右子节点。有些有序的数据搭建成二叉搜索树后,可能会退化成了一个链表,时间复杂度最高是O(n)。AVL树通过控制平衡因子在[-1,1]内来避免退化,使得其查找的时间复杂度是O(logn),但是增删节点时的平衡成本很高,所以出现了红黑树。

红黑树:自平衡二叉搜索树。
叶子节点:null节点,即叶子节点没有数据。所以下图中那些没有子节点的非null节点,默认是有2个null的叶子节点。
参考文章:最通俗易懂入门红黑树(R-B Tree)
图解红黑树的插入及调整过程+源码解读红黑树(二):删除操作
红黑树特点:

  1. 节点颜色有黑色、红色2种。
  2. 根节点为黑色。
  3. 叶子节点为黑色。
  4. 父子节点不能同时为红色。
  5. 从一个节点出发,到它的任意一个叶子节点,经过的黑色节点数相同。
    在这里插入图片描述

上述特点得出的一些推论:

  1. 根据特点4和5,从一个节点出发,到它的叶子节点的最长路径长度不会超过最短路径的2倍。此时最长路径是红黑间隔的,最短路径是全黑的。
  2. 根据特点5,新插入的节点为红色节点。此时,不会破坏特点5但有可能破坏特点4,需要做一些变色和旋转的操作。

1 插入操作

红黑树也是二叉搜索树,当有新的节点时,根据最小右大的规则先找到它的插入位置(即它的父节点以及它是左孩子还是右孩子),然后标记为红色,最后根据红黑树的特点,进行变色和旋转。
变色和旋转的判断规则:

情况 变色 旋转
父节点是黑色
父节点是红色且叔父节点是红色
父节点是红色且叔父节点是黑色

1.1 父节点是黑色

在这里插入图片描述
例如上图,插入66,此时仍然满足红黑树的特点。

1.2 父节点是红色且叔父节点是红色

在这里插入图片描述
例如上图,插入51。此时,49和51都是红色,所以不满足特点4,需要进行变色。
第一步,应该就是将父节点49和叔父节点43变成黑色,以满足特点4;
第二步,将祖父节点45变成红色,使得更上层的节点满足特点5。
第三步,此时递归到祖父节点,判断其是否出现违反特点4的情况,有则重复第一步和第二步,没有则执行第4步。
第四步:如果根节点变成了红色,重新染黑。

步骤图:
在这里插入图片描述
最终结果图:
在这里插入图片描述

1.3 父节点是红色且叔父节点是黑色

在这里插入图片描述

如果插入65,则其会成为66的左孩子。此时,叔父节点null是黑色,导致父节点66变成黑色后,该分支的路径比叔父节点的路径多了1个黑色,不满足特点5,所以需要进行旋转。其实旋转的目的和AVL树一样,插入节点后导致出现平衡因子=2或-2的情况,需要平衡。
在这里插入图片描述
不平衡情况有LL、RR、LR、RL四种,在AVL树中有说明。对于红黑树,旋转(LR和RL需要先旋转变为LL和RR)-变色-旋转。
LL:插入65。先变色,然后对祖父节点69进行右旋。
在这里插入图片描述

RR:插入70。先变色,然后对祖父节点66进行左旋。
在这里插入图片描述
LR:插入67。先对父节点左旋变成LL,然后根据LL的操作先变色再对祖父节点69右旋。
在这里插入图片描述
RL:插入68。先对父节点右旋变成RR,然后根据RR的操作先变色再对祖父节点66右旋。
在这里插入图片描述

2 删除操作

删除比插入要考虑更多因素。首先,删除可能删的是中间层的节点,其次,删除的节点可能是黑色。
按照删除的位置,有3种情况,有2个孩子、有1个孩子、没有孩子。

情况 处理方式 是否按颜色分类处理
有2个孩子 先根据中序遍历找到后继节点(右子树中最小的节点),然后替换掉。此时情况转变为(有1个孩子、没有孩子),按照这2种情况处理。 看后继节点是否有孩子
有1个孩子 直接删除,然后让父节点指向子节点,子节点变色
没有孩子 根据节点(当前节点、父节点、兄弟节点)颜色分情况处理

2.1 有2个孩子

在这里插入图片描述
如果要删除节点-1,则先跟后继节点0替换,问题转化为删除0(没有孩子),需要考虑节点颜色进行处理。
如果要删除节点4,则先跟后继节点5替换,问题转化为删除5(有1个孩子),不需要考虑节点颜色。

2.1 有1个孩子

在这里插入图片描述
删除节点D
颜色判断:D一定是黑色,孩子一定是红色
反证:如果该孩子是黑色,那么节点D的2个分支路径黑色节点数不相等(1≠2),不满足特点5。所以孩子是红色,再根据特点4,D是黑色。
操作:删除D,然后将子节点变黑色并作为父节点的新子节点。

2.3 没有孩子

需要根据节点颜色,分6种情况。
由于对称的情况操作是类似的,所以这里后3种情况都是以删除节点是其父亲节点的左子节点来讨论。

2.3.1 节点为红色

在这里插入图片描述
删除节点D
颜色判断:根据特点4,父节点必然是黑色。
操作:直接删除即可,不影响特点5。

2.3.2 父节点为红色,兄弟节点无孩子

在这里插入图片描述
删除节点D
颜色判断:根据特点4,当前节点和其兄弟节点为黑色。
操作:先删除节点;然后将父节点变成黑色;最后将兄弟节点变成红色。

2.3.3 父节点为红色,兄弟节点有孩子

在这里插入图片描述
删除节点D
颜色判断:兄弟节点的孩子为红色,否则父节点的左右分支不满足特点5。
操作:先删除节点D;然后判断父节点P是RL还是RR类型,如果是RL则右旋兄弟节点B得到RR类型;对父节点P、兄弟节点B和兄弟孩子节点BR进行变色(如果是RL转RR的不需要对BR变色);对父节点P左旋。

2.3.4 节点为黑色,父节点为黑色,兄弟节点有左孩子

在这里插入图片描述
删除节点B
颜色判断:兄弟节点的孩子为红色,否则父节点的左右分支不满足特点5。
操作:先删除节点B;此时父节点P是RL类型,需要进行右旋得到RR,并且对节点D和DL变色使得满足特点4;接着对节点P进行做左旋;最后对DL进行变色使得满足特点5。

2.3.5 节点为黑色,父节点为黑色,兄弟节点只有右孩子

在这里插入图片描述

删除节点B
颜色判断:同2.3.4。
操作:比2.3.4少一次右旋。先删除节点B;接着对节点P进行做左旋;最后对DR进行变色使得满足特点5。

2.3.6 节点为黑色,父节点为黑色,兄弟节点无孩子

在这里插入图片描述
删除节点B
操作:先删除节点B,然后将兄弟节点D染成黑色。此时,P这个分支满足特点4和5,但是P的更上层左右分支不满足特点5,所以需要向上递归。
递归过程:如果P的父节点是红色,则根据2.3.2和2.3.3来处理。如果是黑色,则根据2.3.4/2、2.3.5、2.3.6处理。(这里可能还得再细化一下,使得具体操作可以递归处理)

原文地址:https://blog.csdn.net/weixin_45034895/article/details/135570060

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_56928.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注