红黑树实验报告 71110325 向往.doc

红黑树实验报告
向往
实验目的
通过实践，加深理解红黑树的性质、特点，熟悉其相关操作，提高编程能力。
实验内容
实现红黑树。包括插入节点等基本操作。
实现将一百万个节点的红黑树写入硬盘，并从硬盘中恢复至内存的操作。
实验步骤
红黑树主要数据结构及其说明
1）红黑树节点类：RedBlackNode
数据成员：左右子节点的指针、父节点的指针、关键字、颜色
构造函数：默认构造函数会构造一个标志节点，带Key型参数的构造函数会构造一个关键字为指定参数的红色节点
2）红黑树类：RedBlackTree
数据成员：其根节点
三种主要操作：插入节点，写入文件，从文件中读取。
void insertNode(Node n)，void saveToFile()，void loadFromFile()


2、插入节点的实现
我们首先以二叉查找树的方法增加节点并标记它为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。） 下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样，我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。（参考自维基百科）
通过下列函数，可以找到一个节点的叔父和祖父节点:
placeNode函数
将新节点的关键字与树根节点关键字比较，如果关键字小于等于树根节点就将新节点递归地插入左子树，否则就递归地插入右子树。当碰到某个子树树根为NULL时，就说明已经到达了原树的叶节点，直接安置新节点在此处即可。t为树根节点，tPrt为t的父节点，n为要插入的节点。在调用这个函数插入新节点时，只要写成placeNode(root, NULL, n) 即可。

调整树以保证红黑树的性质不被破坏。（参考自维基百科）
。
情形1: 新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑节点数目增加一，性质5符合。
情形2: 新节点的父节点P是黑色，所以性质4没有失效（新节点是红色的）。在这种情形下，树仍是有效的。性质5也未受到威胁，尽管新节点N有两个黑色叶子子节点；但由于新节点N是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个性质。
情形3: 如果父节点P和叔父节点U二者都是红色，(此时新插入节点N做为P的左子节点或右子节点都属于情形3,这里右图仅显示N做为P左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点G的父节点也有可能是红色的，这就违反了性质4。为了解决这个问题，我们在祖父节点G上递归地进行情形1的整个过程。
情形4: 父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点。在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色; 接着，我们按情形5处理以前的父节点P以解决仍然失效的性质4。注意这个改变会导致某些路径通过它们以前不通过的新节点N或不通过节点P，但由于这两个节点都是红色的，所以性质仍有效。
情形5: 父节点P是红色而叔父节点U是黑色或缺少，新节点N 是其父节点的左子节点，而父节点P又是其父节点G的左子节点。在这种情形下，我们进行针对祖父节点G 的一次右旋转; 在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G 的父节点。我们知道以前的祖父节点G是黑色，否则父节点P就不可能是红色。我们切换以前的父节点P和祖父节点G的颜色，结果的树满足性质4。性质5也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G ，现在它们都通过以前的父节点P。在各自的情形下，这都是三个节点中唯一的黑色节点。
将节点右旋或左旋的两个函数
5） 最后完成insertNode函数
5）最终的插入函数
写入文件与读出文件的实现
写入文件时，非递归前序遍历红黑树，基本步骤是：
1）根节点入栈 2）从栈中取出一个节点，写入文件。 3