平衡二叉树

平衡二叉树(AVL树)

为什么叫 AVL 树,因为他的发明者是 G.M.Adelson-Velsky & Evgenii Landis,根据科学家的英文名也称为AVL树。在1962年发表的论文 《An algorithm for the organization of information》 中公开了这一数据结构。

为什么要有平衡二叉树

二叉查找树在一定程度上可以提高搜索效率。但是,当原序列为有序时。构造的就是一颗倾斜二叉查找树。这时,二叉树退化成单链表,搜索效率降低为 O(n)O(n)

二叉查找树的查找效率取决于树的高度,因此保持树的高度最小,即可保证树的查询效率。

左右子树的高度相差不超过1的树为平衡二叉树

平衡二叉树

平衡二叉查找树:简称平衡二叉树

  1. 可以是空树。
  2. 如果不是空树,任何一个节点的左子树与右子树都是平衡二叉树,并且高度之差绝对值不超过1。

平衡因子

平衡因子:某节点的左子树和右子树的高度(深度)差即为该节点的平衡因子(BF,Balance Factor)。在一颗平衡二叉树中,节点的平衡因子只能是 0、1、-1。

失衡与调整

最小失衡树:在新插入的节点向上查找,一第一个平衡因子的绝对值超过1的节点为根的子树称为最小不平衡子树。也就是说,一颗失衡的树,是有可能有多颗子树同时失衡的。而这个时候,我们只需要调整最小的不平衡子树,就能够将不平衡的树调整为平衡的树。

旋转的目的是减少高度,通过降低整棵树的高度来平衡。

删除元素 & 添加元素都有可能造成树的失衡,需要进行调整

左旋

右子树高度高于左子树。

节点的右孩子替代此节点位置

右孩子的左子树变为该节点的右子树

节点本身变成右孩子的左子树

右旋

左子树高度高于右子树

节点的左孩子替代节点位置

节点的右子树变为该节点的左子树

节点本身变成左孩子的右子树

参考


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!