【C语言】平衡二叉树

AVL树简介Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树(Self-Balancing Binary Search Tree,简称平衡二叉树)。平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉排序树:它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。一棵AVL树有如下必要条件: • 条件一:它必须是二叉查找树。• 条件二:每个节点的左子树和右子树的高度差至多为1。图一中左边二叉树的节点45的左孩子46比45大,不满足二叉搜索树的条件,因此它也不是一棵平衡二叉树。
右边二叉树满足二叉搜索树的条件,同时它满足条件二,因此它是一棵平衡二叉树。 左边二叉树的节点45左子树高度2,右子树高度0,左右子树高度差为2-0=2,不满足条件二;
右边二叉树的节点均满足左右子树高度差至多为1,同时它满足二叉搜索树的要求,因此它是一棵平衡二叉树。AVL树的查找、插入、删除操作在平均和最坏的情况下都是O(logn),这得益于它时刻维护着二叉树的平衡。如果我们需要查找的集合本身没有顺序,在频繁查找的同时也经常的插入和删除,AVL树是不错的选择。不平衡的二叉查找树在查找时的效率是很低的,因此,AVL如何维护二叉树的平衡是我们的学习重点。  AVL树相关概念1. 平衡因子:将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)。
    在图二右边的AVL树上:
    节点50的左子树高度为3,右子树高度为2,BF= 3-2 = 1;
    节点45的左子树高度为2,右子树高度为1,BF= 2-1 = 1;
    节点46的左子树高度为0,右子树高度为0,BF= 0-0 = 0;
    节点65的左子树高度为0,右子树高度为1,BF= 0-1 = -1;
    对于平衡二叉树,BF的取值范围为[-1,1]。如果发现某个节点的BF值不在此范围,则需要对树进行调整。2. 最小不平衡子树:距离插入节点最近的,且平衡因子的绝对值大于1的节点为根的子树.。 在图三中,左边二叉树的节点45的BF = 1,插入节点43后,节点45的BF = 2。节点45是距离插入点43最近的BF不在[-1,1]范围内的节点,因此以节点45为根的子树为最小不平衡子树。  旋转前面说过,如果在AVL树中进行插入或删除节点后,可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态:LL(左左),LR(左右),RR(右右)和RL(右左)。下面给出它们的示意图: LL:LeftLeft,也称为"左左"。插入或删除一个节点后,根节点的左子树的左子树还有非空子节点,导致"根的左子树的高度"比"根的右子树的高度"大2,导致AVL树失去了平衡。
     例如,在下面LL情况中,由于"根节点(8)的左子树(4)的左子树(2)还有非空子节点",而"根节点(8)的右子树(12)没有子节点";导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。
(2) LR:LeftRight,也称为"左右"。插入或删除一个节点后,根节点的左子树的右子树还有非空子节点,导致"根的左子树的高度"比"根的右子树的高度"大2,导致AVL树失去了平衡。
     例如,在下面LR情况中,由于"根节点(8)的左子树(4)的左子树(6)还有非空子节点",而"根节点(8)的右子树(12)没有子节点";导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。
 (3) RL:RightLeft,称为"右左"。插入或删除一个节点后,根节点的右子树的左子树还有非空子节点,导致"根的右子树的高度"比"根的左子树的高度"大2,导致AVL树失去了平衡。
     例如,在下面RL情况中,由于"根节点(8)的右子树(12)的左子树(10)还有非空子节点",而"根节点(8)的左子树(4)没有子节点";导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。
 (4) RR:RightRight,称为"右右"。插入或删除一个节点后,根节点的右子树的右子树还有非空子节点,导致"根的右子树的高度"比"根的左子树的高度"大2,导致AVL树失去了平衡。
     例如,在下面RR情况中,由于"根节点(8)的右子树(12)的右子树(14)还有非空子节点",而"根节点(8)的左子树(4)没有子节点";导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。
  除了上面的情况之外,还有其它的失去平衡的AVL树,暂时考虑。    AVL树失衡调整节点的插入或删除都有可能导致AVL树失去平衡,因此,失衡调整是插入与删除操作的基础。
AVL树的失衡调整可以分为四种情况,我们逐一分析。
假设我们要为数组a[]={4,5,6,3,2,8,7,0,1}构建一棵AVL树。情况一:RR型调整首先插入{4,5,6},在插入元素6后出现不平衡的情况:
当我们在右子树插入右孩子导致AVL失衡时,我们需要进行RR型调整。旋转围绕最小失衡子树的根节点进行。
在删除新节点时也有可能会出现需要单左旋的情况。
左旋代码如下:情况二:LL型调整我们继续插入元素{3,2},此时二叉树为:
插入3、2后出现了不平衡的情况。此时的插入情况是“在左子树上插入左孩子导致AVL树失衡”,我们需要进行LL型调整。
单右旋代码为: 情况三:RL型调整需要进行两次旋转的原因是第一次旋转后,AVL树仍旧处于不平衡的状态,第二次旋转再次进行调整。
我们继续插入元素{8,7}
这种情况,总结起来就是“在右子树上插入左孩子导致AVL树失衡",此时我们需要进行先右旋后左旋的调整。
调整的代码为:情况四:LR型调整根据对称性原理,当我们“在左子树上插入右孩子导致AVL树失衡",此时我们需要进行先左旋后右旋的调整。如果你不理解接着看图。
我们接着插入节点{0,1}
  参考资料1. 2. 3.

相关内容推荐