"""
二叉搜索树
    可以为空也可以不为空，左子树的值小于其根节点的值，右子树的值大于其根节点的值，所有的左右子树分别形成另外的
    二叉查找树
    find按照大小进行查找
    最大值，就是最右节点
    最小值 就是最左节点

    插入和查找几乎相同的找找找就行了
    二叉搜索树的删除如果删除的节点左节点为空，
        那么右节点直接完全替换成这个被删除的节点
    如果有左节点
        那么寻找该节点右子树的最左节点替换成该节点，同时如果该节点右子树的最左节点有右节点，那么右节点代替最左节点

    AVL树和红黑树其实都是二叉搜索树，在时间复杂度的指标上没有区别区别就在于维持平衡性上的方法不同，但是从根本上来讲
    处理平衡性也就是两种基本操作
        右旋      5   右旋之后成为     4                左旋      5                左旋之后成为     6
                4                   3   5                          6                             5  7
              3                                                      7
    每一个节点都封装了一个左右树的高度的值，从一个被插入节点向上找找到第一个不平衡的节点然后进行旋转就行了
                                        3
                    2(左高度为2右高度为0 不平衡了从这里开始进行旋转)       4
                1(左高度都为1右高度为0)
            0(这里我们插入0 高度为左右高度都为0)
    AVL树  保证左右之间高度相差不超过1
        左右旋  就是左子树插入了右节点不平衡   结果就是将i k进行旋转 旋转成RR型然后按照RR型进行处理详情见下面


        LR型
        左右旋    n        先对i进行左旋         n   再对 n进行右旋   k
               i                               k                   i   n
                 k                            i
            右左旋就是将新的数据插入到左孩子的右子树上  就是将i k进行旋转 旋转成LL型然后按照LL型进行处理


满二叉树
    叶子节点都在同一层并且除了叶子节点以外所有节点都有两个子节点
完全二叉树
    叶子结点上面是满二叉树，然后叶子结点从左向右紧密排列，不能出现空缺，可以不满
平衡二叉树
    对于任意节点左右子树高度相差不超过1 AVL树
    平衡二叉树的旋转
        左左旋转
                1 2 3(根)        2
                            1       3
        右右旋转
            1(根)   2   3          2
                                1      3
        左右旋
            2 1 3(根)            2
                            1         3
        右左旋
            1(根) 3 2            2
                            1           3

红黑树
    只有红色和黑色两种节点
    根节点与叶节点都是黑色的  对于所有的没有子节点的叶子结点我们自己添加一个叶子结点为空指针
    红色节点的父节点是黑色的
    一个节点x的所有到叶子结点的黑高度长度一致
    每个节点的黑高度是 不包括自己的子节点到叶子结点的黑节点的数量
    长链不能比短链长度超过一倍  例如一条链全是黑色的(短链) 一条链黑红交替(长链)
跳表
    有正反两个概率分别是0.5  （有一个额外计数  我自己加的其实没有）
    每有一个数进来就进行一次概率判断如果到反面就直接结束 按照额外计数来确定该数据在那层
    如果在正面就额外计数+1  继续概率判断
"""