红黑树和平衡二叉树的优缺点,红黑树为什么是平衡二叉树

预防针：红黑树本来就是基本算法中的难点，所以看此文时建议先有点预备心理或知识铺垫，没接触过RBT而直接看此文的话，绝对懵逼。

为了数据的查询跟增删方便，系统引入了二叉查找树，它具有左节点 < 根节点 <右节点 的属性，

但是这种设定跟数据的插入顺序有很大关系，比如你插入的是1234，二叉查找树会退化为链表。

为了避免链表结构的出现，研究者们又提出了平衡二叉树跟红黑树。平衡二叉树要求任意一个节点的左深度跟右深度差值绝对值不能大于1，如果插入后超过了1会通过左右各种旋转来更改连接的变化，最终实现左右深度差不大于1的这个要求。

平衡二叉树的深度要求太过完美，当涉及大量增删时，可能会太多时间用在调节平衡上，为了平衡投入跟产出比，又设计了红黑树。

红黑树算是一个比较复杂的数据结构了，除非你面字节，可能让你手写红黑树。一般情况下你只要说出红黑树构造的五大背后逻辑，展现你对底层数据结构的深度跟广度即可。

本文不会着重说红黑树的增删过程，因为你百度看下权威教程或源码，然后跟着追踪就知道大致流程了，本文会说下红黑树为何如此设计，它跟2-3树有啥联系。

为了保证查找树的平衡性，需要一些灵活性，因此我们允许树中的一个结点保存多个键。

1. 2结点：含有一个键和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
2. 3结点：含有两个键和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。
3. 4节点：含有三个键和四条链接，大致的思路跟3节点类似。需注意在2-3树中，4节点是短暂存在的，会被转化为2节点或3节点。

要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中的任何一个相等，查找命中。否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中，可以发现跟简单的二叉树查找类似。

要在2-3树中插入一个新结点，我们可以和二叉查找树一样先进行一次未命中的查找，然后把新结点挂在树的底部。但这样的话树无法保持完美平衡性。使用2-3树的主要原因就在于它能够在插入之后继续保持平衡。

1. 如果未命中的查找结束于一个2结点：只要把这个2结点替换为一个3结点，将要插入的键保存在其中即可。
2. 只有一个3结点的树，向其插入一个新数据：此时我们可以创建个临时4节点，然后将其转化为由3个2节点组成的2-3树