红黑树的一些概念

普通的二叉树作为数据存储有重要的优势，可以快速的找到一个给定的关键字，数据项，并且可以快速的插入

和删除数据项。其他的数据存储结构，数组有序数组链表在执行这些操作的时候却很满。

 

但是。遗憾的是二叉树搜索树有一个很麻烦的问题就是：如果树中插入的是随机数据，那么执行的效果很好。

但是，如果插入的是有序的数据或者逆序数据，速度就变的特别慢。因为当插入的数据有序时，二叉树就是非平衡了，而对于非平衡树，

它的快速查找 删除 插入能力就没有了。

 

红黑树就是增加了一些特点的二叉搜索树。

 

还有其他的一些方法来保持树的平衡的。

 

本章将要讨论的在红黑树中插入方法和在已经讲过的在其他数据结构中的方法有点不同，但是理解红黑树很重要。因为这一点，也因为有大量

的对称情况，实际的代码要比人们想象的长而且复杂。因为通过研究代码学习算法十分困难。所以，在这一章中没有程序代码。

 

平衡二叉树

 

不平衡树的效率--- N

我们在插入的时候，一般的二叉树如果遇到有序的数据 比如 1 2 3 4 5 6 7 8 9 那么1 作为根节点，剩余就是成了右节点，

其实就是我们想的那种链表了，所以查找的话 就是要 n的时间复杂度了，而不是logN的情况。

这是极度不平衡的树

 

一般不平衡球情况效率

对于随机数据的实际数量来说，一颗树特别不平衡的情况是不大可能的。但是，可能会有一小部分有序数据

使树的部分非平衡。搜索部分非平衡树的时间要在N 到 logN之间 ，这要看树的不平衡度要看了

 

 

平衡的补救

为了能用较快的时间logN来搜索一颗树，需要保证树总是平衡的（或者至少大部分是平衡的），这就是说树中的每个节点在它

左边后的后代数目和右边的后代数目要大概的相等。

   红黑树的平衡是在插入的过程中（删除时也是，但是暂时忽略这个问题）取得的。对一个要插入的数据项，插入的时候要检查下不会补破坏

   树的一定的特征。如果破坏了，程序就要去纠正，根据需要更改树的结构，通过维持树的特征，保持了树的平衡。

 

   红-黑树的特征

   这种树有什么好神奇的呢？有两个特征就是 一个简单，一个比较复杂：

   节点都有颜色

   在插入和删除的过程中，要遵守保持这些颜色的不同排列的规则

 

 带颜色的节点

 在红黑树中，每一个节点或者是黑色的或者是红色的，也可以是任意的两种颜色的。实际上，所说的颜色是任意的比方。可以用其他的类似的

 方法来表示。比如可以说每一个节点不是深色的就是浅色的。不过对于颜色就是偏于标记。在节点类中增加一个数据字段，可以是boolean类型的

 用来表示颜色。

 

 节点的红黑特征通过节点编辑的颜色来表示的。

 

 

 红黑树的规则

 

 当插入（或者删除）一个新的节点时，必须要遵守一定的规则，他们被称为红黑规则。如果遵守这些规则，树就是平衡的。下面简要的介绍下这些规则

 1.每一个节点不是红色就黑色（）

 2.根总是黑色的

 3.如果节点是红色的，则它的子节点必须是黑色的

 4.根到叶子节点或者空节点的每条路径，必须包含相同数据的黑色的节点

 

 规则4中的（空子节点）是指非叶子节点可以接子节点的位子。换句话说，就是一个有右子节点的节点的可能接左节点的位子，或者是有左子节点

 的节点的可能接右子节点位子。

        仔细的说明：

       在从根到叶子点的路径上的黑色节点的数据叫做黑色高度。规则4的另一种陈述方式是所有从根到叶子节点路径上的黑色高度必须相同。

   这些规则可能使人一头雾水。看不清楚这些怎么能使得一颗树平衡，然而他们做到了；某些很聪明的人发明了他们。请把这些抄在变迁上，

   并且经常的看

 

   重复的关键字

   如果有多余一个数据项的关键字的值相同，将会出现什么情况呢？这给红黑树提出了一个小问题。把有相同关键字的数据项分配到其他也由相同关键字

   数据项的两则是很重要的。这也就是说，如果关键子的序列为50 50 50 要把第二个50放到第一个50的右边，并且把第二个50放到第一个50的左边，否则

   树将不平衡了

    在插入算法中，用某种随机的过程处理相同关键子节点的分配问题。但是，如果要找到所有相同的关键词，插入过程就变的更加复杂了。

目前我们学习的时候不考虑关键词是一样的