概述
由于二叉查找树的性能与树的高度(即根节点到底部节点的深度)相关,因此当高度较大时,二叉查找树的性能就会下降.为了更高效的性能,平衡查找树应运而生,它能保证无论键的插入顺序如何,树的高度都将是总键数的对数.
2-3查找树就是平衡树的一种.
性质
2-3查找树允许树中的一个节点保存多个键.我们可以将二叉查找树中的节点称为2-节点,而在2-3查找树中引入了3-节点,它含有两个键和三条链接.
一棵
2-3查找树由以下节点组成:
2-节点: 含有一个键(及其对应的值)和两条链接,左链接指向的2-3查找树中的键都小于该节点,右链接指向的2-3查找树中的键都大于该节点.
3-节点: 含有两个键(及其对应的值)和三条链接,左链接指向的2-3查找树中的键都小于该节点,中链接指向的2-3查找树中的键都位于该节点的两个键之间,右链接指向的2-3查找树中的键都大于该节点.
一棵完美平衡的2-3查找树中的所有空链接到根节点的距离都应该是相同的.
查找
2-3查找树的查找算法与二叉查找树基本相似.
- 首先,要判断一个键需要先将它和根节点中的键进行比较.
- 如果它和其中任意一个相等,查找命中.
- 否则,根据比较的结果找到指向相应区间的链接,并在其指向的子树中递归地继续查找.
- 如果最后指向空链接,查找未命中.
插入
由于2-3查找树需要保持完美平衡性,所以它的插入算法并不像二叉查找树那么简单.
它的插入算法基本思想是 : 一直向上不断分解临时的4-节点并将中键插入更高层的父节点中,直至遇到一个2-节点并将它替换为一个不需要继续分解的3-节点,或是到达3-节点的根(分解根节点)
向2-节点中插入新键
如果未命中的查找结束于一个2-节点,只需要把这个2-节点替换为一个3-节点,将要插入的键保存在其中即可.
向一棵只含有一个3-节点的树中插入新键
如果我们需要向一棵只含有一个3-节点的树中插入一个新键(这棵树中唯一的节点已经没有可插入新键的空间了).
- 先临时将新键存入该节点中,使之成为一个
4-节点(它扩展了以前的节点并含有3个键和4条链接).
- 将
4-节点分解为一棵由3个2-节点组成的2-3查找树,其中一个节点(根)含有中键,一个节点含有3个键中的最小者(和根节点的左链接相连),一个节点含有3个键中的最大者(和根节点的右链接相连).
- 这时,这棵树既是一棵含有3个节点的
二叉查找树,同时也是一棵完美平衡的2-3查找树.
向一个父节点为2-节点的3-节点中插入新键
如果未命中的查找结束于一个3-节点,而它的父节点是一个2-节点.这种情况下,我们需要在维持树的完美平衡性的前提下为新键腾出空间.
- 构造一个临时的
4-节点并将其分解(此时并不会为中键创建一个新节点).
- 将中键移动至父节点中(可以看做将指向
3-节点的一条链接替换为新父节点中的原中键左右两边的两条链接,并分别指向两个新的2-节点).
向一个父节点为3-节点的3-节点中插入新键
如果未命中的查找结束于一个父节点为3-节点且它本身也是一个3-节点时.我们可以构造一个临时的4-节点并分解它.将中键插入到它的父节点中.
但由于它的父节点也是一个3-节点,所以需要再用这个中键构造一个新的临时4-节点,然后在这个节点上进行相同的变换,即分解这个父节点并将它的中键插入到它的父节点中.
重复相同的变换直到遇到一个2-节点(将2-节点替换为一个3-节点)或者到达根节点(分解根节点).
分解根节点
如果从插入节点到根节点的路径上全部都是3-节点.那么根节点最终会变成一个临时的4-节点,这时可以将4-节点分解为3个2-节点,同时树高加1(仍然保持了树的完美平衡性,因为它变换的是根节点).
具体实现
关于如何使用一个简单的数据结构来表达实现2-3查找树可以见此文 <
总结
2-3查找树的根本在于插入操作中的变换操作都是局部的,除了相关的节点和链接之外不必修改或者检查树的其他部分.
每次变换都会将4-节点中的一个键移动至它的父节点中,并重构相应的链接而不必涉及树的其他部分.且保持了树的完美平衡性,例如在变换之前根节点到所有空链接的路径长度为h,那么变换之后该长度仍然为h.只有进行根节点分解时,所有空链接到根节点的路径长度才会加1.
通过这些我们可以总结得出: 2-3查找树的生长是由下向上的. (标准的二叉查找树则是由上向下生长的)
end
Author : SylvanasSun
Email : sylvanassun_xtz@163.com
本文参考资料引用自<