数据结构可视化网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
demo：https://github.com/lilingyan/take-TreeMap-apart
bst(二叉搜索树)
在插入数据均匀分布时，就是折半查找
二叉搜索树的定义
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 左、右子树也分别为二叉排序树；
- 没有键值相等的节点。
- 插入:
- 从根节点开始，递归比较大小，直至叶子叶子节点。
- 把新节点加上。
- 从根节点开始，递归比较大小，直至叶子叶子节点。
- 删除:
- 从根节点开始，递归比较大小，直至key相等。
- 如果该节点有两个孩子，则用后继节点的值替换它，然后删除后继节点(后继节点必然是叶子节点，执行c)
- 如果只有一个子节点，则把该节点的父节点和该节点的子节点相互指向(这样就没有指向该节点的了，就删除了)
- 如果是叶子节点，直接置空父节点指向改节点的指针
- 从根节点开始，递归比较大小，直至key相等。
avl(平衡二叉树)
BST在key值是线性的时候，就又变成一维的查找了(就是数组)，AVL树能极大的提高线性key的查询效率
平衡二叉树的定义
- 首先它是BST
- 左右子树高度差不超过1(递归)
平衡
自底向上，一层一层的平衡，直到根。
- 插入后情况
- 不需要调整
- 根节点或者左右子树高度差小于1
- 需要调整(左右子树高度差大于1)
- 左子树高的情况(2)
- case1: 插入节点是左子节点的左子节点
- 右旋父节点
- case2:
- 把自己左旋
- 把原父节点右旋
- case1: 插入节点是左子节点的左子节点
- 右子树高的情况(-2)
- 与上同理(镜像)
- 左子树高的情况(2)
- 不需要调整
- 删除后情况
- 不需要调整
- 根节点或者左右子树高度差小于1
- 需要调整(左右子树高度差大于1)
- 左子树高的情况(2)
- case1: 插入节点是左子节点的左子节点
- 当前节点右旋
- case1: 插入节点是左子节点的左子节点
- 当前节点右旋
- case2:
- 当前节点x左子节点左旋
- 当前节点右旋
- case1: 插入节点是左子节点的左子节点
- 右子树高的情况(-2)
- 与上同理(镜像)
- 左子树高的情况(2)
- 不需要调整
