本文共 10013 字,大约阅读时间需要 33 分钟。
公众号原文链接: 希望点进去的小伙伴关注一下我的公众号哟,文末有二维码,谢谢!
完整项目我已经上传到我的码云git仓库上了,如果就需要的话请访问我的码云git仓库获取,附上地址:。或者点击公众号底部菜单->资源汇总->仓库汇总。或者联系我。
平衡二叉树,也是一种二叉查找树,但它是平衡的,即左子树与右子树的高度差最多等于1。
平衡二叉树也叫AVL树,取自发明平衡二叉树算法的人的人名。
平衡因子BF:左子树深度减去右子树深度的值。平衡二叉树所有结点的平衡因子只能是-1,0,1。
最小不平衡子树:假设新插入了一个结点A,然后导致树不平衡了,距离结点A最近且BF绝对值大于1的那个结点为B,以B结点为根的树称为最小不平衡子树
在构建二叉查找树过程中,每插入一个结点,先检查是否破坏了树的平衡。若是,则找出最小不平衡子树,在保持二叉查找树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之达到新的平衡。
旋转分两种:左旋和右旋。右旋会减小BF,左旋增加BF。
上面的说辞比较抽象,下面就来具体一点的。为了更好地讲解原理,我们以依次插入结点3,2,1,4,5,6,7,10,9,8为例。
第一步
首先插入3和2是没问题的。
第二步
当插入1时,发现结点3的BF变成了2,因此需要右旋,如下图所示。
第三步
插入4没问题。
第四步
当插入5时,结点3的BF变成了-2,因此左旋。
第五步
当插入结点6时,结点2的BF变成了-2,将根结点左旋。但3有点多余,将它设置为结点2的右孩子。
大家有没有担心这种情况:结点4的左子树,不单单是一个结点,而是一颗高度大于1的子树?其实不会的,它只能是一个结点。大家可以用笔在纸上画一下,平衡二叉树不会出现这样的情况。
第六步
当插入结点7时,结点5的BF变成-2,左旋。
第七步
插入10没问题。
第八步
当插入9时,7的BF为-2,理论上左旋就行了,但会不满足二叉查找树的特性。
导致这种情况的原因是:结点7和它的孩子结点10,两者的BF符号不一致。既然不一致,先将结点9和结点10组成的子树右旋,然后再以结点7为根结点进行左旋。
第九步
当插入结点8时,结点6的BF为-2,而结点9的BF为1,为了保证符号统一,因此以结点9为根结点进行右旋,注意,结点8本来是结点7的右孩子,但是右旋之后,因为7<8<9,所以只能将结点8当成结点9的左孩子。
平衡二叉树实现原理中的九个步骤,是代码实现的铺垫,建议大家将九个步骤都看懂,然后再看代码,这九个步骤几乎涵盖了所有可能的情况。
我的平衡二叉树实现分四个类:
import com.bobo.group.tree.draw.Drawable;public class AVLNode implements Drawable { private int val; private AVLNode left; private AVLNode right; public AVLNode(int val) { this.val = val; } public AVLNode(int val, AVLNode left, AVLNode right) { this.val = val; this.left = left; this.right = right; } //省略getter/setter方法 @Override public String getValue() { return String.valueOf(this.val); } @Override public Drawable getLeftNode() { return this.left; } @Override public Drawable getRightNode() { return this.right; }}
Ancestor
/** * 结点的祖先信息 */public class Ancestor { private AVLNode ancestor; private boolean isLeft; public Ancestor(AVLNode ancestor) { this.ancestor = ancestor; } public Ancestor(AVLNode ancestor, boolean isLeft) { this.ancestor = ancestor; this.isLeft = isLeft; } // 省略getter/setter方法}
AVLInsert
import com.bobo.group.common.CommonUtil;import com.bobo.group.tree.draw.DrawTree;import java.util.ArrayList;import java.util.List;public class AVLInsert { //记录插入的每个结点 private ListavlNodes = new ArrayList<>(); //画二叉树对象 private DrawTree drawTree = new DrawTree(); //可变的根结点,因为根结点也会旋转 private AVLNode variableRoot; //生成图片时计数 private int drawCounter=1; //树偏移量数组,画图用 //private int[] offset_x_arr = new int[]{60,30,25,20,20,20,10,10}; private int[] offset_x_arr = new int[]{120,80,30,30,20,20,10,10}; /** * 每插入一个结点,就画一次图 * @param key */ private void drawStep(int key){ drawTree.drawEntrance(variableRoot, CommonUtil.getResourceRoot()+"tree/avl/avlinsert_"+drawCounter+"_"+key+".png",false,offset_x_arr); drawCounter++; } /** * 平衡二叉树插入结点核心算法 * @param avlNode 当前结点 * @param key 要插入的关键字 * @param ancestorChain 祖先信息链 */ private void insert(AVLNode avlNode,int key,List ancestorChain){ if(key < avlNode.getVal()){ //新增一个祖先信息 ancestorChain.add(new Ancestor(avlNode,true)); //左孩子为null,则执行插入 if(avlNode.getLeft() == null){ AVLNode keyNode = new AVLNode(key); avlNodes.add(keyNode); avlNode.setLeft(keyNode); //平衡算法 calculateBFAndRotate(ancestorChain); //平衡后,画图 drawStep(key); return; }else{ //递归搜索 insert(avlNode.getLeft(),key,ancestorChain); } } if(key > avlNode.getVal()){ //新增一个祖先信息 ancestorChain.add(new Ancestor(avlNode,false)); //右孩子为null,则执行插入 if(avlNode.getRight() == null){ AVLNode keyNode = new AVLNode(key); avlNodes.add(keyNode); avlNode.setRight(keyNode); //平衡算法 calculateBFAndRotate(ancestorChain); //平衡后,画图 drawStep(key); return; }else{ //递归搜索 insert(avlNode.getRight(),key,ancestorChain); } } } /** * 计算平衡因子,如果有必要的话,还要旋转 * @param ancestorChain 祖先链 */ private void calculateBFAndRotate(List ancestorChain){ //ancestorChain持有的都是新插入的那个导致树不平衡的结点的祖先 // 祖先的顺序是:index为0时,为距离最远的祖先,index为size-1时,为距离最近的祖先 //所以,如果我们要找出最小不平衡子树,则需要从最近的祖先开始判断 for (int i = ancestorChain.size()-1;i >= 0;i--){ //当前祖先 AVLNode ancestorNode = ancestorChain.get(i).getAncestor(); boolean leftOfAncestor = ancestorChain.get(i).isLeft(); //分别计算当前祖先的左右子树深度 int leftDepth = searchDepth(ancestorNode.getLeft(),1); int rightDepth = searchDepth(ancestorNode.getRight(),1); //计算当前祖先的平衡因子 int bf = leftDepth-rightDepth; //如果bf绝对值大于1,则表示树不平衡,需要进行相应的处理;否则,不做任何事情 if(Math.abs(bf) > 1){ //先判断当前祖先的子节点 与 当前祖先 的BF符号是否一致 AVLNode child = leftOfAncestor?ancestorNode.getLeft():ancestorNode.getRight(); int childLeftDepth = searchDepth(child.getLeft(),1); int childRightDepth = searchDepth(child.getRight(),1); int childBf = childLeftDepth-childRightDepth; //符号不一致,以子结点为根结点进行旋转 if(childBf > 0 && bf < 0){ //右旋,旋转一个单位即可,应该没有特殊情况 rightRotate(ancestorNode,child,leftOfAncestor); }else if(childBf < 0 && bf > 0){ //左旋 leftRotate(ancestorNode,child,leftOfAncestor); } //符号统一之后,再旋转当前结点 if(bf > 0){ // 右旋 if(i == 0){ //根结点的旋转特殊处理 AVLNode rootLeftRight = ancestorNode.getLeft().getRight(); AVLNode rootLeft = ancestorNode.getLeft(); rootLeft.setRight(ancestorNode); ancestorNode.setLeft(rootLeftRight); //更新可变根结点 variableRoot = rootLeft; }else{ //非根结点处理,将当前祖先的父节点,当前祖先,当前祖先与其父节点的关系传给rightRotate方法 rightRotate(ancestorChain.get(i-1).getAncestor(),ancestorNode,ancestorChain.get(i-1).isLeft()); } }else if(bf < 0){ // 左旋 if(i == 0){ //根结点的旋转特殊处理 AVLNode rootRightLeft = ancestorNode.getRight().getLeft(); AVLNode rootRight = ancestorNode.getRight(); rootRight.setLeft(ancestorNode); ancestorNode.setRight(rootRightLeft); //更新可变根结点 variableRoot = rootRight; }else{ //非根结点处理,将当前祖先的父节点,当前祖先,当前祖先与其父节点的关系传给rightRotate方法 leftRotate(ancestorChain.get(i-1).getAncestor(),ancestorNode,ancestorChain.get(i-1).isLeft()); } } } } } //左旋时,防止右节点的左孩子不为空 private void leftRotate(AVLNode parent,AVLNode node,boolean isLeft){ //由于是左旋,为了避免不满足二叉查找树特性,所以要先判断node的右孩子的左孩子是否为null AVLNode nodeRightLeft = node.getRight().getLeft(); if(isLeft){ parent.setLeft(node.getRight()); parent.getLeft().setLeft(node); node.setRight(nodeRightLeft); }else{ parent.setRight(node.getRight()); parent.getRight().setLeft(node); node.setRight(nodeRightLeft); } } //右旋时,防止左节点的右孩子不为空 private void rightRotate(AVLNode parent,AVLNode node,boolean isLeft){ //由于是右旋,为了避免不满足二叉查找树特性,所以要先判断node的左孩子的右孩子是否为null AVLNode nodeLeftRight = node.getLeft().getRight(); if(isLeft){ parent.setLeft(node.getLeft()); parent.getLeft().setRight(node); node.setLeft(nodeLeftRight); }else{ parent.setRight(node.getLeft()); parent.getRight().setRight(node); node.setLeft(nodeLeftRight); } } //查找树的深度 private int searchDepth(AVLNode avlNode, int depth){ if(avlNode == null){ return 0; } if(avlNode.getLeft() == null && avlNode.getRight() == null){ return depth; }else if(avlNode.getLeft() == null){ return searchDepth(avlNode.getRight(),depth+1); }else if(avlNode.getRight() == null){ return searchDepth(avlNode.getLeft(),depth+1); }else{ int a = searchDepth(avlNode.getLeft(),depth+1); int b = searchDepth(avlNode.getRight(),depth+1); return a>b?a:b; } } /** * 平衡二叉树结点插入入口 * @param root 根结点 * @param keys 要插入的关键字数组 */ public void insertEntrance(AVLNode root,int[] keys){ if(null == root){ root = new AVLNode(keys[0]); variableRoot = root; this.avlNodes.add(root); for (int i = 1; i < keys.length; i++) { List parentPoints = new ArrayList<>(); insert(variableRoot,keys[i],parentPoints); } }else{ variableRoot = root; for (int i = 0; i < keys.length; i++) { List parentPoints = new ArrayList<>(); insert(variableRoot,keys[i],parentPoints); } } }}
AVLMain
public class AVLMain { public static void main(String[] args) { AVLInsert avlInsert = new AVLInsert(); avlInsert.insertEntrance(null,new int[]{3,2,1,4,5,6,7,10,9,8}); }}
运行main方法,我将每一步的结果生成了图片,供大家参考,暂时我还没测出bug来,应该没啥问题。
平衡二叉树应该还挺重要的,它的算法有一定难度,不过掌握了思想之后,代码写起来就很快了。
觉得写得不错的小伙伴,扫码关注一下我的公众号吧,谢谢呀!
转载地址:http://zvpkf.baihongyu.com/