数据结构-AVL树学习笔记（转）

数据结构可视化网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
demo：https://github.com/lilingyan/take-TreeMap-apart

bst(二叉搜索树)

在插入数据均匀分布时，就是折半查找

二叉搜索树的定义

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 左、右子树也分别为二叉排序树；
4. 没有键值相等的节点。

• 插入:
  • 从根节点开始，递归比较大小，直至叶子叶子节点。
    1. 把新节点加上。
• 删除:
  • 从根节点开始，递归比较大小，直至key相等。
    1. 如果该节点有两个孩子，则用后继节点的值替换它，然后删除后继节点(后继节点必然是叶子节点，执行c)
    2. 如果只有一个子节点，则把该节点的父节点和该节点的子节点相互指向(这样就没有指向该节点的了，就删除了)
    3. 如果是叶子节点，直接置空父节点指向改节点的指针

avl(平衡二叉树)

BST在key值是线性的时候，就又变成一维的查找了(就是数组)，AVL树能极大的提高线性key的查询效率

平衡二叉树的定义

1. 首先它是BST
2. 左右子树高度差不超过1(递归)

平衡
自底向上，一层一层的平衡，直到根。

• 插入后情况
  • 不需要调整
    1. 根节点或者左右子树高度差小于1
  • 需要调整(左右子树高度差大于1)
    1. 左子树高的情况(2)
       • case1: 插入节点是左子节点的左子节点
         1. 右旋父节点
       • case2:
         1. 把自己左旋
         2. 把原父节点右旋
    2. 右子树高的情况(-2)
       • 与上同理(镜像)
• 删除后情况
  • 不需要调整
    1. 根节点或者左右子树高度差小于1
  • 需要调整(左右子树高度差大于1)
    1. 左子树高的情况(2)
       • case1: 插入节点是左子节点的左子节点
         1. 当前节点右旋
       • case1: 插入节点是左子节点的左子节点
         1. 当前节点右旋
       • case2:
         1. 当前节点x左子节点左旋
         2. 当前节点右旋
    2. 右子树高的情况(-2)
       • 与上同理(镜像)