小引——2-3树
二叉查找树中,每个结点上有一个键和两个链接,我们称这种结点为2-结点。所以,有着两个键和三个链接的结点我们称之为3-结点。由2-结点和3-结点构成的树称为2-3树。
2-3树和上一篇说的普通二叉查找树最大的不同就是,它可以保持树的平衡,从而避免了二叉查找树的最坏情况的出现,守住了对数级别操作的底线,通过的办法就是自下向上生长。
查找很简单,跟二叉查找树是类似的,以上图为例,查找8的话,首先跟根节点13比较,8小于小于13,于是去左子树中查找,8又大于6而小于9于是去这个结点的中子树中查找,命中。
插入是非常重要的一步,正是在插入上边体现了2-3树的自下向上生长,保持了树的平衡。也因此,插入要复杂一点点,我们分情况讨论:
原本只有一个根结点,其中存了两个键2和9,插入5之后最终有了三个结点,并且树的高度增长了1,新插入的5成为了新的根节点,自下向上的生长使得新树任然保持了平衡。
2-3树作为一种概念,而红黑树便是它的实现。2-3树为了保持树的平衡性出现了三种结点,而红黑树中只有一种结点,看起来就是普通的二叉查找树。只不过通过对红黑结点进行变色,旋转来使得每一个红黑树都可以有一个与之对应的2-3树,从而拥有2-3树的性质。总之,红黑树的基本思想就是用标准的二叉查找树来表示2-3树,这样我们不需要定义各种不同的结点,只需要给每个结点增加颜色的属性以及旋转变色的动作就可以实现一种高效的二叉查找树。如图2-3树和与之对应的红黑树:
将红线拉平是为了更清楚的看出二者的对应关系,其实红黑树就是一个有颜色的二叉树,将拉平的红线还原:
红黑树中的结点有两种颜色,红色和黑色。由红色链接指向的结点是红结点,黑色链接指向的结点是黑结点。结点了有了颜色之分,为什么链接也有颜色呢?着实还是为了模拟2-3树,2-3树中的3-结点就是通过红色链接在红黑树中实现的。由红色链接连起来的两个2-结点,构成一个3-结点。
为了减少可能出现的情况,我们只允许出现红色左链接,而不允许红色右链接以及连续红色链接的出现。但是当我们进行某些操作之后,这两种我们不允许的状况就会出现,我们就需要进行旋转操作。
左旋转红连接,6和9的结点颜色发生变化,>6&&<9这个子树的父结点发生变化,从而红色右链接转换为红色左链接。
如果出现如图情况就需要进行颜色变换,将自己的两个红色链接变为黑色链接,并将自己由黑变红也就是将指向自己的链接由黑变红。
红黑树的查找就是二叉查找树中的查找,完全类似。
为了保证树的平衡,总是用红色的链接指向新增的结点,对应到2-3树里边就是总是在结点内部新加键而不是新增一个结点。
右插入
新键最小(先右旋上层红链接,再变色)
新键介于两者之间(先左旋下层红链接,再右旋上层红链接,再变色)
红黑树是第一种能够同时实现高效的查找、插入和删除操作的数据结构。今天我们介绍了最简单易懂的部分,并且规定了不准出现右红色链接,也就是对应的2-3树中不会出现4-结点,而现实中这种情况是可以存在的,只不过代码实现要更复杂一些。还有红黑树的删除,以及每种操作的代码实现,都留给未来的那篇文吧。