Java数据结构之平衡二叉树的原理与实现

public class AvlTree { /** * 外部保存根节点的引用 */ private BinaryTreeNode root; /** * 自定义比较器 */ private Comparator cmp; /** * 树节点的数量 */ private int size; /** * 内部节点对象 * * @param  数据类型 */ public static class BinaryTreeNode { //数据域 E data; //左子节点 BinaryTreeNode left; //右子节点 BinaryTreeNode right; //节点高度 从0开始,从下往上;null节点高度返回-1 int height; public BinaryTreeNode(E data) { this.data = data; } @Override public String toString() { return data.toString(); } } /** * 指定比较器 * * @param cmp 比较器 */ public AvlTree(Comparator cmp) { this.cmp = cmp; } /** * 空构造器 */ public AvlTree() { } /** * 是否是空树 * * @return true 是 ;false 否 */ public boolean isEmpty() { return size == 0; } /** * 返回节点数 * * @return 节点数 */ public int size() { return size; } /** * 对元素进行比较大小的方法,如果传递了自定义比较器,则使用自定义比较器,否则则需要数据类型实现Comparable接口 * * @param e1 被比较的第一个对象 * @param e2 被比较的第二个对象 * @return 0 相等 ;小于0 e1  e2 */ private int compare(E e1, E e2) { if (cmp != null) { return cmp.compare(e1, e2); } else { return ((Comparable) e1).compareTo(e2); } } /** * 保存遍历出来的节点数据 */ List> str = new ArrayList<>(); /** * 中序遍历,提供给外部使用的api * * @return 遍历的数据 */ public String toInorderTraversalString() { //如果是空树,直接返回空 if (isEmpty()) { return null; } //从根节点开始递归 inorderTraversal(root); //获取遍历结果 String s = str.toString(); str.clear(); return s; } /** * 中序遍历 内部使用的递归遍历方法,借用了栈的结构 * * @param root 节点,从根节点开始 */ private void inorderTraversal(BinaryTreeNode root) { BinaryTreeNode left = getLeft(root); if (left != null) { //如果左子节点不为null,则继续递归遍历该左子节点 inorderTraversal(left); } //添加数据节点 str.add(root); //获取节点的右子节点 BinaryTreeNode right = getRight(root); if (right != null) { //如果右子节点不为null,则继续递归遍历该右子节点 inorderTraversal(right); } } /** * 获取左子节点 * * @param parent 父节点引用 * @return 左子节点或者null--表示没有左子节点 */ public BinaryTreeNode getLeft(BinaryTreeNode parent) { return parent == null ? null : parent.left; } /** * 获取右子节点 * * @param parent 父节点引用 * @return 右子节点或者null--表示没有右子节点 */ public BinaryTreeNode getRight(BinaryTreeNode parent) { return parent == null ? null : parent.right; } /** * 获取根节点 * * @return 根节点 ;或者null--表示空树 */ public BinaryTreeNode getRoot() { return root; } /** * 获取height * * @param node 节点 * @return 高度或者-1 表示节点为null */ private int getHeight(BinaryTreeNode node) { return node == null ? -1 : node.height; } }

    /** * 查找,开放给外部使用的api * @param e 要查找的元素 * @return false 不存在 true 存在 */ public boolean contains(E e) { return contains(e, root); } /** * 查找,内部调用的方法,从根节点开始查找 * * @param e    要查找的元素 * @param root 节点 * @return false 不存在 true 存在 */ private boolean contains(E e, BinaryTreeNode root) { /*null校验*/ if (root == null) { return false; } /*调用比较的方法*/ int i = compare(e, root.data); /*如果大于0，则说明e>root.date 继续查询右子树*/ if (i > 0) { return contains(e, root.right); /*如果小于0，则说明e

    /** * 保存是否平衡的标志 */ private boolean balance = true; /** * 检查是否是平衡二叉树的方法,当然也可以debug看,如果你不嫌麻烦…… * * @return true 是 ；false 否 */ public boolean checkBalance() { checkBalance(root); boolean balanceNow=balance; balance=true; return balanceNow; } /** * 递归检查是否平衡,实际上这里采用了后序遍历,即左子节点-右子节点-根节点的方法递归遍历检查 * * @param root 根节点 * @return 节点的高度 */ private int checkBalance(BinaryTreeNode root) { if (root == null) { return -1; } //返回左子树的高度 int hl = checkBalance(root.left); //返回右子树的高度 int hr = checkBalance(root.right); //如果root的左右子树高度差绝对值大于1,或者checkBalance和getHeight方法获取的左/右子树高度不一致,那么算作不平衡 if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1 || getHeight(root.left) != hl || getHeight(root.right) != hr) { balance = false; } return getHeight(root); }

   /** * 插入,开放给外部使用的api * * @param e 要插入的元素 */ public void insert(E e) { //返回root,但此时新的节点可能已经被插入进去了 root = insert(e, root); } /** * 插入,开放给外部使用的api * * @param es 要插入的元素的数组,注意,数组元素的顺序存储的位置将会影响二叉排序树的生成 */ public void insert(E[] es) { //返回root,但此时新的节点可能已经被插入进去了 for (E e : es) { root = insert(e, root); } } /** * 插入,内部调用的方法,先从根节点开始递归查找要插入的位置,然后插入 * 大部分代码都和排序二叉树的相似，区别就是在插入之后，会调用尝试重平衡的方法rebalance * * @param e    要插入的数据 * @param root 节点 * @return 原节点重平衡之后的节点或者新插入的节点 */ private BinaryTreeNode insert(E e, BinaryTreeNode root) { /*没有查找到,那么直接构建新的节点返回,将会在上一层方法中被赋值给其父节点的某个引用,这个插入的位置肯定是该遍历路径上的最后一点 * 即插入的元素节点肯定是属于叶子节点*/ if (root == null) { size++; return new BinaryTreeNode<>(e); } /*调用比较的方法*/ int i = compare(e, root.data); /*如果大于0，则说明e>root.date 继续查询右子树*/ if (i > 0) { //重新赋值 root.right = insert(e, root.right); /*如果小于0，则说明e rebalance(BinaryTreeNode root) { /*1、如果节点为null,直接返回null*/ if (root == null) { return null; } /*2、开始旋转*/ /*2.1、如果左子树的高度减去右子树的高度值大于1,说明左子树的高度大于右子树的高度至少2层,可能是情况1、2 继续判断*/ if (getHeight(root.left) - getHeight(root.right) > 1) { /*如果左子节点的左子节点高度大于左子节点的右子节点高度,那说明是情况1,否则是情况2*/ if (getHeight(root.left.left) >= getHeight(root.left.right)) { /*2.1.1、右旋*/ root = rotateRight(root); } else { /*2.1.2、左-右双旋*/ root = rotateLeftAndRight(root); } /*2.2、如果右子树的高度减去左子树的高度值大于1,说明右子树的高度大于左子树的高度至少2层,可能是情况3、4 继续判断*/ } else if (getHeight(root.right) - getHeight(root.left) > 1) { /*如果右子节点的右子节点高度大于右子节点的左子节点高度,那说明是情况4,否则是情况3*/ if (getHeight(root.right.right) >= getHeight(root.right.left)) { /*2.2.1、左旋*/ root = rotateLeft(root); } else { /*2.2.2、右-左双旋*/ root = rotateRightAndLeft(root); } } /*3、到这一步,说明旋转完毕,或者不需要旋转,但是都需要重新计算高度,高度为左/右子树高度最大值+1*/ root.height = Math.max(getHeight(root.left), getHeight(root.right)) + 1; return root; } /** * 右旋 * 通解:右旋之后，k2成为根节点，k1成为k2的右子节点，k2的右子树2成为k1的左子树 * * @param k1 需要旋转的最小不平衡树根节点 * @return k2 旋转后的最小不平衡树根节点, 已经转换为平衡二叉树 */ private BinaryTreeNode rotateRight(BinaryTreeNode k1) { //获取k2,k2是k1的左子节点 BinaryTreeNode k2 = k1.left; //k2的右子树成为k1的左子树 k1.left = k2.right; //k1成为k2的右子节点 k2.right = k1; //k1的高度等于k1的左或者右子树的高度的最大值+1; k1.height = Math.max(getHeight(k1.left), getHeight(k1.right)) + 1; //k2的高度等于k2的左子节点和k1的高度(此时k1就是k2的右子节点)的最大值+1 k2.height = Math.max(getHeight(k2.left), k1.height) + 1; //返回k2,k2成为根节点 return k2; } /** * 左旋 很简单,实际上就是右旋的镜像 * 通解:左旋之后，k2成为根节点，k1成为k2的左子节点，k2的左子树2成为k1的右子树 * * @param k1 需要旋转的最小不平衡树根节点 * @return k2 旋转后的最小不平衡树根节点, 已经转换为平衡二叉树 */ private BinaryTreeNode rotateLeft(BinaryTreeNode k1) { //获取k2,k2是k1的右子节点 BinaryTreeNode k2 = k1.right; //k2的左子树成为k1的右子树 k1.right = k2.left; //k1成为k2的左子节点 k2.left = k1; //k1的高度等于k1的左或者右子树的高度的最大值+1; k1.height = Math.max(getHeight(k1.left), getHeight(k1.right)) + 1; //k2的高度等于k2的右子节点和k1的高度(此时k1就是k2的左子节点)的最大值+1 k2.height = Math.max(getHeight(k2.right), k1.height) + 1; //返回k2,k2成为根节点 return k2; } /** * 右-左双旋 * 通解：将k3当作新的根节点，并且先使得k2右旋成为k3的右子树，然后k1左旋成为k3的左子树，并且左子树2成为k1的右子树，右子树2成为k2的左子树 * * @param k1 需要旋转的最小不平衡树根节点 * @return 旋转后的最小不平衡树根节点, 已经转换为平衡二叉树 */ private BinaryTreeNode rotateRightAndLeft(BinaryTreeNode k1) { /*1、先对k1的右子节点k2进行右旋,返回右旋之后的根节点k3,然后使得成为k3成为的k1的左子树*/ k1.right = rotateRight(k1.right); /*2、然后对k1进行左旋,成为k3的左子树,返回的根节点就是k3,即返回旋转之后的根节点*/ return rotateLeft(k1); } /** * 左-右双旋 很简单,实际上就是右-左双旋的镜像 * 通解: 将k3当作新的根节点，并且先使得k2左旋成为k3的左子树，然后k1右旋成为k3的右子树，并且左子树2成为k2的右子树，右子树2成为k1的左子树 * * @param k1 需要旋转的最小不平衡树根节点 * @return 旋转后的最小不平衡树根节点, 已经转换为平衡二叉树 */ private BinaryTreeNode rotateLeftAndRight(BinaryTreeNode k1) { /*1、先对k1的左子节点k2进行左旋,返回左旋之后的根节点k3,然后使得成为k3成为的k1的左子树*/ k1.left = rotateLeft(k1.left); /*2、然后对k1进行右旋,成为k3的右子树,返回的根节点就是k3,即返回旋转之后的根节点*/ return rotateRight(k1); }

AvlTree avlTree = new AvlTree<>(); Integer[] es = new Integer[]{3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9}; //批量插入 avlTree.insert(es); //中序遍历输出 System.out.println(avlTree.toInorderTraversalString()); //检查是否平衡 System.out.println(avlTree.checkBalance()); //数量 System.out.println(avlTree.size()); 

/** * 查找最小的节点 * * @param root 根节点 * @return 最小的节点 */ private BinaryTreeNode findMin(BinaryTreeNode root) { if (root == null) { return null; /*如果该节点没有左右子节点，那么该节点就是最小的节点，返回*/ } else if (root.left == null) { return root; } /*如果该节点存在左子节点，那么继续向左递归查找*/ return findMin(root.left); } /** * 查找最大的节点 * * @param root 根节点 * @return 最大的节点 */ private BinaryTreeNode findMax(BinaryTreeNode root) { if (root == null) { return null; /*如果该节点没有右子节点，那么该节点就是最大的节点，返回*/ } else if (root.right == null) { return root; } /*如果该节点存在右子节点，那么继续向右递归查找*/ return findMax(root.right); } 

/** * 删除,开放给外部使用的api * * @param e 要删除的元素 */ public void delete(E e) { //返回root,但此时可能有一个节点已经被删除了 root = delete(e, root); } /** * 删除,内部调用的方法,删除分为三种情况: 1、该节点没有子节点 2、该字节仅有一个子节点 3、该节点具有两个子节点 * * @param e    要删除的数据 * @param root (子)树根节点 * @return 该根节点重平衡之后的节点 */ private BinaryTreeNode delete(E e, BinaryTreeNode root) { /*没有查找到,那么什么都不做*/ if (root == null) { return null; } /*调用比较的方法*/ int i = compare(e, root.data); /*如果大于0，则说明e>root.date 继续查询右子树*/ if (i > 0) { //重新赋值 root.right = delete(e, root.right); /*如果小于0，则说明e

System.out.println("======>首先删除5  此时没有影响,不需要重平衡"); avlTree.delete(5); //检查是否平衡 System.out.println(avlTree.checkBalance()); //中序遍历输出 System.out.println(avlTree.toInorderTraversalString()); System.out.println("======>再次删除6  此时节点4的BF为2 需要右旋重平衡"); avlTree.delete(6); //检查是否平衡 System.out.println(avlTree.checkBalance()); //中序遍历输出 System.out.println(avlTree.toInorderTraversalString()); System.out.println("======>再次删除11  由于该节点拥有左右子树,实际上删除的是该节点的右子树的最小节点12,然后将12的值赋值给11的节点,并导致节点12的原父节点11不平衡,需要重平衡"); avlTree.delete(11); //检查是否平衡 System.out.println(avlTree.checkBalance()); //中序遍历输出 System.out.println(avlTree.toInorderTraversalString()); System.out.println("======>再次删除7  由于该节点拥有左右子树,实际上删除的是该节点的右子树的最小节点8,然后将8的值赋值给7的节点,并导致节点8的原父节点9不平衡,需要重平衡"); avlTree.delete(7); //检查是否平衡 System.out.println(avlTree.checkBalance()); //中序遍历输出 System.out.println(avlTree.toInorderTraversalString()); System.out.println("======>再次删除9、12  此时不需要重平衡"); avlTree.delete(9); avlTree.delete(12); //检查是否平衡 System.out.println(avlTree.checkBalance()); //中序遍历输出 System.out.println(avlTree.toInorderTraversalString()); System.out.println("======>最后删除8  由于该节点拥有左右子树,实际上删除的是该节点的右子树的最小节点10节点,然后将10的值赋值给8的节点,并导致节点10的原父节点13不平衡,需要重平衡"); avlTree.delete(8); //检查是否平衡 System.out.println(avlTree.checkBalance()); //中序遍历输出 System.out.println(avlTree.size()); System.out.println(avlTree.toInorderTraversalString());