之前实现的二分搜索树有可能退化成一个链表
AVL由俄罗斯科学家G.M.Adelson-Velsky E.M.Landis在1962年的论文首次提出，是最早的自平衡的自平衡二叉树
- 什么是平衡二叉树？
满二叉树：每一层都满足Math.pow(2,h)这个关系， h是深度
完全二叉树：从上到下，从左到右一层一层的铺，如果没有铺满成满二叉树，那么空缺的部分一定在最右边
平衡二叉树：对于叶子结点，最大的深度值和最小的深度值不超过1，(完全二叉树也是一个平衡二叉树，线段二叉树也是一个平衡二叉树)
AVL中的平衡二叉树的定义比较宽松：对于任意一个节点，左子树和右子树的高度差不超过1
平衡二叉树.png
为每个节点标注高度:heifht
平衡因子：左子树高度减去右子数高度
平衡因子.png
检查一棵树是否为二分搜索树(左小右大)，需要判断中序遍历是否是从小到大的排序,检查这个数是否为平衡二叉树(非严格)，需要判断每个节点的左右高度是否小于等于1
旋转操作的基本原理
AVL树的左旋转和右旋转,什么时候维护平衡性?
什么时候维护平衡.png
看子树，那个高度大，就把谁放在父节点位置！
这里以左倾斜，右旋转为例
- 递归到平衡因为因子为2,且左子树的平衡因子大于等于0的情况`rightRotateLeft`
右旋转原理1.png
- 递归到平衡因为因子为2,且左子树的平衡因子小于0的情况(左子高-右子高=-1)
rightRotateRight
右旋转原理2.png
对应的右倾斜，原理和左倾斜是一样的
- 平衡因子为-2，右子树的平衡因子为小于等于0
leftRotateRight
左旋转1.png
- 平衡因子为-2，右子树的平衡因子为1
leftRotateLeft
左旋转2.png
补充：Collection.sort(一个ArrayList或者什么数组) ，可以对他进行排序
删除一个元素怎样维护自平衡
原理和add里面的一样，递归维护一下高度和平衡！
代码实现
- AVLTree
package AVL;
import java.lang.ref.ReferenceQueue;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class AVLTree<K extends Comparable<K>, V>{
private class Node{
public K key;
public V value;
public Node left, right;
int height;
public Node(K key, V value){
this.key = key;
this.value = value;
this.left = null;
this.right = null;
this.height = 1;
}
}
private Node root;
private int size;
public AVLTree() {
this.root = null;
size = 0;
}
public int getSize(){
return this.size;
}
public boolean isEmpty(){
return this.size == 0;
}
// 层序遍历 并打印结果
public void levelOrer() {
ArrayList<K> levelO = new ArrayList<>();
LinkedList<Node> arrayQ = new LinkedList<>();
Node node;
arrayQ.add(root);
while(!arrayQ.isEmpty()) {
node = arrayQ.remove();
if(node == null)
break;
levelO.add(node.key);
if(node.left != null)
arrayQ.add(node.left);
if(node.right != null)
arrayQ.add(node.right);
}
System.out.println(levelO);
}
// 判断该二叉树是否是一颗二分搜索树，
// 对于此类，如果满足二分搜索树，必须满足中序遍历是递增的
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;
}
private void inOrder(Node node, ArrayList<K> keys) {
if(node == null)
return;
inOrder(node.left, keys);
keys.add(node.key);
inOrder(node.right, keys);
}
// 判断当前这棵树是否为一颗宽松的平衡二叉树
// 每一个节点的左右高度差不超过1
public boolean isBalanced() {
return isBalanced(root);
}
private boolean isBalanced(Node node) {
if (node == null)
return true;
int charge = getBalanceFactor(node);
if(Math.abs(charge) > 1)
return false;
return isBalanced(node.left) && isBalanced(node.right);
}
// @@@ 获得node节点的高度
public int getHeight(Node node) {
if(node == null)
return 0;
return node.height;
}
// @@@ 获得节点node的平衡因子
public int getBalanceFactor(Node node) {
if(node == null)
return 0;
return getHeight(node.left) - getHeight(node.right);
}
// @@@ 每次添加都需要重新计算树的高度，同样时利用递归挂载的思想
/**向二分搜索树中添加元素*/
public void add(K key, V value){
root = add(root, key, value);
}
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;
}
// 递归挂在计算节点的高度，如果高度相比之前发生了变化，
// 就维护下平衡，如果高度没有变化，则不需要维护平衡了
int heightNow = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
if (node.height != heightNow) {
node.height = heightNow;
// 测试：计算平衡因子
int balanceFactor = getBalanceFactor(node);
// 这个地方进行平衡因子判断并进行相应的左右旋转操作，有四种情况
// LL
if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
return rightRotateLeft(node);
// RR
if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
return leftRotateRight(node);
// LR
if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
return rightRotateRight(node);
/** 波波老师的思路，现将左节点左旋转，然后在将此节点右旋转，
* 而我的想法是一步到位旋转！
node.left = leftRotateRight(node.left);
return rightRotateLeft(node);
*/
}
if(balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
return leftRotateLeft(node);
/** 原理同上
node.right = rightRotateLeft(node.right);
return leftRotateRight(node);
*/
}
}
return node;
}
/** @引起非平衡的添加的节点在平衡因子左节点的左节点部分
* y x
* / \ / \
* x t4 向右旋转(y) z y
* / \ - - - - - - > / \ / \
* z t3 t1 t2 t3 t4
* /\
* t1 t2
* */
private Node rightRotateLeft(Node y) {
Node x = y.left;
Node t3 = x.right;
// 向右旋转过程
x.right = y;
y.left = t3;
// 更新 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 z
* / \ / \
* x t4 向右旋转(y) x y
* / \ - - - - - - > / \ / \
* t3 z t3 t1 t2 t4
* /\
* t1 t2
*
* */
private Node rightRotateRight(Node y) {
Node x = y.left;
Node z = x.right;
Node t1 = z.left;
Node t2 = z.right;
// 向右旋转操作
z.left = x;
z.right = y;
x.right = t1;
y.left = t2;
// 维护一下 x,y,z的节点高度
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
z.height = Math.max(getHeight(z.left), getHeight(z.right)) + 1;
return z;
}
/**@引起非平衡的添加的节点在平衡因子右节点的右节点部分
* y x
* / \ / \
*t4 x 向左旋转(y) y z
* / \ - - - - - - > / \ / \
* t3 z t4 t3 t1 t2
* / \
* t1 t2
* */
private Node leftRotateRight(Node y) {
Node x = y.right;
Node t3 = x.left;
// 向右旋转
x.left = y;
y.right = t3;
// 维护 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 z
* / \ / \
* t4 x 向左旋转(y) y x
* / \ - - - - - - > / \ / \
* z t3 t4 t1 t2 t3
* /\
* t1 t2
* */
private Node leftRotateLeft(Node y) {
Node x = y.right;
Node z = x.left;
Node t1 = z.left;
Node t2 = z.right;
// 向左旋转
z.left = y;
z.right = x;
y.right = t1;
x.left = t2;
// 维护各个节点的高度
// 维护一下 x,y,z的节点高度
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
z.height = Math.max(getHeight(z.left), getHeight(z.right)) + 1;
return z;
}
/**返回以node为根节点的二分搜索树中，key所在的节点,调用的时候传入root*/
private Node getNode(Node node,K key){
if(node == null)
return null;
if(key.compareTo(node.key) == 0)
return node;
else if(key.compareTo(node.key) < 0)
return getNode(node.left, key);
else
return getNode(node.right, key);
}
public boolean contains(K key) {
return this.getNode(root, key) != null;
}
public V get(K key){
Node node = this.getNode(root, key);
return node == null? null : node.value;
}
public void set(K key, V value){
Node node = this.getNode(root, key);
if(node == null)
throw new IllegalArgumentException("Set failed, no such key");
node.value = value;
}
/**返回以node为根节点的二分搜索树的最小值所在的节点*/
private Node minimum(Node node){
if(node.left == null)
return node;
return minimum(node.left);
}
/**从二分搜索树中删除键为key的节点*/
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 {
/**综合考虑，分情况讨论
* 待删除的节点左子树为空*/
if(node.left == null){
Node rightNode = node.right;
size --;
node.right = null;
retNode = rightNode;
}
/**待删除的节点右子树为空*/
else if(node.right == null){
Node leftNode = node.left;
size --;
node.left = null;
retNode = leftNode;
} else {
/**待删除节点的左右均不为空
* 在待删除的右子树上寻找最小的节点来代替当前节点的位置
* 由于每次删除操作都需要维护平衡，这种情况下也不例外*/
Node successor = minimum(node.right);
node.right = remove(node.right, successor.key);
successor.left = node.left;
successor.right = node.right;
node.left = node.right = null;
retNode = successor;
}
}
// 当删除的为叶子结点，就不需要进行高度维护
if(retNode == null)
return null;
// 删除呢操作不能根据高度的变化进行判断，当前高度可能不会发生变化
// 但是树的平衡已经被打破！
retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;
int balanceFactor = getBalanceFactor(retNode);
// LL
if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
return rightRotateLeft(retNode);
// RR
if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0)
return leftRotateRight(retNode);
// LR
if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0)
return rightRotateRight(retNode);
if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0)
return leftRotateLeft(retNode);
return retNode;
}
}
- Main测试函数
public class Main {
public static void main(String[] args) {
AVLTree<Integer, Integer> avlTree = new AVLTree<>();
int[] arr = {7,6,5,4,3,2,1};
for(int number : arr) {
if(!avlTree.contains(number))
avlTree.add(number, 1);
else {
avlTree.add(number, avlTree.get(number) + 1);
}
}
avlTree.levelOrer();
System.out.println(avlTree.isBST());
System.out.println(avlTree.isBalanced());
for(int number : arr) {
avlTree.remove(number);
avlTree.levelOrer();
if(!avlTree.isBST())
throw new IllegalArgumentException("is not bst");
if(!avlTree.isBalanced())
throw new IllegalArgumentException("is not balanced");
}
System.out.println("Finally, everything is ok!");
}
}
AVL数的优化
AVL树的操作都是O(logn)级别的
思考：如果添加没有导致树的高度发生变化，那么父树就不需要维护高度了(注意：删除操作不能使用高度进行优化)
删除操作不能根据高度进行判断.png
AVL树的局限性：大名鼎鼎的红黑树平均性能要比AVL树的性能更优，红黑树的操作也是O(logn)级别的
基于AVL数实现集合和映射
基于AVL实现集合和映射的接口即可，相当于将AVL进行包装，这里就不在啰嗦的展示了
