AVL树
最早的平衡二叉树，在二分搜索树的基础上做了自平衡处理，保证不会退化成链表。
二叉树的分类
满二叉树：除了叶子节点，其他全部节点都有两个孩子节点。
完全二叉树：节点都是从左到右插入进来的，最后一层一定是叶子节点，不满的部分一定是在右边部分。简单来说，就是把元素排列成树的形状，元素从左到右，一层层的插入进来，那么元素不够的时候，缺失的部分一定是在最后一层的右边。叶子节点一定在倒数第一或第二层。
平衡二叉树：对于任意一个节点，左子树和右子树的高度差不能超过1。
平衡因子
平衡因子表示左子树跟右子树的高度差，因此每个节点也就引入了高度值，叶子节点的高度值默认设为1，父节点的高度为左右子树高度值的最大值再加1。
平衡维护时机
LL 和 RR 情况
当插入的元素在不平衡节点的左侧的左侧时，会导致平衡因子大于1的情况(即平衡被打破)，这种情况称之为 LL 的情况。同理，当插入的元素在不平衡节点的右侧的右侧时，平衡也会被打破，这种情况称之为 RR 的情况。
LL 的图示如下(RR情况同理)：
LR 和 RL 情况
当插入的元素在不平衡节点的左侧的右侧时，会导致平衡因子大于1的情况(即平衡被打破)，这种情况称之为 LR 的情况。同理，当插入的元素在不平衡节点的右侧的左侧时，平衡也会被打破，这种情况称之为 RL 的情况。
LR 的图示如下(RL情况同理)：
平衡维护方式
LL 情况
需要对打破平衡的节点进行右旋转操作，如下图所示， y 节点打破了平衡，我们对 y 进行一次右旋转操作，操作如图示：
RR 情况
需要对打破平衡的节点进行左旋转操作，如下图所示， y 节点打破了平衡，我们对 y 进行一次左旋转操作，操作如图示一样：
左旋转前图示如下：
左旋转后图示如下：
LR 情况
如下图所示，y 节点打破了平衡，我们需要对打破平衡的节点的左节点 x 进行左旋转操作，然后就转化成了 LL 的情况，再按 LL 情况处理即可：
RL 情况
如下图所示，y 节点打破了平衡，我们需要对打破平衡的节点的右节点 x 进行右旋转操作，然后就转化成了 RR 的情况，再按 RR 情况处理即可：
AVL树代码
public class AVLTree<K extends Comparable<K>, V> {
private Node root;
private int size;
/**
* 获取节点node的高度
*/
private int getHeight(Node node) {
return node == null ? 0 : node.height;
}
/**
* 获取节点对应的平衡因子，即左右子树的高度差
*/
private int getBalanceFactor(Node node) {
if (node == null) {
return 0;
} else {
return getHeight(node.left) - getHeight(node.right);
}
}
/**
* 判断该二叉树是否是一棵二分搜索树
*/
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;
}
/**
* 判断该二叉树是否是一棵平衡二叉树
*/
public boolean isBalanced() {
return isBalanced(root);
}
/**
* 判断以Node为根的二叉树是否是一棵平衡二叉树，递归算法
*/
private boolean isBalanced(Node node) {
if (node == null) {
return true;
}
if (Math.abs(getBalanceFactor(node)) > 1) {
return false;
}
return isBalanced(node.left) && isBalanced(node.right);
}
/**
* 右旋转
*/
private Node rightRorate(Node node) {
Node retNode = node.left;
Node x = retNode.right;
node.left = x;
retNode.right = node;
// 更新height，一定要先更新 node 的，后更新 retNode
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;
return retNode;
}
/**
* 右旋转
*/
private Node leftRorate(Node node) {
Node retNode = node.right;
Node x = retNode.left;
node.right = x;
retNode.left = node;
// 更新height，一定要先更新 node 的，后更新 retNode
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;
return retNode;
}
private void inOrder(Node node, ArrayList<K> keys) {
if (node == null) {
return;
}
inOrder(node.left, keys);
keys.add(node.key);
inOrder(node.right, keys);
}
// 向AVL树中添加新的元素(key, value)
public void add(K key, V value) {
root = add(root, key, value);
}
/**
* 向以node为根的AVL树中插入元素(key, value)，递归算法
* 返回插入新节点后AVL树的根
*/
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
if (node.key.compareTo(key) < 0) {
node.right = add(node.right, key, value);
} else if (node.key.compareTo(key) > 0) {
node.left = add(node.left, key, value);
} else {
node.value = value;
}
// 更新 height
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
// 平衡维护
if (getBalanceFactor(node) > 1 && getBalanceFactor(node.left) >= 0) {
//LL情况，需要右旋转
return rightRorate(node);
}
if (getBalanceFactor(node) > 1 && getBalanceFactor(node.left) < 0) {
//LR情况，需要左旋转，然后右旋转
node.left = leftRorate(node.left);
return rightRorate(node);
}
if (getBalanceFactor(node) < -1 && getBalanceFactor(node.right) <= 0) {
//RR情况，需要左旋转
return leftRorate(node);
}
if (getBalanceFactor(node) < -1 && getBalanceFactor(node.right) > 0) {
//RL情况，需要右旋转，然后左旋转
node.right = rightRorate(node.right);
return leftRorate(node);
}
return node;
}
/**
* 从AVL树中删除键为key的节点
*/
public V remove(K key) {
Node node = getNode(root, key);
if (node == null) {
return null;
} else {
root = remove(root, key);
return node.value;
}
}
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 {
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);
//注意这里，不能用removeMin方法，因为会打破平衡性（也可以在removeMin方法里进行平衡维护）
successor.right = remove(node.right, successor.key);
successor.left = node.left;
node.left = node.right = null;
retNode = successor;
}
}
//注意删除的是叶子节点时，retNode可能为null
if (retNode == null) {
return null;
}
// 更新 height
retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;
// 平衡维护
if (getBalanceFactor(retNode) > 1 && getBalanceFactor(retNode.left) >= 0) {
//LL情况，需要右旋转
return rightRorate(retNode);
}
//疑惑，为什么不能等于0
if (getBalanceFactor(retNode) > 1 && getBalanceFactor(retNode.left) < 0) {
//LR情况，需要左旋转，然后右旋转
node.left = leftRorate(retNode.left);
return rightRorate(retNode);
}
if (getBalanceFactor(retNode) < -1 && getBalanceFactor(retNode.right) <= 0) {
//RR情况，需要左旋转
return leftRorate(retNode);
}
//疑惑，为什么不能等于0
if (getBalanceFactor(retNode) < -1 && getBalanceFactor(retNode.right) > 0) {
//RL情况，需要右旋转，然后左旋转
retNode.right = rightRorate(retNode.right);
return leftRorate(retNode);
}
return retNode;
}
/**
* 向以 node 为根的树中找最小元素并返回
*/
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}
/**
* 向以 node 为根的树中寻找最大元素并返回
*/
private Node maximum(Node node) {
if (node.right == null) {
return node;
}
return maximum(node.right);
}
public boolean contains(K key) {
return getNode(root, key) != null;
}
public V get(K key) {
Node node = getNode(root, key);
return node == null ? null : node.value;
}
/**
* 向以 node 为根的树中查询key对应的结点,递归算法
*/
private Node getNode(Node node, K key) {
if (node == null) {
return null;
}
if (key.compareTo(node.key) < 0) {
return getNode(node.left, key);
} else if (key.compareTo(node.key) > 0) {
return getNode(node.right, key);
} else {
return node;
}
}
public void set(K key, V newValue) {
Node node = getNode(root, key);
if (node == null) {
throw new IllegalArgumentException(key + " does not exist!");
} else {
node.value = newValue;
}
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
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;
// 节点高度值默认为1
height = 1;
}
}
}
BST 和 AVLTree 的性能比较
BST 在元素按排序的方式插入时，会退化成链表，因为 BST 没有自平衡机制 。
public class AVLMain {
public static void main(String[] args) {
ArrayList<String> words = new ArrayList<>();
if (FileOperation.readFile("F:\\java_projects\\data_structure\\DataStructures\\src\\a-tale-of-two-cities.txt", words)) {
System.out.println("Total words: " + words.size());
// 排序之后，二分搜索树会退化成链表
Collections.sort(words);
// Test BST
long startTime = System.nanoTime();
BSTMap<String, Integer> bst = new BSTMap<>();
for (String word : words) {
if (bst.contains(word))
bst.set(word, bst.get(word) + 1);
else
bst.add(word, 1);
}
for(String word: words)
bst.contains(word);
long endTime = System.nanoTime();
double time = (endTime - startTime) / 1000000000.0;
System.out.println("BST: " + time + " s");
// Test AVL Tree
startTime = System.nanoTime();
AVLTree<String, Integer> avl = new AVLTree<>();
for (String word : words) {
if (avl.contains(word))
avl.set(word, avl.get(word) + 1);
else
avl.add(word, 1);
}
for (String word : words)
avl.contains(word);
endTime = System.nanoTime();
time = (endTime - startTime) / 1000000000.0;
System.out.println("AVL: " + time + " s");
}
System.out.println();
}
}
当 BST 退化成链表时，运行结果如下：
Total words: 141489
BST: 43.441510112 s
AVL: 0.112137956 s
当 BST 不退化链表时，运行结果如下：
Total words: 141489
BST: 0.305946419 s
AVL: 0.285817112 s
总结： BST 不退化成链表时，性能跟 AVLTree 相差不大，因为元素是随机进入时，两者的时间复杂度均为 O(logn)，当退化成链表时，BST 的复杂度会变成 O(n) ，此时性能相差较大。
底层为 AVLTree 的映射
我们可以对比基于 BST 实现的映射和基于 AVLTree 实现的映射的性能，总体来说 AVLTree 更优。
public class AVLMap<K extends Comparable<K>,V> implements Map<K,V> {
private AVLTree<K, V> tree;
public AVLMap() {
tree = new AVLTree<>();
}
@Override
public void add(K key, V value) {
tree.add(key,value);
}
@Override
public V remove(K key) {
return tree.remove(key);
}
@Override
public boolean contains(K key) {
return tree.contains(key);
}
@Override
public V get(K key) {
return tree.get(key);
}
@Override
public void set(K key, V newValue) {
tree.set(key,newValue);
}
@Override
public int getSize() {
return tree.getSize();
}
@Override
public boolean isEmpty() {
return tree.isEmpty();
}
}
底层为 AVLTree 的集合
我们可以对比基于 BST 实现的集合和基于 AVLTree 实现的集合的性能，总体来说 AVLTree 更优。
public class AVLSet<E extends Comparable<E>> implements Set<E> {
private AVLTree<E, Object> avlTree;
public AVLSet() {
avlTree = new AVLTree<>();
}
@Override
public void add(E e) {
avlTree.add(e,null);
}
@Override
public void remove(E e) {
avlTree.remove(e);
}
@Override
public boolean contains(E e) {
return avlTree.contains(e);
}
@Override
public int getSize() {
return avlTree.getSize();
}
@Override
public boolean isEmpty() {
return avlTree.isEmpty();
}
}