0%

平衡二叉查找树（AVL）

发表于 分类于

文章字数：427,阅读全文大约需要1分钟

和红黑树相比旋转操作更多，频繁插入删除的情况下红黑树更优

概念

  1. 二叉查找树
  • 任意节点，若左子树不为空，则左子树上所有的节点值都小于它的根节点值
  • 人员节点，若右子树不为空，则右子树上所有节点均大于它的节点值
  • 左右节点都可以单独当做二叉查找树
  • 利用二分查找法，查找的最大次数等于树的高度
  • 在极端情况下，数可能会退化成链表。
  1. 平衡二叉查找树（AVL）
  • 具有二叉查找树所有的优点
  • 每个节点的左子树和右子树高度差最多为1
  • 每次插入后如果不满足条件2，则需要通过若干左旋右旋操作恢复平衡

需要平衡的类型

  1. 左-左型
  • 倾斜于左的情况，此时需要进行右旋。
  • 即顺时针旋转两个节点，使父节点被自己的左孩子渠道，自己成为右孩子
    例1
    1
    2
    3
    4
    5
           9
          /         右旋       5
        5         ====>      /   \
      /                    4      9
    4
    例2
    1
    2
    3
    4
    5
    6
    7
             6                         4
            /  \                      /  \
          4      9                  3     6
         /  \           右旋      /      /  \
       3      5         ====>   2       5    9
      /
    2
  1. 右-右型
  • 倾斜于右的情况，和左-左型刚好相反

  1. 右-左型

    1
    2
    3
    4
    5
    7                                   7                      9
     \    先对10右旋，变成右-右型         \    再左旋节点7     /  \
      10            ======>                9     =====>      7    10
     /                                      \
    9                                        10

  2. 左-右型

  • 整体倾斜于左，但是新增的节点倾斜于右
  • 和右-左型处理刚好相反