二叉查找树、平衡二叉树、红黑二叉树简单概念

 二叉查找树（二叉排序树、二叉搜索树）：
性质：
        1.若其左子树非空，则左子树上所有节点的值都小于根节点的值；

        2.若其右子树非空，则右子树上所有节点的值都大于根节点的值；

        3.其左右子树都是一颗二叉查找树。

二叉查找树的特性：

        左子树  < 根节点  < 右子树，即二叉查找树的中序遍历是一个递增序列。

查询算法分析：

若二叉查找树为空，则查找失败，返回空指针
若二叉查找树非空，则将待查找关键字key与根节点的关键字T − > d a t a T->dataT−>data进行比较：
如果x = T − > d a t a x=T->datax=T−>data，则查找成功，返回查询到的当前节点T
如果x < T − > d a t a xdataxdata，则递归查找左子树
如果x > T − > d a t a x>T->datax>T−>data，则递归查找右子树 

平衡二叉树（AVL）：
定义：
        一棵空树或者具有以下性质的二叉排序树:它的左子树和右子树的高度之差（平衡因子）的绝对值不超过1 ，且它的左子树和右子树都是一棵平衡二叉树。

树的深度：从根节点开始（其深度为0）自顶向下逐层累加的；
树的高度：从子节点开始（其高度为0）自底向上逐层累加的。

平衡因子：此节点往下   左子树高度 - 右子树高度  = 平衡因子

一棵AVL树有如下必要条件：

1.  条件一：它必须是二叉查找树。
2. 条件二：每个节点的左子树和右子树的深度差至多为1。

红黑二叉树：
性质：
        红黑二叉树是一棵二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED，也可以是BLACK。

每条路径上的黑节点数目相同

红黑树保证最长路径不超过最短路径的2倍，因此近似平衡

 最短路径都是黑节点，最长路径就是一个红节点一个黑节点，最后黑节点相同时，最长路径正好是最短路径的两倍

插入节点：（默认颜色为红）

具体步骤：

1.根节点为null，直接插入新节点并将其颜色位置设置为黑色
2.根节点不为null，找到要插入新节点的位置
3.插入新节点
4.判断插入节点对全树颜色的影响，更新调整颜色

如果插入节点的父节点为黑色，则直接插入，若为红色，则需要判断