5、结构,以达到对红黑树进行插入、删除结点等操作时,红黑树依然能保持它特有的性质(如上文所述的,五点性质)。树的旋转,分为左旋和右旋,以下借助图来做形象的解释和介绍:1.左旋如上图所示:当在某个结点pivot上,做左旋操作时,我们假设它的右孩子y不是NIL[T],pivot可以为树内任意右孩子而不是NIL[T]的结点。左旋以pivot到y之间的链为“支轴”进行,它使y成为该孩子树新的根,而y的左孩子b则成为pivot的右孩子。来看算法导论对此操作的算法实现(以x代替上述的pivot):1. LEFT-ROTATE(T, x) 1.1 y ← right[x] ▹
6、 Set y. 2.2 right[x] ← left[y] ▹ Turn y's left subtree into x's right subtree. 3.3 p[left[y]] ← x 4.4 p[y] ← p[x] ▹ Link x's parent to y. 5.5 if p[x] = nil[T] 6.6 then root[T] ← y 7.7 else if x = left[p[x]] 8.8 then left[p[x]] ← y 9.9
7、 else right[p[x]] ← y 10.10 left[y] ← x ▹ Put x on y's left. 11.11 p[x] ← y 2.右旋右旋与左旋差不多,再此不做详细介绍。 对于树的旋转,能保持不变的只有原树的搜索性质,而原树的红黑性质则不能保持,在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。至于有些书如STL源码剖析有对双旋的描述,其实双旋只是单旋的两次应用,并无新的内容,因此这里就不再介绍了,而且左右旋也是相互对称的,只要理解其中一种旋转就可以了。 三、红黑树