首页 > 代码库 > 平衡二叉树
平衡二叉树
平衡二叉树
平衡二叉树又称AVL树。它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是
平衡二叉树，且左子树和右子树的深度之差绝对值不超过1.若将二叉树上节点的平衡因子BF(Balance Facter）
定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1，0和1。
只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
失去平衡后进行调整的规律可归纳为下列4种情况：
（1）单向右旋平衡处理：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为
根的子树失去平衡，则需要进行一次向右的顺时针旋转操作。
（2）单向左旋平衡处理：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为
根结点的子树失去平衡，则需要进行一次向左的逆时针旋转操作。
（3）双向旋转（先左后右）平衡处理：由于在*a的左子树根结点的右子树上插结点，*a的平衡因子由1增指2，致
使以*a为根结点的子树失去平衡，则需要进行两次旋转（先右旋后左旋）操作。
平衡二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。