首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》解决方案

关灯直达底部

在一棵红黑树中查找和在其他任何二叉查找树中查找没什么不同。例5-9是在红黑树中进行查找的代码。从根节点开始,我们将会检查每一个节点,如果键值小于左子节点,那么我们准备开始遍历左子树,否则遍历右子树。

例5-9:查找的Java代码

图 5-11 添加键值14的元素到红黑树所需要的4步

红黑树算法的关键是在于不断地插入和删除操作时保持红黑树的性质。我们在这里描述插入的过程,删除的过程是非常复杂的,我们将在代码中实现这个过程,你可以在algs.model.tree.BalancedTree类中阅读相关代码。

当我们希望在图5-10的树中插入14时,一个值为14的新节点将会成为值为13的节点的右子节点(图5-11的第一步)。一旦插入,红黑树的性质就不能继续保持,所以需要进行调整。在第二步中,节点的颜色会被更新,以确保不违反红黑树的性质4。在第三步中,树将会右旋以确保不违反红黑树的性质5。最后,在第四步中,节点的颜色又一次被修改,以满足红黑树的性质4。

当重构树时,一个基本的操作是围绕一个节点进行旋转。我们修改树中的指针来加速这个旋转。图5-12给出了围绕一个节点左旋或者右旋的结果。左子树可以围绕节点左旋来得到右子树。类似地,你也可以让右子树左旋来得到左子树。

图 5-12 红黑节点旋转

你可以看到,为了能够进行旋转,红黑树中节点的结构必须包含父节点指针。例5-10是执行左旋的代码,执行右旋的代码基本上差不多。你可以在(Cormen等,2001)中找到左旋和右旋执行的细节分析。

例5-10:左旋的Java实现

注意旋转操作维护的是二叉查找树的性质,因为节点的序并没有改变。一旦新的节点插入到红黑树中,树将会自动调整以保持红黑树的性质4和性质5。