2-3树和左倾红黑树
最后更新于：2022-04-02 04:11:39
[TOC]
## 概述
红黑树是一种近似平衡的二叉查找树
从`2-3`树或`2-3-4`树衍生而来
染色为红或黑节点，来模仿`2-3`树或`2-3-4`树的3节点和4节点
2-3-4 树对照实现的红黑树是普通的红黑树，而 2-3 树对照实现的红黑树是一种变种，称为左倾红黑树，其更容易实现。
使用平衡树数据结构，可以提高查找元素的速度
## 2-3 树
`3阶的B树`(注：`B`为`Balance`平衡的意思)
它不是一棵二叉树，是一棵三叉树。具有以下特征：
1. 内部节点要么有1个数据元素和2个孩子，要么有2个数据元素和3个孩子，叶子节点没有孩子，但有1或2个数据元素。
2. 所有叶子节点到根节点的长度一致。这个特征保证了完全平衡，非常完美的平衡。
3. 每个节点的数据元素保持从小到大排序，两个数据元素之间的子树的所有值大小介于两个数据元素之间。
### 树插入元素
### 左倾红黑树
左倾红黑树可以由`2-3`树的二叉树形式来实现。
其定义为：
1. 根节点的链接是黑色的。
2. 红链接均为左链接。
3. 没有任何一个结点同时和两条红链接相连
4. 任意一个节点到达叶子节点的所有路径，经过的黑链接数量相同，也就是该树是完美黑色平衡的。比如，某一个节点，它可以到达5个叶子节点，那么这5条路径上的黑链接数量一样。
';