[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条路径上的黑链接数量一样。