1. 定义：带有平衡条件的二叉搜索树。平衡条件为其每个节点的左子树和右子树的高度最多差1。该平衡条件保证了树的深度为O(log N).
2. 具体实现过程：
a. AVL树节点的定义：
声明了节点值，左右孩子节点和节点高度
/**
* 定义AVL树的节点
* @param <T>
*/
private class AVLTreeNode<T extends Comparable<T>>{
T key;//节点值
int height;//节点高度
AVLTreeNode<T> left;
AVLTreeNode<T> right;
public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right){
this.key = key;
this.left = left;
this.right = right;
this.height = 0;
}
}
b. AVL树中节点的查找：
先比较节点值与传入的值，再递归查找左右子树
/**
* 根据传入的值和树，实现在树中查找是否存在某个节点值为key
* @param x
* @param key
* @return
*/
private AVLTreeNode<T> search(AVLTreeNode<T> x, T key){
if (x == null){
return null;
}
//进行比较
int cmp = key.compareTo(x.key);
//查找左子树
if (cmp < 0){
return search(x.left, key);
}
//查找右子树
else if (cmp > 0){
return search(x.right, key);
}
//查找成功，返回
else {
return x;
}
}
public AVLTreeNode<T> search(T key){
return search(root, key);
}
非递归版查找
private AVLTreeNode<T> iterativeSearch(AVLTreeNode<T> x, T key){
while (x != null){
int cmp = key.compareTo(x.key);
if (cmp < 0){
x = x.left;
} else if (cmp > 0){
x = x.right;
} else {
return x;
}
}
return x;
}
public AVLTreeNode<T> iterativeSearch(T key){
return iterativeSearch(root, key);
}
3. 查找AVL树中的最值：
最大值：不断向右子树查找，直到某个节点的右孩子节点为空，则返回当前节点
private AVLTreeNode<T> maximum(AVLTreeNode<T> tree){
if (tree == null){
return null;
}
while (tree.right != null){
tree = tree.right;
}
return tree;
}
public T maximum(){
AVLTreeNode<T> p = maximum(root);
if (p != null){
return p.key;
}
return null;
}
最小值：不断向左子树查找，直到某个节点的左孩子节点为空，则返回当前结点
public T minimum(){
AVLTreeNode<T> p = minimum(root);
if (p != null){
return p.key;
}
return null;
}
private AVLTreeNode<T> minimum(AVLTreeNode<T> tree){
if (tree == null){
return null;
}
while (tree.left != null){
tree = tree.left;
}
return tree;
}
4. 对AVL树进行插入节点：
当我们进行插入操作时，若不会破坏AVL树平衡的特性，则直接插入即可，否则在插入完成之前我们要进行一些简单的修正，我们称其为旋转。
出现不平衡的四种情况，我们假定出现不平衡的节点为a.
1. 对 a 的左儿子的左子树进行一次插入
2. 对 a 的左儿子的右子树进行一次插入
3. 对 a 的右儿子的右子树进行一次插入
4. 对 a 的右儿子的左子树进行一次插入
其中情况1和情况3，我们通过对树的一次单旋转即可完成，而对于情况2和情况4，我们需要通过双旋转完成。
单旋转：
LL的旋转，即情况1：
single_rotation
/**
* 传入不平衡的节点，进行LL旋转，返回平衡后的节点
* @param k2
* @return
*/
private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2){
AVLTreeNode<T> k1;
//进行旋转
k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
//更新节点的高度
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), k2.height) + 1;
return k1;
}
RR旋转，即情况3:
RR_rotation
/**
* 实现RR旋转
* @param k1
* @return
*/
private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1){
AVLTreeNode<T> k2;
//进行旋转
k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
//更新高度
k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
k2.height = Math.max(height(k2.right),k1.height) + 1;
return k2;
}
双旋转：
LR旋转，即情况2
LR_Rotation
/**
* 实现LR旋转
* @param k3
* @return
*/
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3){
//获取到k1节点
AVLTreeNode<T> k1 = k3.left;
//对k1进行RR旋转
k3.left = rightRightRotation(k1);
//再对k3进行LL旋转
return leftLeftRotation(k3);
}
RL旋转，即情况4：
RL_Rotation
/**
* 实现RL旋转
* @param k1
* @return
*/
private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1){
//获取到k3节点
AVLTreeNode<T> k3 = k1.right;
//对k3节点进行LL旋转
k1.right = leftLeftRotation(k3);
//对k1节点进行RR旋转
return rightRightRotation(k1);
}
实现插入节点操作：
/**
* 实现插入节点的操作
* @param tree
* @param key
* @return
*/
private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key){
//若当前结点为空，则创建一个新节点，并返回
if (tree == null){
return new AVLTreeNode<T>(key, null, null);
}
//进行比较
int cmp = key.compareTo(tree.key);
//进入左子树
if (cmp < 0){
//对左子树进行递归插入
tree.left = insert(tree.left, key);
//若插入后，存在不平衡情况
if (height(tree.left) - height(tree.right) == 2){
//若插入的位置为左边，则进行LL旋转
if (key.compareTo(tree.left.key) < 0){
tree = leftLeftRotation(tree);
}
//若插入的位置在右边，则进行LR旋转
else {
tree = leftRightRotation(tree);
}
}
}
//进入右子树
else if (cmp > 0){
//对右子树进行递归插入
tree.right = insert(tree.right, key);
//若插入后，存在不平衡的情况
if (height(tree.right) - height(tree.left) == 2){
//若插入的位置在右边，则进行RR旋转
if (key.compareTo(tree.right.key) > 0){
tree = rightRightRotation(tree);
}
//若插入的位置在左边，则进行RL旋转
else {
tree = rightLeftRotation(tree);
}
}
}
//存在该节点了，不做操作
else {
System.out.println("添加失败：不允许添加相同的节点");
}
//更新节点的高度
tree.height = Math.max(height(tree.left), height(tree.right)) + 1;
return tree;
}
public void insert(T key){
root = insert(root, key);
}
实现删除节点操作：
/**
* 实现删除节点操作，并返回删除的节点
* @param tree
* @param delete
* @return
*/
private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> delete){
//没有删除的节点，直接返回空
if (tree == null || delete == null){
return null;
}
//进行比较
int cmp = delete.key.compareTo(tree.key);
//进入左子树
if (cmp < 0){
//对左边进行递归删除
tree.left = remove(tree.left, delete);
//存在不平衡的情况
if (height(tree.right) - height(tree.left) == 2){
//因为删除的是左子树节点，则要调整的为右子树节点
AVLTreeNode<T> r =tree.right;
//左大于右，则进行RL旋转
if (height(r.left) > height(r.right)){
tree = rightLeftRotation(tree);
}
//右高于左，则进行RR旋转
else {
tree = rightRightRotation(tree);
}
}
}
//进入右子树
else if (cmp > 0){
//进行递归删除
tree.right = remove(tree.right, delete);
//出现不平衡的情况
if (height(tree.left) - height(tree.right) == 2){
//删除的是右子树节点，因此要调整的是左子树
AVLTreeNode<T> l = tree.left;
//右高于左，则进行LR旋转
if (height(tree.right) > height(tree.left)){
tree = leftRightRotation(tree);
}
//左高于右，则进行LL旋转
else {
tree = leftLeftRotation(tree);
}
}
}
//进行删除当前结点
else {
//左右孩子都不为空
if ((tree.left != null) && (tree.right != null)){
//左高于右，那么要调整的是左子树
if (height(tree.left) > height(tree.right)){
//获取到左子树的最大节点，因为此节点不含孩子
AVLTreeNode<T> max = maximum(tree.left);
//左子树最大节点替换当前结点
tree.key = max.key;
//删除左子树的最大节点
tree.left = remove(tree.left,max);
} else {
//获取右子树的最小节点
AVLTreeNode<T> min = minimum(tree.right);
//用右子树的最小节点替换当前结点
tree.key = min.key;
//删除右子树的最小节点
tree.right = remove(tree.right, min);
}
}
//若只存在左孩子或右孩子，则使孩子替换当前结点
else {
tree = (tree.left != null) ? tree.left : tree.right;
}
}
return tree;
}
public void remove(T key){
AVLTreeNode<T> z = search(root, key);
if (z != null){
root = remove(root, z);
}
}
