首页 > 代码库 > 2-3查找树

2-3查找树

2024-07-02 07:59:39   224人阅读

作者：disappearedgod
文章出处：http://blog.csdn.net/disappearedgod/article/details/24661755
时间：2014-4-18

前言

源自博客文章“查找与树”，由于2-3树实在有太多面试意义，所以单独抽出来成文。
由于叙述众多，不在本博客中做详细解释，正文部分中有相关链接，请点击查阅。

正文

1.3.1.1 定义及优势

1.3.1.1.1 定义

定义 一棵2-3查找树或为一棵空树，或由以下结点组成：
2-结点，含有一个键(及其对应的值)和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
3-结点，含有两个键(及其对应的值)和三条链接，左链接指向的2-3树中的键都小于该结点，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都待遇该结点。
将指向一棵空树的链接成为空链接。

1.3.1.1.2 优势

和标准二叉树有上向下生长不同，2-3树是由下向上生长的（堆排序恰巧也是符合这个思想的二叉树）。一个简单的构造例子如下：

2-3树的查找效率与树的高度是息息相关的。

  • 在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN
  • 在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于0.631lgN
  • 1百万个节点的2-3树，树的高度为12-20之间,对于10亿个节点的2-3树，树的高度为18-30之间。



1.3.1.1.3 为什么要这样排列？

 因为它是balanced的！一棵高度为k的2-3 tree有2k – 1 到 3k – 1 之间的叶；一棵有elements 为n的2-3 tree 高度最小为 1+log3n， 最大为 1+log2n。它的检索时间为O(logn)。

伪代码如下：

LOOP until curr = nil

IF ( data = http://www.mamicode.com/curr.small OR data = curr.large )>
假设已处平衡状态，我们先看基本操作。
1.3.1.2 查找
2-3树的查找和二叉查找树类似，要确定一个树是否属于2-3树，我们首先和其跟节点进行比较，如果相等，则查找成功；否则根据比较的条件，在其左中右子树中递归查找，如果找到的节点为空，则未找到，否则返回。

  • 二叉树按照升序插入10个key会得到高度为9的一棵最差树，2-3Tree的高度为2.
  • 含有10亿个结点的一棵2-3树的高度仅在19-30之间。（也就是说，访问最多30个结点可查）

1.3.1.2.1 插入

插入：1. 未命中查找;2.新节点挂在底部；3.平衡。

对于2-3 tree，所有的插入（新值）都必须发生在leaf。所以，首先找到新值应该所在的leaf，然后根据这个leaf的情况做出判断：

 1．  该点只有一个元素。直接加入就可以了，判断是small还是large。

 2．  该点full（small和large都有值），其父结点不是full。那就split该结点，并把中间值推上去。

 3．  该点和其父结点都full。如果父结点full，表示父结点已经有3个子树。那就需要一直split 并一直往上推，直到发生以下情况：

         1)     父结点最多只有3个子树

         2)     父结点是根，创建一个新root，保存中间值。树的高度增加1

1.3.1.2.2 往一个2-node节点插入

往2-3树中插入元素和往二叉查找树中插入元素一样，首先要进行查找，然后将节点挂到未找到的节点上。2-3树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态。如果查找后未找到的节点是一个2-node节点，那么很容易，我们只需要将新的元素放到这个2-node节点里面使其变成一个3-node节点即可。但是如果查找的节点结束于一个3-node节点，那么可能有点麻烦。


1.3.1.2.3 往一个3-node节点插入

往一个3-node节点插入一个新的节点可能会遇到很多种不同的情况，下面首先从一个最简单的只包含一个3-node节点的树开始讨论。
  • 新建插入，临时将新键存入该节点中，使之成为4-结点。
  • 3-key 4-link，为了容易转化为一棵由3个2-node组成的2-3 Tree


1.3.1.2.4 向节点是3-node，父节点是2-node中插入新键

需要在维持树的完美平衡的前提下为新建腾出空间。
分析：父节点既然是2-node，就要改成3-node，只有将新的4-node中的中值赋给2-node，作为3-node中后面的一个点。
  • 新建插入，临时将新键存入该节点中，使之成为4-结点。
  • 3-key 4-link，为了容易转化为一棵由3个2-node组成的2-3 Tree
  • 将上述的父节点（3.1.2.2中分解出的父节点）与其真正的父节点（2-node）合并。


1.3.1.2.5 节点是3-node，父节点也是3-node

当我们插入的节点是3-node的时候，我们将该节点拆分，中间元素提升至父节点，但是此时父节点是一个3-node节点，插入之后，父节点变成了4-node节点，然后继续将中间元素提升至其父节点，直至遇到一个父节点是2-node节点，然后将其变为3-node，不需要继续进行拆分。

1.3.1.2.6 分解根节点

当根节点到字节点都是3-node节点的时候，这是如果我们要在字节点插入新的元素的时候，会一直查分到跟节点，在最后一步的时候，跟节点变成了一个4-node节点，这个时候，就需要将跟节点查分为两个2-node节点，树的高度加1，这个操作过程如下：

1.3.1.2.5 汇总

1.3.1.2.5.1 局部变换
2-3 Tree插入算法的根本在于这些变换都是局部的：除了相关节点和链接之外不必修改或检查树的其他部分。换句话说，每次变换中，变更的连接数不会超过一个很小的常数。

1.3.1.2.5.2 全局性质
全局有序性和全局平衡性：任意空链接到根节点的路径长度都是相等的。

1.3.1.2.5.3 2-3树的实现

1.3.1.3 一些扩展

一个有趣的小例子：   2–3 Tree Java Applet
Reference：
  1. Gross, R. Hernández, J. C. Lázaro, R. Dormido, S. Ros (2001). Estructura de Datos y Algoritmos. Prentice Hall. ISBN 84-205-2980-X.
  2. Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley., p.145-147

2-3查找树


联系
我们