2-3树
2-3树是什么
2-3树由二节点和三节点构成绝对平衡的树。
二三树的性质
- 2-3树是绝对平衡的树（它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树）。
- 2-3树每次添加元素不会直接添加，而是进行节点融合，在融合之后，根据情况，进行分开融合等操作，将树转化为一个绝对平衡的2-3树。
添加过程
-
直接添加第一个元素42
1.png -
添加第二个元素的时候，将37融合在42的右边
2.png
3-1.添加第三个元素，首先将12放在节点最右边
3-1.png
3-2.但是由于2-3树最大节点是3节点，也就是两个元素，所以我们将这个节点拆开，编成三个2节点，这样，树就又变成了一个绝对平衡的2-3树
3-2.png
4.添加第4个元素12，直接融合在18的右边
4.png
5-1.添加第5个元素6，融合在12-18的右边，形成一个4节点
5-1.png
5-2.因为2-3树没有4节点，所以我们将4节点拆开
5-2.png
5-3.然后我们再把拆开的节点向上融合，则又形成了一个平衡的2-3树
5-3.png
总结如何融合
插入2节点.png
插入3节点.png
插入3节点，父亲为2节点.png
插入3节点，父亲为3节点.png
红黑树
概念或者性质
- 每个节点都是红色或者黑色的
- 根节点为黑色
- 每一个叶子节点（空节点）是黑色的
- 如果一个红黑树是红色的，那么他的孩子节点都是黑色的。
- 从任意一个节点到达叶子节点，经过的黑色节点数量是一样的，即，黑节点平衡。
2-3树与红黑树的关系
二三树与红黑树是同一种树，只不过红黑树是2-3树的一种只含2节点的表现形式。（注：红黑树并不是只有这一种实现方式）
-
我们可以把2-3树的三节点看作二分搜索树中的两个节点合作构成的一个节点，二其中小的一方就是红节点。
1.png -
一个2-3树按照1的设定展开
2.png
3.可以看到，将部分节点横放后，2-3树与红黑树其实是等价的。
3.png
