将二分查找法用数据结构来表示===》二叉搜索树
二叉树的节点删除情况：
1、删除叶子结点，直接删除即可
2、删除非叶子结点，但是该节点只有一个孩子结点的话，直接用孩子结点补上即可
3、删除有两个孩子的结点，找到该节点的前驱结点/后继结点，交换位置以后删除该节点即可！！
其定义是：
但是二叉搜索树如果遇到以下这种情况的时候效率很低，时间复杂度很高，以下是查找8的元素：
不符合我们使用二叉搜索树的初衷（类似于二分法，更高效的查找数据）===》引出了自平衡二叉搜索树，避免退化成链表查找（（AVL）/红黑树）

AVL（平衡二叉搜索树）：空树/每个节点的左子树深度与右子树深度之差的绝对值不超过1
红黑树在平衡性上没那么高要求，具体看红黑树的性质！

红黑树

1. 定义：是一种特殊的二叉搜索树，本质上是二叉搜索树，不过是特殊的，用于高效的查找数据的一种算法
2. 性质：

• 根节点一定是黑色的
• 每个节点不是红色就是黑色
• 不可能有连在一起的红色节点，也就相当于每个红色节点的子节点都是黑色的，所有的叶子结点都是黑色的，这里的叶子结点不是说没有子树的结点，而是对于每个为空NULL的结点，在红黑树中称为叶子结点，如下图所示，NULL对应的结点是黑色的
• 从一个结点到该节点的子孙结点的所有路径上包含相同数目的黑结点！！==》红黑树是接***衡的二叉树
  
  根据这个性质，构造出来的二叉搜索树是相对平衡的

3.为了满足以上的性质，需要对二叉搜索树进行以下几种操作（当然也可能是不做任何操作，根据二叉树插入节点的性质插入节点以后仍然满足红黑树的性质）

• 变色，即红变黑，黑变红

• 左旋
  
  

• 右旋
  
  
  以上是理论原理，那么什么情况下要进行上述的操作呢？
  红黑树中所有插入的点都默认是红色的！

• 变色的情况（假设插入一个值为6的结点）
  如下图所示，当前结点是红色，当前结点的父结点是红色，叔叔结点也是红色的时候，需要变色，进行变色的步骤是：
  第一步：将父结点与叔叔结点变成黑色，将父结点的父结点即爷爷结点变为红***r>第二步：将指针指向当前爷爷结点
  
  如上图，变色以后的树也不符合红黑树的性质，仍然有两个相连的红色结点，但是并不满足当前结点的父结点是红色，叔叔结点也是红色的前提条件，所以需要旋转
  ====》什么时候用左旋，什么时候用右旋呢？

• 左旋的情况
  当前结点是红色，当前结点的父结点是红色，叔叔结点是黑色（或者不存在的时候）的时候，当前结点属于右子树的情况，进行左旋，其中是以当前结点的父结点左右左旋的第一步结点，当前结点是第二步结点。左旋完成以后，当前结点指针指向的是上一个当前指针的父结点
  
  但是左旋完成以后（对应第二行的第一张图），对应的二叉搜索树仍然不满足红黑树的性质，其当前结点是红色，当前结点的父结点是红色，叔叔结点是黑色，但是当前结点是左子树的情况，所以还需要进行右旋操作

• 右旋的情况
  其当前结点是红色，当前结点的父结点是红色，叔叔结点是黑色（或者不存在的时候），但是当前结点属于左子树的情况，所以还需要进行右旋操作，相比于左旋而言，较为复杂，需要先将当前结点的父结点变为黑色，爷爷结点变为红色，然后将当前结点的爷爷结点作为右旋第一步的结点，当前结点的父结点作为第二步的结点，当前指针指向的是上一个当前结点的爷爷结点，右旋结果如上图第二行第二张图片所示。==》是一个红黑树

可以对照着四张图的那张图和以下的图去分析（更容易懂）：

注意：红黑树插入节点有两个步骤：
1、根据二叉搜索树插入节点
2、根据红黑树的性质调整树的结构以满足红黑树的性质
红黑树的部分源码：

• 红黑树中的结点定义

  class RBTNode//定义每个节点所包含的内容
  {
  public:
    RBTcolor color;    // 颜色
    T key;            // 关键字(键值)
    RBTNode *left;    // 左孩子
    RBTNode *right;    // 右孩子
    RBTNode *parent; // 父结点
    RBTNode(T val,RBTNode *l,RBTNode *r,RBTNode *p,RBTcolor col):key(val),left(l),right(r),parent(p),color(col){}
  };

• 左旋：

  void leftromate(RBTNode *x)//给定一个指针，指向左旋以该节点开始旋转的一个结点
  {
    RBTNode *y=x->right;
    if(x->parent)
    {
        x->parent->left=y;
        y->parent=x->parent;
    }
    else
        y->parent=x->parent;
    x->parent=y;
    x->right=y->left;
    if(y->left)
        y->left->parent=x;
    y->left=x;
  }

• 右旋：

void rightromate(RBTNode *x)//给定一个指针，指向右旋以该节点开始旋转的一个结点
{
    RBTNode *y=x->left;
    if(x->parent)
    {
        x->parent->left=y;
        y->parent=x->parent;
    }
    else
        y->parent=x->parent;
    x->left=y->right;
    if(y->right)
        y->right->parent=x;
    y->right=x;
    x->parent=y;
}

红黑树的删除步骤如下：（结点的度：即该节点所含子树的个数）
1、直接删除
查看需要删除的结点所处的位置，如果该节点是度为0的结点，直接删除即可，删除完以后的树仍然为红黑树
2、取代删除
查看需要删除的结点所处的位置，如果该节点是度为1的结点，直接用孩子结点取代即可，取代之后如果出现不符合红黑树的性质的话，按照上面插入结点的规则进行调整操作，直到满足红黑树性质为止
3、前驱/后继结点取代删除
查看需要删除的结点所处的位置，如果该节点是度为2的结点，将该节点的前驱结点或者后继结点与该节点进行交换，然后观察是否符合1/2的条件，如果不符合继续使用其结点的前驱/后继结点进行交换，直到满足1/2的条件，然后删除，当然，如果出现删除后不满足红黑树的性质的情况的话，按照上面插入结点的规则进行调整操作，直到满足红黑树性质为止