前言

平衡二叉树是二叉搜索树的一个变种，一棵完全偏向一边的搜索树在一定程度上会影响查找性能。 然而历史上总是不缺神，一些追求极致、完美（强迫症）的神就想出了平衡二叉树。

本次仅实现插入、按层级展示两个功能。

安利 此文很不错，特别是自带动画效果！！ http://blog.csdn.net/eson_15/article/details/51144079

这个简明扼要！！！ http://www.cnblogs.com/skywang12345/p/3577479.html

网易公开课《数据结构》陈越、何钦铭中关于平衡二叉树的讲解： http://mooc.study.163.com/course/ZJU-1000033001?tid=1000044001#/info

平衡二叉树

如果一棵树非空，其任意一个节点的左右子树之间的高度差的绝对值不超过1(<=1)，那么其就是平衡二叉树。

左右子树的高度差的绝对值称为平衡因子

举个例子

判断是否为平衡二叉树

图1

根节点 没有左子树，高度为0。右子树的高度为2。 平衡因子2 > 1，不满足要求。

其他节点无需再判断，图1不是平衡二叉树。

图2

根节点 左子树高度为1，右子树高度为2。 平衡因子为1 = 1，暂时满足要求(记住定义为任意一个节点)。

节点1 左子树高度为0，右子树高度为0， 平衡因子为0 < 1，满足要求。

节点3 左子树高度为0，右子树高度为1， 平衡因子为1 = 1，满足要求。

节点4 左子树高度为0，右子树高度为0， 平衡因子为0 < 1，满足要求。

所有节点判断完毕。可以断定，图2的树就是平衡二叉树。

还有一些问题

Q1:道理我都懂，平衡二叉树到底怎么写？

A1:

在普通的二叉搜索树中插入节点时，我们只通过大小来判断位置，不管树的形态。

在平衡二叉树中，我们则需要

插入节点时，判断节点的位置插入节点后，确认任意一个节点平衡因子还是<=1如果出现了偏差，那么修正树的形态

Q2:如何计算平衡因子？

A2:

平衡因子 = |节点的左子树的高度 - 节点的右子树高度| ||：绝对值

Q3:如何确定一个节点子树的高度

A3:

你听说过深度优先遍历吗？

private int getHeightRecursion(TreeNode root) { if (root == null) { return 0; } int left = getHeightRecursion(root.left); int right = getHeightRecursion(root.right); return (left > right ? left : right) + 1; }

先进行左优先遍历，再进行右优先遍历。

取最大值是怕出现没左节点，有右节点的情况，0：1总不能取0啊。

从最后一层回到首层，每次都自增一层。

最后结果就是深度。

---

下面可能是废话：

从根节点进入到最后一个左节点，到达后返回，每次自增。

再进入最后一个右节点，到达后返回，每次自增。

到达最后一层后返回时，可能会出现[有]左子节点(left=1)，[无]右子节点的情况(right=0)。

因此，整个递归期间，左右的高度都有可能不同。

所以需要取最大值。

+1表示深度增加一层。

如果只有一个根节点，高度为1。

---

理解了递归探索子树深度，来看看AVL树中可以怎么玩。

让节点自带高度属性，插入操作时进行记录，那么每次判断平衡因子就不用进行额外的递归了。

//节点 class TreeNode<T extends Comparable<T>> { private T data; private TreeNode left; private TreeNode right; //用于记录高度 private int height; TreeNode(T data) { this.data = data; } } //获取高度 private int getHeightRecord(TreeNode tree) { if (tree != null) { return tree.height; } return 0; } //插入操作 private TreeNode insertNode(TreeNode<T> root, T data) { if (root == null) { root = new TreeNode<>(data); } else { int cmp = data.compareTo(root.data); if (cmp < 0) { root.left = insertNode(root.left, data); } else if (cmp > 0) { root.right = insertNode(root.right, data); } else { System.out.println("已存在相同节点"); } } root.height = Math.max(getHeightRecord(root.left), getHeightRecord(root.right)) + 1; return root; }

原理和递归探索一样，多了记录这一操作。

插入节点时，我们从根节点开始，搜索到合适的位置插入。【即到达最深处】

插入完成后。 [记录]新插入的节点高度为1。

回退到上一层。

由于可能新增了节点，所以更新这一层的原来的记录。

通过节点的height属性获取左右节点的高度，取最大值。

加上自己本身高度1，即为新高度。重新记录。

Q3:怎么修正树的形态？

A3:

这是AVL树中最棘手的问题，一旦平衡状态被破坏，我们通过四种旋转来修正树的形态。分别为：LL旋转、RR旋转、LR旋转、RL旋转。

其中L表示left，R表示right。

我们知道当某个节点的平衡因子到达2时，树就已经失去平衡了。 所以每当一个节点的平衡因子超过1时，我称该节点为【被破坏节点】。

以下是个人理解：

而这些LL、RR、LR、RL都是针对【被破坏节点】的。

例如LL，说的是【被破坏节点】的【左子节点】的【左子节点】 RL，说的是【被破坏节点】的【右子节点】的【左子节点】。

切记 从字面意思来理解旋转。 围着一个指定的节点旋转。 当我说提升某个节点的时候，其实就是围绕那个节点旋转。

下面进入正题，四大旋转。

LL插入(左单旋):

围绕【被破坏节点】的【左子节点】向右旋转。

情况1：

修正方法： 将【被破坏节点】的【左子节点】提升为根节点。

情况2：

修正方法： 同样是将【被破坏节点】的【左子节点】提升为根节点。

但重点关注的是【被破坏节点】的【左子节点】的【右子节点】 如上图中的【节点8】，称为【左右节点】。

如果直接提升根节点。此时根节点会有三个分支，这是不可取的。

所以将【节点8】移动，变为【被破坏节点】的【左子节点】。 （因为【左右节点】肯定比【被破坏节点】小，又肯定比【被提升节点】大）

图片示例：

上图说明在情况2里，新插入的节点在【左左节点】的左边还是右边都不影响修正步骤。 【节点8】在修正后移动到了【被破坏节点】的左边

上面提到的提升为根节点可能造成混淆，可以理解成提升为【被破坏节点】的【父节点】。

综合2种情况：

1. 先将【被破坏节点】的【左子节点】提升为成【父节点】 2. 【被破坏节点】移动到【被提升节点】的右边。（绕着父节点向右旋转） 3. 最后将原来【被提升节点】的【右子节点】移动到【被破坏节点】的左边。（指针跟着向右旋转） private TreeNode singleLeftRotation(TreeNode tree) { //将被破坏节点的左子节点提升为根节点 TreeNode root = tree.left; //如果新根节点的右边不为空，把它放进被破坏节点的左边 tree.left = root.right == null ? null : root.right; //被破坏节点放进新根节点的右边 root.right = tree; return root; }

RR插入(右单旋):

围绕【被破坏节点】的【右子节点】向左旋转。

情况1：

修正方法： 将【被破坏节点】的【右子节点】提升为根节点即可。

情况2：

修正方法： 将【被破坏节点】的【右子节点】提升为根节点。 根节点会有三个分支，这是不可取的。

所以在提升后，将【右子节点】的左分支移动到【被破坏节点】的右边。 （原因是【右左节点】肯定比【被破坏节点】大，又肯定比【被提升节点】小）

如上图，【右左节点】6被移动到【被破坏节点】5的右边

综合2种情况：

1. 先将【被破坏节点】的【右子节点】提升为成【父节点】 2. 【被破坏节点】移动到【被提升节点】的左边。（绕着父节点向左旋转） 3. 最后将原来【被提升节点】的【左子节点】移动到【被破坏节点】的右边。（指针跟着向左旋转） private TreeNode singleRightRotation(TreeNode tree) { //将被破坏节点的右子节点提升为根节点 TreeNode root = tree.right; //如果新根节点的左边不为空，转移到被破坏节点的右边 tree.right = root.left == null ? null : root.left; //被破坏节点放进新根节点的左边 root.left = tree; return root; }

LR插入(左-右双旋):

如上图，在插入【节点7】后，【节点9】被破坏。

且【节点7】是【节点9】的【左子节点】的【右子节点】的子节点之一。

使用LR旋转修正：

private TreeNode doubleLeftRightRotation(TreeNode tree) { tree.left = singleRightRotation(tree.left); return singleLeftRotation(tree); }

RL插入(右-左双旋):

如上图，在插入【节点9】后，【节点7】被破坏。

且【节点9】是【节点7】的【右子节点】的【左子节点】的子节点之一。

使用RL旋转修正：

private TreeNode doubleRightLeftRotation(TreeNode tree) { tree.right = singleLeftRotation(tree.right); return singleRightRotation(tree); }

完整代码实现

测试跟实现放在一起了，纯粹就是懒。

import java.util.ArrayDeque; import java.util.ArrayList; public class AVLTree<T extends Comparable<T>> { public static void main(String[] args) { System.out.println("输入："); int[] nodeValues = {9, 6, 10, 5, 8, 7, 11}; AVLTree<Integer> tree = initTreeAndShowData(nodeValues); System.out.println("输出："); tree.show(tree.root); System.out.println("输入："); nodeValues = new int[]{9}; tree = initTreeAndShowData(nodeValues); System.out.println("输出："); tree.show(tree.root); System.out.println("输入："); nodeValues = new int[]{9, 3, 2, 1, 13, 80, 54, 26, 90, -3, 70, 24, 27, 8, 10}; tree = initTreeAndShowData(nodeValues); System.out.println("输出："); tree.show(tree.root); System.out.println("输入："); nodeValues = new int[]{7, 5, 10, 8, 11, 9}; tree = initTreeAndShowData(nodeValues); System.out.println("输出："); tree.show2(tree.root); } /** * 将数组内的数据存储进二叉树 * @param nodeValues 需要录入二叉树的数组 * @return 返回已录入数据的二叉树的根节点 */ static AVLTree<Integer> initTreeAndShowData(int[] nodeValues) { AVLTree<Integer> tree = new AVLTree<Integer>(); for (int i = 0; i < nodeValues.length; i++) { tree.insert(nodeValues[i]); System.out.print(nodeValues[i] + " "); } System.out.println(); return tree; } /****************************************************************************/ /** * 二叉树内部节点 */ class TreeNode<T extends Comparable<T>> { private T data; private TreeNode<T> left; private TreeNode<T> right; private int height; TreeNode(T data) { this.data = data; left = null; right = null; } } private TreeNode<T> root; AVLTree() { root = null; } /** * 将给定数据插入节点 * @param data 需要插入树中的节点数据 */ public void insert(T data) { root = insertNode(root, data); } /** * 插入二叉树的内部实现 * @param root 指定的根节点 * @param data 需要插入的数据 * @return 返回插入数据后的树 */ private TreeNode<T> insertNode(TreeNode<T> root, T data) { if (root == null) { root = new TreeNode<>(data); } else { //比较插入数据与当前根节点的大小 int cmp = data.compareTo(root.data); if (cmp < 0) { root.left = insertNode(root.left, data); //判断平衡因子是否超过了1 if (isLargerThanOne(root)) { if (data.compareTo(root.left.data) < 0) { //左单旋 root = singleLeftRotation(root); } else { //左-右双旋 root = doubleLeftRightRotation(root); } } } else if (cmp > 0) { root.right = insertNode(root.right, data); if (isLargerThanOne(root)) { if (data.compareTo(root.right.data) > 0) { //右单旋 root = singleRightRotation(root); } else { //右-左双旋 root = doubleRightLeftRotation(root); } } } else { System.out.println("已存在相同节点"); } } //更新节点高度 root.height = Math.max(getHeightRecord(root.left), getHeightRecord(root.right)) + 1; return root; } private boolean isLargerThanOne(TreeNode tree) { return Math.abs(getHeightRecord(tree.left) - getHeightRecord(tree.right)) > 1; } /** * 将传入节点的左子节点提升为根 * @param tree 被破坏节点 * @return 返回旋转完毕后的子树 */ private TreeNode singleLeftRotation(TreeNode tree) { //将被破坏节点的左子节点提升为根节点 TreeNode root = tree.left; //如果新根节点的右边不为空，把它放进被破坏节点的左边 tree.left = root.right == null ? null : root.right; //被破坏节点放进新根节点的右边 root.right = tree; return root; } /** * 将传入节点的右子节点提升为根 * @param tree 被破坏节点 * @return 返回旋转完毕后的子树 */ private TreeNode singleRightRotation(TreeNode tree) { //将被破坏节点的右子节点提升为根节点 TreeNode root = tree.right; //如果新根节点的左边不为空，转移到被破坏节点的右边 tree.right = root.left == null ? null : root.left; //被破坏节点放进新根节点的左边 root.left = tree; return root; } /** * 处理LR插入 * @param tree 被破坏节点 * @return 返回旋转完毕后的子树 */ private TreeNode doubleLeftRightRotation(TreeNode tree) { tree.left = singleRightRotation(tree.left); return singleLeftRotation(tree); } /** * 处理RL插入 * @param tree 被破坏节点 * @return 返回旋转完毕后的子树 */ private TreeNode doubleRightLeftRotation(TreeNode tree) { tree.right = singleLeftRotation(tree.right); return singleRightRotation(tree); } /** * 获取tree的高度 * @param tree 一个节点 * @return 如果为null，返回0，否则返回高度 */ private int getHeightRecord(TreeNode tree) { if (tree != null) { return tree.height; } return 0; } /** * 按层级显示一棵二叉树，不带高度的二叉树 * @param node 二叉树的根节点 */ public void show(TreeNode<Integer> node) { ArrayDeque<TreeNode> nodes = new ArrayDeque<>(); int i = 0, n = 0; boolean isFirst = true; TreeNode<Integer> t; nodes.add(node); while (nodes.size() != 0) { t = nodes.remove(); System.out.print(t.data + "\t"); if (++i == 2 << n || isFirst) { i = 0; n = isFirst ? n : n + 1; isFirst = false; System.out.println(); } if (t.left != null) { nodes.add(t.left); } if (t.right != null) { nodes.add(t.right); } } System.out.println(); } /** * 按层级显示一棵二叉树，带高度的二叉树 * @param node 二叉树的根节点 */ public void show2(TreeNode<Integer> node) { ArrayList<TreeNode> nodes = new ArrayList<TreeNode>(); TreeNode<Integer> t; nodes.add(0, node); int size = nodes.size(); while (size != 0) { t = nodes.remove(0); if (t.left != null) { nodes.add(t.left); } if (t.right != null) { nodes.add(t.right); } if ((size = nodes.size()) != 0 && t.height == nodes.get(0).height) { System.out.print(t.data + "\t"); } else { System.out.println(t.data); } } } /** * 属性不带高度时，根据根节点判断高度 * @param tree 根节点 * @return 树的高度 */ private int getHeightRecursion(TreeNode tree) { if (tree == null) { return 0; } int left = getHeightRecursion(tree.left); int right = getHeightRecursion(tree.right); return (left > right ? left : right) + 1; } }

结果

输出结果按层级展示。

输入： 9 6 10 5 8 7 11 输出： 8 6 10 5 7 9 11 输入： 9 输出： 9 输入： 9 3 2 1 13 80 54 26 90 -3 70 24 27 8 10 输出： 13 3 54 1 9 26 80 -3 2 8 10 24 27 70 90 输入： 7 5 10 8 11 9 输出： 8 7 10 5 9 11

END