二叉树特性：
    1、某节点的左子树节点仅包含小于该节点的值
    2、某节点的右子树节点仅包含大于该节点的值
    3、左右子树也必须是二叉查找树
    4、顺序排列（有序）

    平衡二叉树：
    （查询效率相对于链表更快，相对于数组更慢，增删操作优于数组）
    image.png
    不平衡二叉树：
    （查询效率不高，类似于链表。解决方案：去除树顶优势，从而达到树平衡，衍生出了红黑树）
    image.png

    红黑树（Red-Black Tree RBT）特性：
    红黑树是一个自平衡（相对）的二叉树【并非绝对平衡】，树上的节点必须满足如下规则：
    1、每个节点要么是红色，要么是黑色
    2、根节点必须是黑色
    3、每个叶子节点【NIL】必须是黑色
    4、每个红色节点的子节点必须是黑色
    5、任意节点到每个叶子节点路径包含的黑色节点数必须一致（红色可以不一致，所以并非绝对平衡）

    image.png

    变化规则：
    1、recolor：根据规则重新定义每个节点的颜色
    2、rotation：旋转，树达到平衡的关键

    旋转规则图：
    1、当插入节点的父节点和父节点的兄弟节点都是红色，只需变色，不需旋转
    image.png
    image.png
    2、当插入节点的父节点的兄弟节点为黑色或者不存在，则需要旋转
    image.pngimage.png
    3、当插入节点的父节点在祖父节点的右侧，当前节点在父节点的左侧，先变色右旋，再左旋
    当插入节点的父节点在祖父节点的左侧，当前节点在父节点的右侧，先变色左旋，再右旋
    image.png