2023年6月22日发(作者：)

平衡⼆叉树（AVL树）详细解析-通俗易懂平衡⼆叉树定义:⼆叉排序树的平衡因⼦绝对值⼩于等于1，即平衡因⼦为-1、0、1,那么是平衡⼆叉树（平衡因⼦：根结点的左⼦树深度减右⼦树深度的差）。最⼩不平衡⼦树：⼦树的根结点距离插⼊结点距离最近，且平衡因⼦绝对值⼤于1的树为最⼩不平衡⼦树。平衡⼆叉树：当插⼊结点后出现最⼩不平衡⼦树，那么就要对最⼩不平衡⼦树重新构造，通过顺时针（平衡因⼦皆为正）或逆时针（平衡因⼦皆为负）旋转最⼩不平衡⼦树的根结点使之成为平衡⼆叉树。注意：如果最⼩不平衡⼦树的根结点与页结点不是同号的，需要将其先转为同号再进⾏上述旋转(如何双旋转：如果最⼩不平衡树的根结点平衡因⼦为负数，说明其右⼦树深度⾼，为R，结点逆时针旋转;如果最⼩不平衡树的根结点右⼦树平衡因⼦为正数，说明其左⼦树深度⾼，为L，结点顺时针旋转；这样就形成了从上往下为RL，则先下⼦树L旋转，再上⼦树R旋转；反之为LR旋转）。我们在处理平衡⼆叉树的时候回出现4中情况:LL型单旋转，顺时针旋转（新增结点在最⼩不平衡⼦树根的左⼦树的左⼦树下，L表⽰左⼦树，数字2表⽰平衡因⼦） /** *

执⾏LL顺时针旋转，最⼩不平衡⼦树才需要旋转，平衡的会过滤，对⽐图理解会⽐较容易 * @param tree

不⼀定是最⼩不平衡⼦树，看LR第⼆个图计算可知 * @return

返回根结点 */ public TreeNode executeLeftLeft(TreeNode tree) { TreeNode newRoot; newRoot = b; b = ub; ub = tree; = (getHeight(b), getHeight(ub)) + 1; = (getHeight(b), getHeight(tree)) + 1; return newRoot; }LR型双旋转，先下后上旋转，先R逆时针选择，后L顺时针旋转（新增结点在最⼩不平衡⼦树根的左⼦树的右⼦树下，L表⽰左⼦树，数字2表⽰平衡因⼦） /** *

执⾏LR旋转，则先R逆时针旋转，最后变成LL,再顺时针旋转即可，对⽐图理解会⽐较容易 * @param tree

不⼀定是最⼩不平衡⼦树，看LR第⼆个图计算可知 * @return

返回根结点 */ public TreeNode executeLeftRight(TreeNode tree) { b = executeRightRight(b); return executeLeftLeft(tree); }RR型单旋转，逆时针旋转（新增结点在最⼩不平衡⼦树根的右⼦树的右⼦树下，R表⽰右⼦树，数字-2表⽰平衡因⼦） /** *

执⾏RR逆时针旋转，最⼩不平衡⼦树才需要旋转，平衡的会过滤，对⽐图理解会⽐较容易 * @param tree

不⼀定是最⼩不平衡⼦树，看LR第⼆个图计算可知 * @return */ public TreeNode executeRightRight(TreeNode tree) { TreeNode newRoot; newRoot = ub; ub = b; b = tree; = (getHeight(b), getHeight(ub)) + 1; = (getHeight(tree), getHeight(b)) + 1; return newRoot; }RL型双旋转，先下后上旋转，先R逆时针选择，后L顺时针旋转（新增结点在最⼩不平衡⼦树根的右⼦树的左⼦树下，R表⽰右⼦树，数字-2表⽰平衡因⼦） /** *

执⾏RL旋转，则先执⾏L顺时针旋转，最后变成RR,再逆时针旋转即可，对⽐图理解会⽐较容易 * @param tree

不⼀定是最⼩不平衡⼦树，看LR第⼆个图计算可知 * @return */ public TreeNode executeRightLeft(TreeNode tree) { ub = executeLeftLeft(ub); return executeRightRight(tree); }下⾯举个栗⼦具体操作：依次添加5、4、3、6、10、8、9、14、13这些结点（1）前⾯添加到3时才会不平衡，因此就从添加3开始了，加3后，LL,根顺时针单旋转（2）加6后任然是平衡树（3）加10后，RR,最⼩不平衡树根逆时针单旋转（4）加8后RR,最⼩不平衡树根逆时针单旋转（5）加9后LR，所以先R逆时针旋转后L顺时针旋转（6）加14后仍然是⼆叉平衡树（7）加13后RL,所以先L顺时针旋转后R逆时针旋转package ;public class TreeNode> {

T data; //树结点值 TreeNode leftSub; //树的左⼦树 TreeNode rightSub; //树的右⼦树 int hight; //树的⾼度

private TreeNode root;

public TreeNode getTree() { return root; }

public TreeNode() {};

public TreeNode(T data, TreeNode leftSub, TreeNode rightSub) { = data; b = leftSub; ub = rightSub; = 1; //新增结点树的⾼度是1 }

public static void main(String[] args) { TreeNode treeNode = new TreeNode(); int tree[] = {5, 4, 3, 6, 10, 8, 9, 14, 13}; for (int i = 0; i < ; i++) { (tree[i]); } TreeNode newTree = e(); n("树⾼：" + ); AndBalance(newTree, 9); AndBalance(newTree, 9); newTree = e(); n("树⾼：" + );

}

/** *

获取树的⾼度 * @param tree

⼆叉树 * @return */ public int getHeight(TreeNode tree) { if (tree != null) { return ; } //如果树为空，则返回0 return 0; }

//平衡因⼦为<=1⽆需处理 /** *

执⾏LL顺时针旋转，最⼩不平衡⼦树才需要旋转，平衡的会过滤，对⽐图理解会⽐较容易 * @param tree

不⼀定是最⼩不平衡⼦树，看LR第⼆个图计算可知 * @return

返回根结点 */ public TreeNode executeLeftLeft(TreeNode tree) { TreeNode newRoot; newRoot = b; b = ub; ub = tree; = (getHeight(b), getHeight(ub)) + 1; = (getHeight(b), getHeight(tree)) + 1; return newRoot; }

/** *

执⾏RR逆时针旋转，最⼩不平衡⼦树才需要旋转，平衡的会过滤，对⽐图理解会⽐较容易 * @param tree

不⼀定是最⼩不平衡⼦树，看LR第⼆个图计算可知 * @return */ public TreeNode executeRightRight(TreeNode tree) { TreeNode newRoot; newRoot = ub; ub = b; b = tree; = (getHeight(b), getHeight(ub)) + 1; = (getHeight(tree), getHeight(b)) + 1; return newRoot; }

/** *

执⾏LR旋转，则先R逆时针旋转，最后变成LL,再顺时针旋转即可，对⽐图理解会⽐较容易 * @param tree

不⼀定是最⼩不平衡⼦树，看LR第⼆个图计算可知 * @return

返回根结点 */ public TreeNode executeLeftRight(TreeNode tree) { b = executeRightRight(b); return executeLeftLeft(tree); }

/** *

执⾏RL旋转，则先执⾏L顺时针旋转，最后变成RR,再逆时针旋转即可，对⽐图理解会⽐较容易 * @param tree

不⼀定是最⼩不平衡⼦树，看LR第⼆个图计算可知 * @return */ public TreeNode executeRightLeft(TreeNode tree) { ub = executeLeftLeft(ub); return executeRightRight(tree); } }

public void insert(T data) { root = insert(root, data); }

/** *

新增结点 * @param tree

被添加结点树 * @param data

结点值 * @return */ public TreeNode insert(TreeNode tree, T data) { if (tree == null) { return new TreeNode(data, null, null); } int cmp = eTo(); if (cmp > 0) { ub = insert(ub, data); } else if (cmp < 0) { b = insert(b, data); } return balance(tree); } /** *

新增结点 * @param tree

⼆叉树 * @return */ public TreeNode balance(TreeNode tree) { if (tree == null) { return null; } int balanceFactor = 1; if (getHeight(b) - getHeight(ub) > balanceFactor) { if (getHeight(b) > getHeight(ub)) { tree = executeLeftLeft(tree); } else { tree = executeLeftRight(tree); } } else if (getHeight(ub) - getHeight(b) > balanceFactor) { if (getHeight(ub) > getHeight(b)) { tree = executeRightRight(tree); } else { tree = executeRightLeft(tree); } } = (getHeight(b), getHeight(ub)) + 1; return tree; }

/** *

查找⼆叉树的结点 * @param tree

⼆叉树 * @param data

数据 * @return */ public TreeNode findNode(TreeNode tree, T data) { if (tree == null) { return null; } int cmp = eTo(); if (cmp < 0) { return findNode(b, data); } else if (cmp > 0) { return findNode(ub, data); } else { return tree; return tree; } }

/** *

更新结点值 * @param tree

⼆叉树 * @param data

旧值 * @param newData

更新值 * @return */ public TreeNode modifyNode(TreeNode tree, T data, T newData) { if (tree == null) { return null; } int cmp = eTo(); if (cmp < 0) { return findNode(b, data); } else if (cmp > 0) { return findNode(ub, data); } else { = newData; return tree; } }

/** *

找最⼩值结点 * @param tree * @return */ public TreeNode findMinData(TreeNode tree) { if (tree == null) { return null; } else if (b == null) { return tree; } return findMinData(b); }

/** *

找最⼤值结点 * @param tree * @return */ public TreeNode findMaxData(TreeNode tree) { if (tree == null) { return null; } else if (ub == null) { return tree; } return findMaxData(ub); }

/** *

删除⼆叉树及平衡⼆叉树 * @param tree * @param data * @return */ public TreeNode removeAndBalance(TreeNode tree, T data) { TreeNode treeNew = remove(tree, data); return balance(treeNew); }

/** *

删除⼆叉树结点 * @param tree * @param data * @param data * @return */ public TreeNode remove(TreeNode tree, T data) { if (tree == null) { return null; }// int flag = 1; //设置标识是在查找结点的左⼦树还是右⼦树 int cmp = eTo(); if (cmp > 0) { ub = remove(ub, data);// flag = 1; } else if (cmp < 0) { b = remove(b, data);// flag = -1; } else if (b != null && ub != null) {// if (flag == -1) { //为左⼦树，找左⼦树中值最⼤的结点替换当前结点// = findMaxData(b).data;// ub = remove(b, );// } else {//为左⼦树，找右边⼦树中值最⼩的结点替换当前结点 = findMinData(ub).data; ub = remove(ub, );// } } else { tree = (b != null) ? b : ub; } return tree; }

}