红黑树是一种2-3查找树的一种简洁实现。本文从2-3查找树的概念开始，逐步介绍红黑树的实现原理。
从2-3树开始
2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key。
2-3查找树的定义如下：
1、要么为空，要么：
2、是一个2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点。
3、对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。
2-3 树的查找
2-3树的插入
往一个2-node节点插入
首先要进行查找，然后将节点挂到未找到的节点上。
如果查找后未找到的节点是一个2-node节点，那么很容易，我们只需要将新的元素放到这个2-node节点里面使其变成一个3-node节点即可。
往一个3-node节点插入
1、只包含一个3-node节点。
暂时使其变成一个4-node节点，然后，我们将这个4-node节点的中间元素提升，左边的节点作为其左节点，右边的元素作为其右节点。
插入完成，变为平衡2-3查找树，树的高度从0变为1。
2、节点是3-node，父节点是2-node
同理，临时的4-node节点提升，此时高度加一，再使原父节点和提升后的节点合并成3-node 节点，高度减一。
3、节点是3-node，父节点也是3-node
节点临时的4-node节点提升，此时高度加一，再使临时4-node节点的父节点的父节点和提升后的节点合并成一个新节点，高度减一。重复操作，直到新节点是一个2-3节点。
总结：
4-node节点拆分成2-3node涉及的操作有6种：
在root；
在2-node 节点的左右；
在3-node 节点的左中右；
对于4-node节点变形为2-3节点，变形前后树的高度没有发生变化。只有当跟节点是4-node节点，变形后树的高度才加一。如下图所示：（6中4-node 变形的可能情况）
红黑树
首先，红黑树和avl树都是自平衡树，但是定义不同，表现有所区别。AVL树要求它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，红黑树要求所有的黑色连接是一个完全平衡的二叉树。
“ 红黑树的主要是想对2-3查找树进行编码，以约定的编码形式使用2-node 节点表示3-nodes，从而实现2-3 查找树。”这样做使2-3节点的实现在2节点的树中完成。
红黑树是一种具有红色和黑色链接的平衡查找树，同时满足：
- 红色节点向左倾斜 （减少3-nodes节点的类型）
- 一个节点不可能有两个红色链接 （两个红色节点对应为4-nodes 节点；特别的，为了满足此规定，对红黑树变色，这也是红黑树中唯一触发变色的条件）
- 整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同。（为一个平衡的2-3 树）
实现
原理：按照2-3 树的逻辑，从一个root开始，逐步添加所有的节点，这是生成树的基本步骤。可以假设每次添加前，树都是“平衡的”，加入一个node时，2-3树平衡化保证树的维持平衡（2node 变成 3-node 高度不变；3-node变为 4-node，变形后高度加一，将head向上归并，最后高度不变或最终root拆分，整颗树高度加一）
定义：
1、在二叉查找树的每一个节点上增加一个新的表示颜色的标记。该标记指示该节点指向其父节点的颜色。
2、新插入的节点使用红色链接。并约定红色节点向左倾斜。
3、左旋，右旋，和颜色转换如下图：（ H 表示触发动作的节点位置。该图表示以红色节点向左倾斜为前提的所有操作。）
在左转和右转的过程中，链接颜色不变。唯一触发改变颜色的条件是出现4-node 节点，即为出现两个子节点为红色节点。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/75357.html