算法导论 - 实验四 常见平衡树的实现与比较

实验四 常见平衡树的实现与比较

1. 问题描述:

代码实现红黑和AVL树

2. 算法原理: a) 树的旋转知识

当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。

为了保持红黑树的性质，我们可以通过对树进行旋转，即修改树种某些结点的颜色及指针结构，以达到对红黑树进行

插入、删除结点等操作时，红黑树依然能保持它特有的性质（如上文所述的，五点性质）。

树的旋转，分为左旋和右旋，以下借助图来做形象的解释和介绍：

i. 左旋

如上图所示：

当在某个结点pivot上，做左旋操作时，我们假设它的右孩子y不是NIL[T]，pivot可以为树内任意右孩子而不是NIL[T]的结点。

左旋以pivot到y之间的链为“支轴”进行，它使y成为该孩子树新的根，而y的左孩子b则成为pivot的右孩子。

ii. 右旋

右旋与左旋差不多，再此不做详细介绍。

b) 红黑树插入、删除操作的具体实现

i.

插入操作各种可能的情况

情况1：插入的是根结点。

原树是空树，此情况只会违反性质2。 对策：直接把此结点涂为黑色。

情况2：插入的结点的父结点是黑色。

此不会违反性质2和性质4，红黑树没有被破坏。 对策：什么也不做。

情况3：当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色。 此时父结点的父结点一定存在，否则插入前就已不是红黑树。

与此同时，又分为父结点是祖父结点的左子还是右子，对于对称性，我们只要解开一个方向就可以了。

在此，我们只考虑父结点为祖父左子的情况。

同时，还可以分为当前结点是其父结点的左子还是右子，但是处理方式是一样的。我们将此归为同一类。

对策：将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法。

针对情况3，变化前（图片来源：saturnman）[插入4节点]：

变化后：

情况4：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子 对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。 如下图所示，变化前[插入7节点]：