红黑树的简介及特点说明

红黑树示意图

红黑树的简介

红黑树是一种含有红黑结点并能自平衡的二叉查找树
红黑树需满足以下特性:

 特性1:
    每个节点要么是黑色，要么是红色。
 特性2：
    根节点是黑色。
 特性3：
    每个叶子节点(NIL)是黑色(注意事项，此处的叶子节点,指为空(NIL或NULL)的叶子节点)
 特性4:
     每个红结点的两个子结点一定都是黑色 
 特性5:
     任意一结点到每个叶子结点的路径都包含相同数量的黑结点。
 
  特性5.1:
      如果一个结点存在黑子结点，那么该结点肯定有两个子结点

红黑树如何自平衡呢?

红黑树能自平衡，依靠以下三种操作:
    左旋、右旋和变色
 
左旋:
   以某个结点作为支点(旋转结点)
    其右子结点变为旋转结点的父结点,
	右子结点的左子结点变为旋转结点的右子结点,
	左子结点保持不变

右旋:
    以某个结点作为支点(旋转结点)
	 其左子结点变为旋转结点的父结点,
	 左子结点的右子结点变为旋转结点的左子结点,
	 右子结点保持不变

变色:
   结点的颜色由红变黑或由黑变红。