一棵2-3查找树或为一棵空树,或由以下节点组成:
2-节点:含有一个键和两条链接,左链接指向的2-3树中的键都小于该节点,右链接指向的2-3树中的键都大于该节点.
3-节点:含有两个键和三条链接,左链接指向的2-3树中的键都小于该节点,中链接指向的2-3树中的键都位于该节点的两个键之间,右链接指向的2-3树中的键都大于该节点.
2-3_1.jpeg
一棵完美平衡的2-3查找树中的所有空链接到根节点的距离都应该是相同的.
由于2-3树也是属于二叉查找树中的一种,往树里面插入一个新节点时,肯定是插入到某个叶子节点上.需要分情况讨论因为有两种节点类型.
叶子节点是2-节点: 直接把新节点加入到2-节点生成一个新的3-节点.
2-3_2.jpeg
叶子节点是3-节点:当把新节点加入到3-节点会变成临时的4-节点,然后再进行分解成3个2-节点.
2-3_3.jpeg
把中间的2-节点传递给父亲节点,至于父亲节点是2-节点或者3-节点就可以进行递归处理.直接上图会比较好理解.
2-3_4.jpeg
再看一张图
2-3_5.jpeg
参考算法4.
1. 2-3 树1.1 2-3树查找元素1.2 2-3树删除元素删除最小元素删除任意元素1.3 2-3树与AVL ...
2-3树 2-3树是什么 2-3树由二节点和三节点构成绝对平衡的树。 二三树的性质 2-3树是绝对平衡的树（它是一...
本文主要包括以下内容： 什么是2-3树 2-3树的插入操作 红黑树与2-3树的等价关系 《算法4》和《算法导论》上...
2-3 树 在介绍红黑树之前有必要先介绍一下2-3树，因为直接理解红黑树是有一定难度的，而红黑树其实是2-3 树的...
平衡树 常见平衡树：平衡二叉查找树，2-3查找树，AVL树， 红黑树 2-3查找树 概述:保证查找树的平衡性，我们...
2-3树 1. 2-3树的定义 一颗2-3查找树或为一颗空树，或由以下节点组成： 2-节点，含有一个键（及其对应的...
2-3树 在了解红黑树之前，我们先来认识2-3树，在算法（第4版）[https://book.douban.com...
画了一系列树的动画，从二分搜索树，到AVL树，再到2-3树，再到基于2-3树的红黑树，都可以发现这些树都跟二叉查找...
定义 一棵2-3查找树或为一棵空树,或由以下节点组成:2-节点:含有一个键和两条链接,左链接指向的2-3树中的键都...
平衡查找树 定义 父节点的左子树和右子树的高度之差不能大于1 2-3查找树 定义 2-3树运行每个节点保存1个或者...
本文标题：2-3树
本文链接：https://www.haomeiwen.com/subject/iqkveftx.html
网友评论