为什么要平衡什么是平衡平衡因子 不平衡的情况和平衡的方法LLRRLRRL 删除操作实现 AVL是发明这个算法的两个大神 Adelson- Velsky and Landis 的名字首字母

为什么要平衡

一般的搜索树, 如果元素是顺序加入的话, 那么这棵树就会退化成链表

什么是平衡

对于任意一个节点, 左右子树的高度差不超过1的树就是平衡二叉树, 比如下面这棵树 height表示高度, 父节点的高度是左右子节点中最大的那个高度加一 平衡二叉树的高度和节点数之间的关系是 O(log n)的 因为每次加入新的节点, 都要看节点的高度, 所以节点的结构如下

class Node{ key; // 用来统计词频的话, key就是单词 value; // value是单词的出现频率 Node left, right; // 左右节点 height; // 树的高度 }

平衡因子

父节点的平衡因子(balance factor)是左子树与右子树的高度(height)之差(可正可负) 叶子节点的左右子节点为空, 高度为0, 平衡因子为0 当树中有一个节点平衡因子大于1或小于-1时, 这棵树就不平衡, 如下图

不平衡的情况和平衡的方法

只有一个节点, 或者两个节点的树是平衡的 当向一棵平衡树插入一个新的节点时, 可能会不平衡 如果不平衡, 那么那个新插入的节点的父亲节点, 祖先节点的平衡因子都会大于1或小于-1

所以新插入节点都要向上回溯来维护其平衡性

不平衡的情况有4种:

LL

如下图中, 是框中的节点带来了不平衡 我们可以把框中部分用下图来代替, 蓝色部分是他们的子树 这种情况可以称为 Left Left, 意思是新添了一个节点 z 到根节点 y 左子树的左子树, 导致根节点的平衡因子绝对值大于1

这种情况用代码表示为getBalanceFactor(y) > 1 && getBalanceFactor(x) > 0, 再次说明 平衡因子是拿左子树的height减右子树的height, getBalanceFactor(y) = 2, getBalanceFactor(x) = 1

只需要把x的右子树换成y, y的左子树换位x原来的右子树 T3 即可达到平衡, 同时还保持了二叉树搜索树的性质 相当于z不动, 将y节点以x为轴顺时针旋转, 也称为右旋转, 效果如下

Node rightRotate(Node y){ Node x = y.left; Node T3 = x.left; // 向右旋转 x.right = y; y.left = T3; // 更新height, 先更新y, 再更新x, 因为y在下面 y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; return x; }

RR

还有一种情况我们称为 Right Right, 意思是新添了一个节点 z 到根节点 y 右子树的右子树

这种情况用代码表示为getBalanceFactor(y) < -1 && getBalanceFactor(x) < 0 只需要把x的左子树换成y, y的右子树换位x原来的左子树 T3 即可达到平衡, 同时还保持了二叉树搜索树的性质 相当于z不动, 将y节点以x为轴逆时针旋转, 也称为左旋转, 效果如下

Node leftRotate(Node y){ Node x = y.right; Node T3 = x.left; // 向左旋转 x.left = y; y.right = T3; // 更新height, 先更新y, 再更新x, 因为y在下面 y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; return x; }

LR

另一种情况称为 Left Right, 意思是新添了一个节点 z 到根节点 y 左子树的右子树

这种情况用代码表示为getBalanceFactor(y) > 1 && getBalanceFactor(x) < 0 这种情况需要两次旋转 (要注意得保持二叉搜索树的性质), 首先把节点x以节点z为轴逆时针旋转, 节点y不动 (左旋转) 再把节点y以z为轴顺时针旋转, 得到效果如下 (右旋转)

RL

另一种情况称为 Right Left, 意思是新添了一个节点 z 到根节点 y 右子树的左子树

这种情况用代码表示为getBalanceFactor(y) < -1 && getBalanceFactor(x) > 0 这种情况也需要两次旋转 先节点x绕节点z顺时针旋转 (右旋转) 节点y再绕z逆时针旋转 (左旋转)

删除操作

删除一个元素的话, 就得拿一个新的元素来代替自己放在原来的位置, 我们可以拿比它大的最小元素, 或者比它小的最大元素来代替它, 这样可以同时保持二叉搜索树的性质

待删除的节点分为四种情况

待删除节点左子树为空 可以拿它的右子树代替掉自己 (用它大的最小元素代替)待删除节点右子树为空 可以拿它的左子树代替掉自己 (用比它小的最大元素代替)待删除节点左右子树为空 叶子节点也可以看成是有null作为孩子, 这样就可以用上面的方法处理掉待删除节点左右子树不为空 如果用 比它大的最小元素, 那就是拿它右子树的最小元素来代替它 如果用 比它小的最大元素, 那就是拿它左子树的最大元素来代替它

删除之后记得要重新维护平衡, 方法同上

实现

Map.java

public interface Map<K, V> { void add(K key, V value); V remove(K key); boolean contains(K key); V get(K key); void set(K key, V newValue); int getSize(); boolean isEmpty(); }

AVL.tree

import test.FileOperation; // 测试用, 可删 import java.util.ArrayList; // 测试用, 可删 public class AVLTree<K extends Comparable<K>, V> implements Map<K, V>{ private class Node{ public K key; public V value; public Node left, right; public int height; public Node(K key, V value){ this.key = key; this.value = value; left = null; right = null; height = 1; } } private Node root; private int size; public AVLTree(){ root = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } /** * 判断该二叉树是否是一棵二分搜索树 * @return */ public boolean isBST(){ ArrayList<K> keys = new ArrayList<>(); inOrder(root, keys); // 中序遍历一遍, 然后看是不是按顺序的 for(int i=1; i<keys.size(); i++) if(keys.get(i-1).compareTo(keys.get(i)) > 0) return false; return true; } /** * 判断一棵树是否是平衡二叉树 * @return */ public boolean isBalanced(){ return isBalanced(root); } /** * 判断以Node为根的二叉树是否是一棵平衡二叉树，递归算法 * @param node * @return */ private boolean isBalanced(Node node) { if(node == null) return true; int balanceFactor = getBalanceFactor(node); if(Math.abs(balanceFactor) > 1) return false; return isBalanced(node.left) && isBalanced(node.right); // 父节点的平衡因子小于1, 子节点不一定也都小于1 } /** * 中序遍历, 保存到一个ArrayList中 * @param node * @param keys */ private void inOrder(Node node, ArrayList<K> keys) { if(node == null){ return; } inOrder(node.left, keys); keys.add(node.key); inOrder(node.right, keys); } private int getHeight(Node node){ if(node == null) return 0; return node.height; } /** * 向二分搜索书中添加元素(key, value) * @param key * @param value */ @Override public void add(K key, V value) { root = add(root, key, value); } /** * 获得节点node的平衡因子 * @param node * @return */ private int getBalanceFactor(Node node){ if(node == null) return 0; return getHeight(node.left) - getHeight(node.right); } // 对节点y进行向右旋转操作，返回旋转后新的根节点x // y x // / \ / \ // x T4 向右旋转 (y) z y // / \ - - - - - - - -> / \ / \ // z T3 T1 T2 T3 T4 // / \ // T1 T2 private Node rightRotate(Node y){ Node x = y.left; Node T3 = x.right; // 向右旋转 x.right = y; y.left = T3; // 更新height, 先更新y, 再更新x, 因为y在下面 y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; return x; } // 对节点y进行向左旋转操作，返回旋转后新的根节点x // y x // / \ / \ // T4 x 向左旋转 (y) y z // / \ - - - - - - - -> / \ / \ // T3 z T4 T3 T1 T2 // / \ // T1 T2 private Node leftRotate(Node y){ Node x = y.right; Node T3 = x.left; // 向左旋转 x.left = y; y.right = T3; // 更新height, 先更新y, 再更新x, 因为y在下面 y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; return x; } /** * 向以node为根的二分搜索树中插入元素(key, value)，递归算法 * 如果key已存在, 则更新value * @param node * @param key * @param value * @return 插入新节点后二分搜索树的根 */ private Node add(Node node, K key, V value) { if(node == null){ size++; return new Node(key, value); } if(key.compareTo(node.key) < 0) node.left = add(node.left, key, value); else if(key.compareTo(node.key) > 0) node.right = add(node.right, key, value); else node.value = value; // 1. 更新height node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); // 2. 计算平衡因子 int balanceFactor = getBalanceFactor(node); // 3. 维护平衡 // LL if(balanceFactor > 1 && getBalanceFactor(node.left) > 0) // 不用>=0, 因为node.left左右一定是不相等的, 如果相等的话, 那就是有两个节点导致了不平衡, 这是不可能的, 但是加上也可以啦 return rightRotate(node); // RR if(balanceFactor < -1 && getBalanceFactor(node.right) < 0) return leftRotate(node); // LR if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){ node.left = leftRotate(node.left); // 转化成LL的情况 return rightRotate(node); } // RL if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){ node.right = rightRotate(node.right); // 转化成RR的情况 return leftRotate(node); } // 平衡结束 return node; } /** * * @return 返回以node为根的二分搜索树的最小值所在的节点 */ private Node minimum(Node node){ if(node.left == null) return node; return minimum(node.left); } /** * 从二分搜索树中删除键为key的节点 * @param key * @return */ @Override public V remove(K key) { Node node = getNode(root, key); if(node != null){ root = remove(root, key); return node.value; } return null; } private Node remove(Node node, K key) { if(node == null) return null; Node retNode; if(key.compareTo(node.key) < 0){ node.left = remove(node.left, key); retNode = node; // 删除完节点后可能会打破平衡, 先不返回 } else if(key.compareTo(node.key) > 0){ node.right = remove(node.right, key); retNode = node; } else{ // key.compareTo(node.key) == 0 // 删除节点左子树为空的情况 if(node.left == null){ Node rightNode = node.right; node.right = null; size--; retNode = rightNode; } // 删除节点右子树为空的情况 else if(node.right == null){ Node leftNode = node.left; node.left = null; size--; retNode = leftNode; } // 待删除节点左右子树均不为空的情况 else{ // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); successor.right = remove(node.right, successor.key); successor.left = node.left; node.left = null; node.right = null; // size--; removeMin已经改过size了 retNode = successor; } } if(retNode == null){ // retNode为空 return null; } // 1. 更新height retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right)); // 2. 计算平衡因子 int balanceFactor = getBalanceFactor(retNode); // 3. 维护平衡 // LL // getBalanceFactor(retNode.left) >= 0 的等于号是必须要的, 如果删除T4的话, // y 就会出现z, T3两个节点同时导致不平衡, 这在添加的时候不可能出现, // / \ 但在删除的时候可能出现 // x T4 // / \ // z T3 if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) return rightRotate(retNode); // RR if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) return leftRotate(retNode); // LR // getBalanceFactor(retNode.left) >= 0 的等于号何以省略, 因为 =0 就是上面的情况, 在上面用比较简单的方法就处理掉了 if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){ retNode.left = leftRotate(retNode.left); // 转化成LL的情况 return rightRotate(retNode); } // RL if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){ retNode.right = rightRotate(retNode.right); // 转化成RR的情况 return leftRotate(retNode); } // 平衡结束 return retNode; } /** * @return 以node为根节点的二分搜索树中，key所在的节点 */ private Node getNode(Node node, K key){ if(node == null){ return null; } if(key.equals(node.key)) return node; else if(key.compareTo(node.key) < 0) return getNode(node.left, key); else // key.compareTo(node.key) > 0 return getNode(node.right, key); } @Override public boolean contains(K key) { return getNode(root, key) != null; } @Override public V get(K key) { Node node = getNode(root, key); return node == null ? null : node.value; } @Override public void set(K key, V newValue) { Node node = getNode(root, key); if(node == null) throw new IllegalArgumentException(key + " doesn't exist!"); node.value = newValue; } // 仅测试用 public static void main(String[] args) { System.out.println("Pride and Prejudice"); ArrayList<String> words = new ArrayList<>(); if(FileOperation.readFile("on-the-road.txt", words)) { System.out.println("Total words: " + words.size()); AVLTree<String, Integer> map = new AVLTree<>(); for (String word : words) { if (map.contains(word)) map.set(word, map.get(word) + 1); else map.add(word, 1); } System.out.println("Total different words: " + map.getSize()); System.out.println("Frequency of PRIDE: " + map.get("pride")); System.out.println("Frequency of PREJUDICE: " + map.get("prejudice")); System.out.println("is BST: " + map.isBST()); System.out.println("is Balanced: " + map.isBalanced()); for(String word : words){ map.remove(word); if(!map.isBST() || !map.isBalanced()){ throw new RuntimeException("ERROR"); } } } System.out.println(); } }

把ALVTree包装一下就作为AVLMap, 如果不使用value, 只用key的话也可以作为AVLSet使用