登录
原创

2-3树,2-3-4树,B树

发布于 2020-12-12 阅读 419
  • 算法
原创

2-3树是一种多路查找树

2和3的意思就是2-3树包含两种结点

  1. 2结点包含一个元素和两个孩子(或者没有孩子)。

    ① 左子树包含结点的元素值小于该结点的元素值,右子树包含的结点的元素值大于该结点的元素值

    ② 2结点要不有两个孩子,要不就没有孩子,不允许有一一个孩子

  2. 3结点包含一大一 小两个元素和三个孩子(或者没有孩子)。(两个元素按大小顺序排列好)

    ①左子树包含的结点的元素值小于该结点较小的元素值,右子树包含的结点的元素值大于该结点较大
    的元素值,中间子树包含的结点的元素值介于这两个元素值之间。

    ②3结点要不有三个孩子,要不就没有孩子,不允许有一个或两个孩子

  3. 2 -3树所有叶子结点都在同一层次

2-3-4树

  1. 2结点包含一个元素和两个孩子(或者没有孩子)。

    ① 左子树包含结点的元素值小于该结点的元素值,右子树包含的结点的元素值大于该结点的元素值

    ② 2结点要不有两个孩子,要不就没有孩子,不允许有一一个孩子

  2. 3结点包含一大一 小两个元素和三个孩子(或者没有孩子)。(两个元素按大小顺序排列好)

    ①左子树包含的结点的元素值小于该结点较小的元素值,右子树包含的结点的元素值大于该结点较大
    的元素值,中间子树包含的结点的元素值介于这两个元素值之间。

    ②3结点要不有三个孩子,要不就没有孩子,不允许有一个或两个孩子

  3. 2 -3-4 树所有叶子结点都在同一层次

  4. 4结点包含小中大三个元素和四个孩子(或者没有孩子)。

    ①最左子树包含的结点的元素值小于该结点最小的元素值,第二个子树包含的结点的元素值大于
    最小的元素值小于中间元素值,第三个子树包含的结点的元素值大于中间元素值小于最大元素值,
    最右子树包含的结点的元素值大于该结点最大的元素值。

    ②4结点要不有四个孩子,要不就没有孩子,不允许有一个或两个或三个孩子

B树

B树也是一种平衡的多路查找树,2-3树和2-3-4树都是B树的特例, 我们把树中结点最大的孩子数目称
为B树的阶。通常记为m

一棵m阶B树或为空树, 或为满足如下特性的m叉树:

  1. 树中每个结点至多有m棵子树。(即至多含有m-1个关键字) (“两棵子树指针夹着一个关键字”)

  2. 若根结点不是终端结点,则至少有两棵子树。(至少一个关键字)

  3. 除根结点外的所有非叶结点至少有<math><semantics><mrow><mo>⌈</mo><mi>m</mi><mi mathvariant="normal">/</mi><mn>2</mn><mo>⌉</mo></mrow><annotation encoding="application/x-tex">\lceil m/2 \rceil</annotation></semantics></math>m/2棵子树。(即至少含有<math><semantics><mrow><mo>⌈</mo><mi>m</mi><mi mathvariant="normal">/</mi><mn>2</mn><mo>⌉</mo><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">\lceil m/2 \rceil-1</annotation></semantics></math>m/21个关键字)。 判断是否需要分裂

  4. 所有非叶结点的结构如下:

    n P<math><semantics><mrow><msub><mrow></mrow><mn>0</mn></msub></mrow><annotation encoding="application/x-tex">_0</annotation></semantics></math>0 K<math><semantics><mrow><msub><mrow></mrow><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">_1</annotation></semantics></math>1 P<math><semantics><mrow><msub><mrow></mrow><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">_1</annotation></semantics></math>1 K<math><semantics><mrow><msub><mrow></mrow><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">_2</annotation></semantics></math>2 …… K<math><semantics><mrow><msub><mrow></mrow><mi>n</mi></msub></mrow><annotation encoding="application/x-tex">_n</annotation></semantics></math>n P<math><semantics><mrow><msub><mrow></mrow><mi>n</mi></msub></mrow><annotation encoding="application/x-tex">_n</annotation></semantics></math>n

    其中K<math><semantics><mrow><msub><mrow></mrow><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">_i</annotation></semantics></math>i(i=1,2,……,n)为结点的关键字,且满足K<math><semantics><mrow><msub><mrow></mrow><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">_1</annotation></semantics></math>1<K<math><semantics><mrow><msub><mrow></mrow><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">_2</annotation></semantics></math>2<K<math><semantics><mrow><msub><mrow></mrow><mn>3</mn></msub></mrow><annotation encoding="application/x-tex">_3</annotation></semantics></math>3<……K<math><semantics><mrow><msub><mrow></mrow><mi>n</mi></msub></mrow><annotation encoding="application/x-tex">_n</annotation></semantics></math>n

    其中P<math><semantics><mrow><msub><mrow></mrow><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">_i</annotation></semantics></math>i(i=0,1,2,……,n)为指向子树根节点的指针,且指针P<math><semantics><mrow><msub><mrow></mrow><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub></mrow><annotation encoding="application/x-tex">_{i-1}</annotation></semantics></math>i1所指的子树的所有节点的关键字都小于K<math><semantics><mrow><msub><mrow></mrow><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">_i</annotation></semantics></math>i,P<math><semantics><mrow><msub><mrow></mrow><mrow><mi>i</mi></mrow></msub></mrow><annotation encoding="application/x-tex">_{i}</annotation></semantics></math>i所指向子树的所有结点的关键字都小于K<math><semantics><mrow><msub><mrow></mrow><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub></mrow><annotation encoding="application/x-tex">_{i+1}</annotation></semantics></math>i+1,n是结点中关键字的个数

  5. 所有的叶子结点出现在同一层次上,不带信息。(就像是折半查找判断树中查找失败的结点)

1.B树的查找操作

B树是多路查找树,二叉排序树是二路查找,B树是多路查找,所以它是二叉排序树的拓展。因此,B树的查找
操作和二叉排序树的查找操作非常类似。
查找过程:①先让待查找关键字key和结点的中的关键字比较,如果等于其中某个关键字,则查找成功。
②如果和所有关键字都不相等,则看key处在哪个范围内,然后去对应的指针所指向的子树中查找。
Eg:如果Key比第一个关键字K1还小, 则去P0指针所指向的子树中查找,如果比最后一一个关键字Kn,还
大,则去Pn指针所指向的子树中查`找。

2.B树的插入操作

在二叉排序树中,仅需查找到需插入的终端结点的位置。但是,在B树中找到插入的位置后,并不能
简单地将其添加到终端结点位置,因为此时可能会导致整棵树不再满足B树中定义中的要求。
给定一-组关键字(20,30, 50, 52, 60, 68, 70}, 给出创建一棵3阶B树的过程。

3.B树的删除操作

B树中的删除操作与插入操作类似,但要稍微复杂些,要使得删除后的结点中的关键字个数≥[m/21-1,因此
将涉及结点的“合并" 问题。由于删除的关键字位置不同,可以分为关键字在终端结点和不在终端结点上两
种情况。

评论区

v知
1粉丝

励志做一条安静的咸鱼,从此走上人生巅峰。

0

0

0

举报