红-黑树

红-黑树的由来：

• • 二叉搜索树是一种非常好的数据存储结构，它可以快速地查找到指定关键值的数据项，并且可以快速的查找和删除指定的数据项。平衡二叉搜索树   的查找指定关键值数据项的时间复杂度是O(logN)
  • 但是，二叉搜索树只是在插入的数值序列是随机排列的时候效果较好，如果插入的数值不是随机排列的（如数据按照降序或者升序排列时），那么依次插入这些数值后所得的二叉搜索树就会是不平衡的，不平衡的二叉搜索树中指定关键值的数据项的查找、删除、插入速度都会变慢。
  • 最极端的不平衡二叉搜索树是由升序或者降序序列中的元素依次插入二叉搜索树中得到的，这种二叉搜索树只有左子树或者只有右子树，相当于链表。数据的排列是一维的，而不是二维的。这时特定关键值数据项的查找，时间复杂度是O(N)
  • 但是一般的不平衡二叉搜作树都是部分不平衡，所以查找特定关键值数据项的时间复杂度在O(logN)和O(N)之间,这取决于树的不平衡程度
  • 为了解决上述问题（二叉搜索树不平衡的问题）　　，特地引入红-黑树。
  • 红-黑树是在插入以及删除一个数据项的时候，都要遵循一定的规则，这样一来不管你的数据序列是怎样的，都能保证所得的二叉搜索树是平衡二叉搜索树。

红-黑树的定义：

　　　　概述：红-黑树是改进的二叉搜索树，只要保证插入和删除一个新的节点时都满足红黑树的颜色规则，就可以保证操作后所得的二叉搜索树是平衡的。

　　　　　　　当新插入或者删除一个节点之后，如果不再满足红黑树的颜色规则了，就需要执行“旋转”操作，使其重新满足红黑树的颜色规则（也即，遇到违反规则的节点时需要通过旋转操作使得非平衡的二叉搜索树重新变成平衡的二叉搜索树）

　　　　红-黑树的颜色规则：

• • • 

 

　　　　红-黑树中的旋转：

红-黑树的编程实现：

　　　　插入函数（插入新节点）：

• • • 编程思路
    • Java实现实例

　　　　删除函数（删除某个节点）：

• • • 编程思路
      • 删除一个节点会比插入一个新的节点还要复杂，所以一般情况下程序员都不会真的删除相应的节点，而是给相应的节点加上一个“”已删除“”标记，使得后面再去访问该节点时显示为不存在即可。　　
    • Java实现实例