1. 简介
AVL树得名于它的发明者---前苏联的数学家G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。
2. 定义
AVL树其实是一棵高度平衡的二叉搜索树，它是依靠平衡因子来维持树的高度。
- 对于每个结点来说，它的左右子树高度差的绝对值（平衡因子）不会超过1。
- 它具有和二叉搜索树一样的性质，也就是说除了二叉搜索树中那些会改变树的高度的操作（插入，删除），其他的操作都可以用在AVL树中。
3. 实现
因为AVL树除了插入，删除这些可能改变树高度的操作之外，其他操作的与二叉搜索树无异，所以这里只讲插入和删除操作。
- 每个叶子结点的高度都为1
- 每个结点都有高度，其高度为左右孩子中最高孩子的高度加上1
- 每个结点的高度差为左子树的高度减去右子树的高度
- 每当插入或删除一个结点后，可能导致某个结点的平衡因子超过1，这时候就需要对以这个结点进行旋转操作来维持平衡。
旋转操作：
1. 左左旋转：
需要进行左左旋转
如上图，当插入一个0001这个结点后，导致0003的平衡因子超过1，此时0003结点需要通过左左旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的左孩子的左孩子上，取名左左旋转，旋转后的结果如下图：
左左旋转后
代码实现：
//左左旋转
private Node rotationLeft(Node node){
Node x = node.left;
node.left = x.right;
x.right = node;
updateHeight(node);
return x;
}
2. 右右旋转：
需要进行右右旋转
如上图，当插入一个0003这个结点后，导致0001的平衡因子超过1，此时0003结点需要通过右右旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的右孩子的右孩子上，取名右右旋转，旋转后的结果如下图：
右右旋转后
代码实现：
//右右旋转
private Node rotationRight(Node node){
Node x = node.right;
node.right = x.left;
x.left = node;
updateHeight(node);
return x;
}
3. 右左旋转：
需要进行右左旋转
如上图，当插入一个0002这个结点后，导致0001的平衡因子超过1，此时0001结点需要通过右左旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的右孩子的左孩子上，取名右左旋转，旋转后的结果如下图：
右左旋转后
代码实现：
//右左旋转
private Node rotationRightLeft(Node node){
node.right = rotationLeft(node.right);
updateHeight(node.right);
return rotationRight(node);
}
4.左右旋转：
image.png
如上图，当插入一个0002这个结点后，导致0003的平衡因子超过1，此时0003结点需要通过左右旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的左孩子的右孩子上，取名左右旋转，旋转后的结果如下图：
左右旋转后
代码实现：
//左右旋转
private Node rotationLeftRight(Node node){
node.left = rotationRight(node.left);
updateHeight(node.left);
return rotationLeft(node);
}
4. 时间复杂度
由于AVL树是一个高度平衡的二叉搜索树，所以树的高度几乎是lgN，所以无论查找，插入还是删除操作最坏情况的时间复杂度为O(lgN)。
5. 代码实现
其中的插入删除操作都是用递归来实现的
import java.util.*;
public class AVL <Key extends Comparable<Key>, Value>{
private class Node{
Key key;
Value value;
int height;
Node left;
Node right;
public Node(Key key, Value value, int height, Node left, Node right){
this.key = key;
this.value = value;
this.height = height;
this.left = left;
this.right = right;
}
}
private Node root;
private int size;
public int size(){
return size;
}
//获取树高度
public int height(Node node){
return node == null ? 0 : node.height;
}
//高度差
private int altitude(Node node){
return height(node.left) - height(node.right);
}
//更新树高度
private void updateHeight(Node node){
node.height = Math.max(height(node.left), height(node.right)) + 1;
}
//右旋
private Node rotationRight(Node node){
Node x = node.right;
node.right = x.left;
x.left = node;
updateHeight(node);
return x;
}
//左旋
private Node rotationLeft(Node node){
Node x = node.left;
node.left = x.right;
x.right = node;
updateHeight(node);
return x;
}
//左右旋转
private Node rotationLeftRight(Node node){
node.left = rotationRight(node.left);
updateHeight(node.left);
return rotationLeft(node);
}
//右左旋转
private Node rotationRightLeft(Node node){
node.right = rotationLeft(node.right);
updateHeight(node.right);
return rotationRight(node);
}
//平衡
private Node balance(Node node, int altitude){
if (altitude == 2)
node = height(node.left.left) > height(node.left.right) ? rotationLeft(node) : rotationLeftRight(node);
else if (altitude == -2)
node = height(node.right.left) > height(node.right.right) ? rotationRightLeft(node) : rotationRight(node);
updateHeight(node);
return node;
}
//插入
public void put(Key key, Value value){
root = put(key, value, root);
++size;
}
private Node put(Key key, Value value, Node node) {
if (node == null)
return new Node(key, value, 1, null, null);
int cmp = key.compareTo(node.key);
if (cmp < 0)
node.left = put(key, value, node.left);
else if (cmp > 0)
node.right = put(key, value, node.right);
else {
node.value = value;
return node;
}
return balance(node, altitude(node));
}
private Node max(Node node){
if (node == null)
return null;
while (node.right != null)
node = node.right;
return node;
}
public Value max() {
return root == null ? null : max(root).value;
}
public void deleteMax(){
if (root != null) {
root = deleteMax(root);
--size;
}
}
private Node deleteMax(Node node){
if (node.right == null)
return node.left;
node.right = deleteMax(node.right);
return balance(node, altitude(node));
}
private Node deleteMin(Node node){
if (node.left == null)
return node.right;
node.left = deleteMin(node.left);
return balance(node, altitude(node));
}
public void deleteMin(){
if (root != null) {
root = deleteMin(root);
--size;
}
}
public Value delete(Key key){
Node node = delete(key, root);
if (node != null)
return node.value;
return null;
}
private Node delete(Key key, Node node){
if (node == null)
return null;
int cmp = key.compareTo(node.key);
if (cmp < 0)
node.left = delete(key, node.left);
else if (cmp > 0)
node.right = delete(key, node.right);
else {
--size;
if (node.left == null)
return node.right;
if (node.right == null)
return node.left;
Node x = max(node.right);
node.key = x.key;
node.value = x.value;
node.right = deleteMax(node.right);
}
return balance(node, altitude(node));
}
//中序遍历
private void inorderTraverse(Node node, Set<Key> keySet){
if (node == null)
return;
inorderTraverse(node.left, keySet);
keySet.add(node.key);
inorderTraverse(node.right, keySet);
}
//返回一个把键从小到大排序的迭代器
public Iterable<Key> keySet(){
Set<Key> keySet = new TreeSet<>();
inorderTraverse(root, keySet);
return keySet;
}
public static void main(String[] args){
AVL<Integer, String> tree = new AVL<>();
Random random = new Random();
for (int i = 0; i < 500; ++i)
tree.put(random.nextInt(), "naoko" + i);
tree.deleteMax();
tree.deleteMin();
for (int i : tree.keySet())
System.out.println(i);
System.out.println("符号表的大小：" + tree.size());
}
}
网友评论