红黑树的介绍和实现(一)

一、红黑树（Red-Black Tree）是二叉搜索树（Binary Search Tree）的一种。二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后）。这种低效产生的原因是树没有维持一定的平衡性，要提高搜索效率，就要想办法来维持树左边的平衡，也就是要尽时降低树的高度，可行的做法就是用一些策略在每次修改树的内容之后都调整树的结构，使之满足一定的平衡条件。其中一种满足一定平衡条件而且目前应用广泛的是红黑树。它可以在每一次插入或删除节点之后都会花O（log N）的时间来对树的结构作修改，以保持树的平衡。而红黑树的查找方法与二叉搜索树完全一样，也能够在O(log N)时间上完成。而红黑树的插入和删除节点的的方法只是在原二叉搜索树搜索和删除算法之后经过一定的过程来维持红黑树的性质不变。

红黑树的每个节点上的属性除了有一个key、3个指针：parent、left、right以外，还多了一个属性：color。它只能是两种颜色：红或黑,当然也可以再加一些以key来索引的数据。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下5点性质：

1. 每个节点是黑色的或是红色的。

2. 根节点是黑色的。

3. 空节点是黑色的（红黑树中，根节点的parent以及所有叶节点left、right都不指向NULL，而是指向一个定义好的空

补充：软件开发 , C语言 ,