数据结构-树型结构
度：节点拥有的子节点的数量称为节点的度数（Degree），而树的度数是所有节点中度数的最大值。
树的种类：
1、二叉树
    二叉树中，任意的一个节点的度必须小于或等于2
    节点：在树结构中，每一个元素称为节点
    度：每一个节点的子节点的个数。
2、二叉查找树
    二叉查找树也叫【二叉排序树】，也叫【二叉搜索树】
    每一个节点上最多有两个子节点。
    左子树上所有节点的值都小于根节点的值
    右子树上所有节点的值都大于根节点的值
二叉查找树添加子节点的时候，要求：
    比父节点小的放左边
    比父节点大的放右边
    一样的不放
3、平衡二叉搜索树 AVL树
    要求二叉树的左右子树的高度差不能超过1。
    要求任意的节点的左右两个子树都是一棵平衡二叉树
    平衡二叉树旋转
        旋转触发的时机：当添加一个节点之后，这棵树不再是平衡二叉树的时候，就会进行旋转。
    二叉树的旋转：
    左旋：
        把根节点右侧往左拉，原来的右子节点变为新的父节点，并且把多余的左子节点让出，
        给降级的根节点当右子节点。

    右旋：
        就是把根节点左侧往右拉，原来的左子节点变为新的父节点，并且把多余的右子节点让出，
        给降级的根节点当左子节点。
    触发平衡二叉树旋转的四种情况：
    左左：
        当根节点左子树的左子树有节点插入，导致二叉树不平衡。
        旋转方式：直接对整体进行右旋即可
    左右：
        当根节点左子树的右子树有节点插入，导致二叉树不平衡。
        旋转方式：先在左子树对应的节点位置进行左旋，然后再对整体进行右旋
    右右：
        当根节点右子树的右子树有节点插入，导致二叉树不平衡。
        旋转方式：直接对整体进行左旋即可
    右左：
        当根节点右子树的左子树有节点插入，导致二叉树不平衡。
        旋转方式：先在右子树对应的节点位置进行右旋，然后再对整体进行左旋
4、红黑树
    每一个节点可以是【红】或者是【黑】
    红黑树不是高度平衡的，它的平衡是通过自己的【红黑规则】来实现的
红黑规则：
    1、每一个节点要么是红色的，要么是黑色的。
    2、根节点必须是黑色的。
    3、如果一个节点没有子节点(叶子节点)或者没有父节点(根节点)，
    那么该节点相应的指针属性值为Nil，这些Nil是为叶子节点，每个叶子节点是黑色的。
    4、如果一个节点是红色的，那么它的子节点必须是黑色的(不能出现两个红色节点相连的情况)
    5、每一个节点，从该节点开始到后面的所有叶子节点的简单路径上，都要包含相同个数的黑色节点。

添加节点的时候，新节点的颜色可以是红色也可以是黑色。建议默认的颜色是红色，可以提高效率。

当我们添加节点后，为了保持红黑规则：
    根节点位置，建议直接设置为黑色。
    非根节点位置，
        |-如果父节点是黑色，那么不用做任何操作，子节点默认红色就行。
        |-如果父节点是红色，
            |-叔叔节点也为红色
                把父节点设置为黑色，把叔叔节点设置为黑色
                把祖父节点设置为红色
                如果祖父节点是根节点，就再次把根节点设置为黑色
            |-叔叔节点为黑色
                把父节点设置为黑色
                把祖父节点设置为红色
                再以祖父节点为支点进行旋转