2-3树
2023/4/1 18:22:12
本文主要是介绍2-3树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
定义
一棵 2-3 树是一棵查找树,该查找树要么为空要么满足以下性质(令 left、middle、right 为 2-3 树结点的孩子指针;dl, dr为 2-3 树结点元素):
- 每个内部结点或者是一个2结点,或者是一个3结点。一个2结点存放一个元素,而一个3结点存放两个元素。
- 每个结点的 dl 值大于 left 指向子树所有结点内元素的值 且 小于 middle 指向子树所有结点的元素值。
- 每个结点的 dr 值大于 middle 指向子树所有结点的元素值 且 小于 right 指向子树的所有结点的元素值。
- 所有外部结点都在同一层。
根据定义,可以看出,2-3 树本身就是一个自平衡树。对于高度为 h 的一棵 2-3 树,其上的元素个数介于 2h - 1 到 3h - 1 之间。一棵包含 n 个结点的 2-3 树,其高度在 log2(n+1) 和 log3(n + 1) 之间。
类型定义
Java 定义
1 public class TwoThreeNode<T extends Comparable<T>> { 2 private T dataLeft; 3 private T dataRight; 4 private TwoThreeNode left; 5 private TwoThreeNode middle; 6 private TwoThreeNode right; 7 private TwoThreeNode parent; 8 }
比较函数
结点有2个元素,定义一个比较函数,返回值含义:
- 1 为左子树方向
- 2 为中子树方向
- 3 为右子树方向
- 4 为等于左元素
- 8 为等于右元素
查找函数
Java 定义
1 public TwoThreeNode<T> search(T data) { 2 TwoThreeNode<T> node = head; 3 while (node != null) { 4 int r = compare(node, data); 5 switch (r) { 6 case 1: node = node.getLeft(); break; 7 case 2: node = node.getMiddle(); break; 8 case 3: node = node.getRight(); break; 9 case 4: 10 case 8: return node; 11 } 12 } 13 return null; 14 }
插入
插入新元素,必然是插入到叶子结点中,如果是 2 结点的话,直接插入就结束了,但如果是3结点的话,如果向下溢出,则破坏了 2-3 树的平衡,因此需要拆分当前的结点然后向上合并,直到树根,以此保持 2-3 树自身的平衡。
- 如果是空树,则插入一个结点,设置结点为树根。
- 查找插入的结点位置,如果发现元素在树中,则插入失败,否则 定位插入的叶子结点 n 。
- n 结点是 2 结点时,直接插入 e 即可。
- n 结点是 3 结点时,由于插入 e 后,结点变为 4 结点,这时需要对结点 n 进行分裂,定义一个结点变量 q,初始化值为空,具体过程如下:
- 将 4 结点的三个元素的最小值存入 n 的左元素位置
- 以 4 结点的三个元素的最大值构建一个新的 2 结点 qq
- 根据 e 的位置设置 qq 的 left 和 middle 指针:
- 如果 e < n.dl 则 qq.left = n.middle | qq.middle = n.right | n.middle = q
- 如果 n.dl < e < n.dr 则 qq.left = q | qq.middle = n.right
- 如果 n.dr < e 则 qq.left = n.right | qq.middle = q
- 将 qq 赋值给 q,将 n 的父结点 赋值给 n,将 4 结点中中间值赋给 e 继续向上回溯
删除
找到待删除元素所在结点 n,如果 n 不是叶子结点,用它的直接前驱(左子树的最大元素)或者直接后继(右子树的最小元素)替换,进而转换为对叶子结点的删除。
- 如果被删除的是 3结点,直接删除即可。
- 如果被删除的是 2结点,删除后,结点元素为空(零元素)。如果删除结点,则2-3树自身平衡被破坏,因此需要从父节点 parent 和 兄弟节点 sibling 进行借元素进行合并:
-
- 如果 兄弟结点 sibling 为 3结点时,需要从父结点借一个元素过来,填充当前结点,而父结点的被借的元素位置需要从 sibling 的借一个元素过来。
- 如果 兄弟节点 sibling 为 2结点时,需要从父节点借一个元素过来 和 兄弟结点的的元素合并,组成一个3结点,兄弟结点得到释放。
- 如果 父节点处理后,结点元素为空(零元素),则继续向上回溯;否则退出。
这篇关于2-3树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署