红黑树

• 左子树上所有结点的值均小于或等于它的根结点的值。
• 右子树上所有结点的值均大于或等于它的根结点的值。
• 左、右子树也分别为二叉排序树。

• 优点：
  比如我们要找节点10，算上根节点，一共找4次就能找到。也就是说，使用BST查找一个元素的最大查找次数等于树的高度。插入新节点也是如此，通过一层一层查找找到合适位置。
• 缺点：
  在数据递增或递减时，BST会不平衡，导致查找的性能退化成线性的。比如下面这样一棵BST，"左子树"成了线性链表了。
  
  

• 根节点是黑色，其他节点是红色或黑色；
• 每个叶子节点都是黑色的空节点（称为NIL节点）；
• 每个红色节点的两个子节点都是黑色，也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点；
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

（2）红黑树调整策略

• 变色：将红色节点变为黑色，或者把黑色节点变为红色，使该树重新符合红黑树的要求。
• 旋转：
  • 左旋转：左旋转使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
    
    
  • 右旋转：右旋转使得父节点被自己的左孩子取代，而自己成为自己的右孩子。
    
    

（3）★★如何向红黑树中插入一个新节点？

• 待删节点没有子节点，如节点1，直接删除即可。
• 待删节点有一个子节点，如节点2，将这个子节点(1)替代待删节点即可。
• 待删节点有两个子节点，如节点4，将待删节点与它中序遍历的后续节点(5)互换，然后删除此时新位置上的待删节点即可。

• 首先是待删节点X没有子节点的情况，待删节点可能是黑色也可能是红色：
  • 如果是红色的话，X的父节点一定是黑色且X没有兄弟，此时直接删除X就结束了；
    
  • 如果X是黑色的话，那么X一定有兄弟，如果兄弟是黑色，那么兄弟就没有孩子，此时删除X，需要把黑兄弟变红；
    
  • 如果兄弟是红色，那么兄弟就有俩黑色孩子，此时删除X需要旋转和变色（如最后一张图）。
    
• 其次是待删节点X只有一个子节点，由红黑树的性质，只有一个子节点的节点，一定是父(X)黑子红的情况，此时删除X需要用子节点替代X的位置，并变为黑色：
  
  
• 最后是最麻烦一种，也就是待删节点X有两个子节点，这两个子节点分为两红、两黑、一红一黑的3种情况：
  • 两红：删除X后需要用后继与X交换再删除现在的X，然后
  • 两黑：
  • 一红一黑：