一、基本概念
平衡二叉树：对于任意一个节点，左子树和右子树的差值不能大于1
例1：（满足）
例2：（不满足）
二、实现的主要操作：
1.定义height：标记当前节点的高度值
2.设定getBalanceFactor方法，计算左右子树差值的平衡因子
3.预定两个测试函数：测试自己实现的代码是否满足BST和AVL性质
4.四种旋转操作：LL、RR、LR、RL
//1.右旋转：
// 对节点y进行向右旋转操作，返回旋转后新的根节点x
// y x
// / \ / \
// x T4 向右旋转 (y) z y
// / \ - - - - - - - -> / \ / \
// z T3 T1 T2 T3 T4
// / \
// T1 T2// 2.对节点y进行向左旋转操作，返回旋转后新的根节点x
// y x
// / \ / \
// T1 x 向左旋转 (y) y z
// / \ - - - - - - - -> / \ / \
// T2 z T1 T2 T3 T4
// / \
// T3 T4//3.LR旋转：
// 对节点y进行向右旋转操作，返回旋转后新的根节点x
// y y
// / \ / \
// x T4 左孩子先旋转 z T4 父亲节点向左旋转 (y)
// / \ - - - - - - - -> / \ - - - - - - - - - -> 同上
// T1 z x T3
// / \ / \
// T2 T3 T1 T2//4.RL旋转：(同理可得)5.在BST的添加和删除过程中均需要对height进行维护，并进行四种旋转
三、实现的代码及注解：
1.BST
//**************************BST是原函数（没有平衡性，但是有二分搜索树的性质）***************//
package IMUHERO;
import java.util.ArrayList;public class BST<K extends Comparable<K>, V> {private class Node{public K key;public V value;public Node left, right;public Node(K key, V value){this.key = key;this.value = value;left = null;right = null;}}private Node root;private int size;public BST(){root = null;size = 0;}public int getSize(){return size;}public boolean isEmpty(){return size == 0;}// 向二分搜索树中添加新的元素(key, value)public void add(K key, V value){root = add(root, key, value);}// 向以node为根的二分搜索树中插入元素(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 // key.compareTo(node.key) == 0node.value = value;return node;}// 返回以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 // if(key.compareTo(node.key) > 0)return getNode(node.right, key);}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;}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;}// 返回以node为根的二分搜索树的最小值所在的节点private Node minimum(Node node){if(node.left == null)return node;return minimum(node.left);}// 删除掉以node为根的二分搜索树中的最小节点// 返回删除节点后新的二分搜索树的根private Node removeMin(Node node){if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}node.left = removeMin(node.left);return node;}// 从二分搜索树中删除键为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;if( key.compareTo(node.key) < 0 ){node.left = remove(node.left , key);return node;}else if(key.compareTo(node.key) > 0 ){node.right = remove(node.right, key);return node;}else{ // key.compareTo(node.key) == 0// 待删除节点左子树为空的情况if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}// 待删除节点右子树为空的情况if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}// 待删除节点左右子树均不为空的情况// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点// 用这个节点顶替待删除节点的位置Node successor = minimum(node.right);successor.right = removeMin(node.right);successor.left = node.left;node.left = node.right = null;return successor;}}}
2.AVLTree(既有二分搜索树的顺序性，又有平衡树的平衡性)
package IMUHERO;
import java.util.ArrayList;public class AVLTree<K extends Comparable<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;}public int getSize(){return size;}public boolean isEmpty(){return size == 0;}// 判断该二叉树是否是一棵二分搜索树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);}// 判断该二叉树是否是一棵平衡二叉树public boolean isBalanced(){return isBalanced(root);}// 判断以Node为根的二叉树是否是一棵平衡二叉树，递归算法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);}// 获得节点node的高度private int getHeight(Node node){if(node == null)return 0;return node.height;}// 获得节点node的平衡因子private int getBalanceFactor(Node node){if(node == null)return 0;return getHeight(node.left) - getHeight(node.right);}// 向二分搜索树中添加新的元素(key, value)public void add(K key, V value){root = add(root, key, value);}// 向以node为根的二分搜索树中插入元素(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 // key.compareTo(node.key) == 0node.value = value;// 更新heightnode.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));// 计算平衡因子int balanceFactor = getBalanceFactor(node);
// if(Math.abs(balanceFactor) > 1)
// System.out.println("unbalanced : " + balanceFactor);//以下开始维护平衡因子******************************************************//if (balanceFactor>1&&getBalanceFactor(node.left)>=0){return rightRotate(node);}if (balanceFactor<-1&&getBalanceFactor(node.right)<0){return leftRotate(node);}if (balanceFactor>1&&getBalanceFactor(node.left)<0){return LRrotate(node);}if (balanceFactor<-1&&getBalanceFactor(node.right)>0){return RLrotate(node);}return node;}// 返回以node为根节点的二分搜索树中，key所在的节点//1.右旋转：// 对节点y进行向右旋转操作，返回旋转后新的根节点x// y x// / \ / \// x T4 向右旋转 (y) z y// / \ - - - - - - - -> / \ / \// z T3 T1 T2 T3 T4// / \// T1 T2public Node rightRotate(Node node){Node x=node.left;Node T3=x.right;x.right=node;node.left=T3;//更新高度，由图可见只有x,y的高度发生了变化node.height=Math.max(getHeight(node.left),getHeight(node.right))+1;x.height=Math.max(getHeight(x.left),getHeight(x.right))+1;return x;}// 2.对节点y进行向左旋转操作，返回旋转后新的根节点x// y x// / \ / \// T1 x 向左旋转 (y) y z// / \ - - - - - - - -> / \ / \// T2 z T1 T2 T3 T4// / \// T3 T4public Node leftRotate(Node node){Node x=node.right;Node T2=x.left;x.left=node;node.right=T2;//更新高度，同理只有y和x发生了高度改变node.height=Math.max(getHeight(node.left),getHeight(node.right))+1;x.height=Math.max(getHeight(x.left),getHeight(x.right));return x;}//3.LR旋转：// 对节点y进行向右旋转操作，返回旋转后新的根节点x// y y// / \ / \// x T4 左孩子先旋转 z T4 父亲节点向左旋转 (y)// / \ - - - - - - - -> / \ - - - - - - - - - -> 同上// T1 z x T3// / \ / \// T2 T3 T1 T2public Node LRrotate(Node node){node.left= leftRotate(node.left);return rightRotate(node);}//4.RL旋转：(同理可得)public Node RLrotate(Node node){node.right= rightRotate(node.right);return leftRotate(node);}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 // if(key.compareTo(node.key) > 0)return getNode(node.right, key);}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;}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;}// 返回以node为根的二分搜索树的最小值所在的节点private Node minimum(Node node){if(node.left == null)return node;return minimum(node.left);}// 删除掉以node为根的二分搜索树中的最小节点// 返回删除节点后新的二分搜索树的根private Node removeMin(Node node){if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}node.left = removeMin(node.left);return node;}// 从二分搜索树中删除键为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{ // key.compareTo(node.key) == 0// 待删除节点左子树为空的情况if(node.left == null){Node rightNode = node.right;node.right = null;size --;retNode=rightNode;}// 待删除节点右子树为空的情况if(node.right == null){Node leftNode = node.left;node.left = null;size --;retNode=leftNode;}// 待删除节点左右子树均不为空的情况// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点// 用这个节点顶替待删除节点的位置else {Node successor = minimum(node.right);successor.right = removeMin(node.right);successor.left = node.left;node.left = node.right = null;retNode=successor;}}if (retNode==null)return null;retNode.height=1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));// 计算平衡因子int balanceFactor = getBalanceFactor(retNode);// 平衡维护//LLif (balanceFactor>1&&getBalanceFactor(node.left)>=0){return rightRotate(node);}//RRif (balanceFactor<-1&&getBalanceFactor(node.right)<0){return leftRotate(node);}//LRif (balanceFactor>1&&getBalanceFactor(node.left)<0){return LRrotate(node);}//RLif (balanceFactor<-1&&getBalanceFactor(node.right)>0){return RLrotate(node);}return retNode;}}
注：文中图片引用慕课liuyubobobo老师的课程讲解，主要目的是为了总结自己的学习历程，分享心得体会，如有转发请标注此项。