1. 什么是BST
   二叉搜索树——
   二叉树—-含有一个值（或者key+卫星数据） ，并且包含最多两个左右子节点（一棵树也叫节点，如果该树没有左右节点，则成该树为叶子节点），每个节点又是一个二叉树。二叉搜索树——-所有左侧节点的值小于当前节点的值，所有右侧节点的值小于当前节点值的二叉树。

2.树T的左旋转和又旋转
左旋转——左(x)变子，移动y的左子为x的左子
右旋转——右(y)变子,移动x的右子为y的右子
3.红黑树
红黑树定义
1). 任一节点要么是红色,要么是黑色。
2). 根节点为黑色。
3). 所有的叶节点(NIL节点)为黑色。
4). 如果一个节点为红色,则它的两个子节点都是黑色。
5). 对任一节点,从它出发到所有叶子节点的路径上包含相同数量的黑色节点。
红黑树特点：最高高度（搜索复杂度为2lg(n+1))
红黑树—-没一个红节点可以和他的父节点组合成一个新的节点，从而形成2-3-4树，降低高度。所以我们尽可能的染成红色—-如下：

           [black 5]
          /         \
      [red 3]     [black 6]
     /       \
[black 2] [black 4]

组合后：

    [3 | 5]
   /   |   \
 [2]  [4]  [6]

4.红黑树插入z
a. z= root，直接染黑
b. z.uncle = red ,父节点recolor（反向color）
c. z.uncle =black（三角形） 旋转父辈
d. z.uncle = black(line)，旋转爷爷辈，recolor

5.什么是AVL
一种特别的平衡树，所有的sub tree 的平衡因子绝对值<=1
原理：局部平衡，达到总体平衡