其实仔细来看2-3树好像是 B 树的一个特例,它规定了一个节点要么有一个 key 要么有两个 key。
这样一来就会发现他其实也会处在插入的时候出现分裂的情况,当一个节点需要插入的时候我们先让他插入,这时候可能出现一个节点有三个 key 的情况,我们就打出四个分支,然后我们把中间的那个 key 分裂到父节点,然后左右的 key 分别作为左右子节点。
这时候我们能够发现当且仅当我们的根节点分裂的时候我们的 2-3 树的高度才会真正的加一。这也是和 B 树的性质相似的。
2-3 树最好情况就是当所有的节点都是 3 key 节点的时候,这时候我们的树高度最小,而最坏情况自然也就是一个二叉树的时候。
红黑树我们可以把它看做为 2-3 树的变种,也就是说我们可以在 2-3 上进行一些改造生成对应的红黑树。一般来说我们就是将那些具有三个子节点的节点拆分成两个节点,key 大的那个作为根,小的那个作为左子节点,然后他们之间使用红色连接起来(用红色连接的意思就是父节点是黑的,子节点是红的),也就可以看出红黑树更偏向于左边。下面是一个具体的例子:
从第一个图到第二个,这个在什么情况下需要呢?当我们插入一个新节点的时候我们发现插入后就是图一的情况,这时候我们还原到 2-3 树我们发现因为 s 节点更大,所以 s 节点应该是根节点, e 节点应该是 s 节点的子节点才对。所以产生了这样的操作!
所以说,当我们插入一个节点的时候我们发现插入到了右边的节点了我们就需要左旋转进行调整。
右旋转刚和和左旋转相反。
颜色翻转就是
当红黑树是这种情况的时候我们会发现他对应的 2-3 树是有问题的,需要进行分裂,所以说这里的颜色翻转就是把他的子节点都表示为黑色,自己变成红色。
上面看到了关于红黑树的三个基本操作,这三个操作其实在我们插入的时候都是用的上的,并且重要的是在 AVL 树我们也可以仿照这种思想去完成平衡操作。
上面一般就是我们进行插入的时候会遇到的所有需要处理的情况。
我们的 AVL 树完全可以按照这个套路在接着写。