一方咆、平衡二叉樹
平衡二叉樹 也稱平衡二叉搜索樹（Self-balancing binary search tree）是一種結(jié)構(gòu)平衡的二分搜索樹薄腻。
平衡二叉樹由二分搜索樹發(fā)展而來倔矾，在二分搜索樹的基礎(chǔ)上平衡二叉樹需要滿足兩個條件：
- 1够委、它的左右兩個子樹的高度差的絕對值不超過1昼榛。
- 2锌雀、左右兩個子樹都是一棵平衡二叉樹
平衡因子
某結(jié)點的左子樹與右子樹的高度(深度)差即為該結(jié)點的平衡因子（BF,Balance Factor）。平衡二叉樹上所有結(jié)點的平衡因子只可能是 -1翰绊，0 或 1佩谷。如果某一結(jié)點的平衡因子絕對值大于1則說明此樹不是平衡二叉樹。為了方便計算每一結(jié)點的平衡因子我們可以為每個節(jié)點賦予height這一屬性监嗜，表示此節(jié)點的高度谐檀。
常見的平衡二叉搜索樹有：
- AVL樹
- 紅黑樹
- Treap
二、AVL樹
AVL樹 是由 G. M. Adelson- V elsky 和 E. M. Landis于1962年提出秤茅。AVL樹是最早的平衡二叉樹稚补。
AVL樹維護自身的平衡涉及到兩個概念：
- 1、節(jié)點的高度
- 2框喳、節(jié)點的平衡因子
節(jié)點的高度就是從根節(jié)點到該節(jié)點的邊的總和
節(jié)點的 平衡因子 是左子樹的高度減去它的右子樹的高度
帶有平衡因子1课幕、0或 -1的節(jié)點被認為是平衡的厦坛，因為它的左右子樹高度差不超過 1。
面的兩張圖片乍惊，左邊的是AVL樹杜秸，它的任何節(jié)點的兩個子樹的高度差別都<=1；而右邊的不是AVL樹润绎，因為7的兩顆子樹的高度相差為2(以2為根節(jié)點的樹的高度是3撬碟，而以8為根節(jié)點的樹的高度是1)。
三莉撇、AVL樹代碼實現(xiàn)
3.1 基礎(chǔ)設(shè)計
首先我們可以設(shè)計出AVL樹節(jié)點呢蛤，并且實現(xiàn)一些簡單通用的方法供后續(xù)操作。
public class AVLTree<K extends Comparable<K>, V> {
//AVLTree 樹節(jié)點類
private class Node<K extends Comparable<K>, V>{
public K key;
public V value;
public Node<K, V> left;
public Node<K, V> right;
//當前節(jié)點所處的高度值
public int height;
public Node(K key, V value){
this.key = key;
this.value = value;
this.left = null;
this.right = null;
//初始化新的節(jié)點都是葉子節(jié)點棍郎，高度都為1
this.height = 1;
}
@Override
public String toString() {
return key.toString() +" : " + value.toString();
}
}
// 根節(jié)點
private Node<K, V> root;
// 樹容量
private Integer size;
public AVLTree(){
root = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int getSize() {
return size;
}
/**
* 判斷該二叉樹是否是一棵平衡二叉樹
* @return
*/
private boolean isBalanced(){
return isBalanced(root);
}
/**
* 判斷該二叉樹是否是一棵平衡二叉樹, 遞歸調(diào)用函數(shù)
* @param node
* @return
*/
private boolean isBalanced(Node<K,V> node){
//node == null 代表該樹是一顆平衡二叉樹其障，
//平衡二叉樹左右子樹高度相差不超過1
// 因為空樹的左右子樹高度相差不超過1
if(node == null){
return true;
}
//獲取平衡因子
int balanceFactor = getBalanceFactor(node);
//左右子樹高度相差超過1，則不是平衡二叉樹
if(Math.abs(balanceFactor) > 1){
return false;
}
//遞歸調(diào)用該節(jié)點的左右子樹涂佃，判斷是否是平衡二叉樹
return isBalanced(node.left) && isBalanced(node.right);
}
/**
* 返回node節(jié)點的高度值
* @param node
* @return
*/
private int getHeight(Node<K, V> node){
if(node == null){
return 0;
}
return node.height;
}
/**
* 獲取節(jié)點node的平衡因子
* @param node
* @return
*/
private int getBalanceFactor(Node<K, V> node){
if(node == null){
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
}
3.2 添加節(jié)點
往平衡二叉樹中添加節(jié)點很可能會導致二叉樹失去平衡励翼，所以我們需要在每次插入節(jié)點后進行平衡的維護操作。插入節(jié)點破壞平衡性有如下四種情況：
3.2.1 LL（右旋）
LL的意思是向左子樹（L）的左孩子（L）中插入新節(jié)點后導致不平衡辜荠，這種情況下需要右旋操作汽抚，而不是說LL的意思是右旋，后面的也是一樣伯病。
我們將這種情況抽象出來造烁，得到下圖：
我們需要對節(jié)點y進行平衡的維護。步驟如下圖所示：
* 右旋轉(zhuǎn)
* // 對節(jié)點y進行向右旋轉(zhuǎn)操作狱从，返回旋轉(zhuǎn)后新的根節(jié)點x
* // y x
* // / \ / \
* // x T4 向右旋轉(zhuǎn) (y) z y
* // / \ - - - - - - - -> / \ / \
* // z T3 T1 T2 T3 T4
* // / \
* // T1 T2
/**
* 右旋轉(zhuǎn)
* // 對節(jié)點y進行向右旋轉(zhuǎn)操作膨蛮，返回旋轉(zhuǎn)后新的根節(jié)點x
* // y x
* // / \ / \
* // x T4 向右旋轉(zhuǎn) (y) z y
* // / \ - - - - - - - -> / \ / \
* // z T3 T1 T2 T3 T4
* // / \
* // T1 T2
* @param y
* @return
*/
private Node<K, V> rightRotate(Node<K, V> y){
Node<K, V> x = y.left;
Node<K, V> T3 = x.right;
//向右旋轉(zhuǎn)過程
x.right = y;
y.left = T3;
//更新節(jié)點的高度height值
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
3.2.2 RR（左旋）
我們將這種情況抽象出來叠纹，得到下圖：
我們需要對節(jié)點y進行平衡的維護季研。步驟如下圖所示：
* 向左旋轉(zhuǎn)
* // 對節(jié)點y進行向左旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點x
* // y x
* // / \ / \
* // T1 x 向左旋轉(zhuǎn) (y) y z
* // / \ - - - - - - - -> / \ / \
* // T2 z T1 T2 T3 T4
* // / \
* // T3 T4
/**
* 向左旋轉(zhuǎn)
* // 對節(jié)點y進行向左旋轉(zhuǎn)操作誉察，返回旋轉(zhuǎn)后新的根節(jié)點x
* // y x
* // / \ / \
* // T1 x 向左旋轉(zhuǎn) (y) y z
* // / \ - - - - - - - -> / \ / \
* // T2 z T1 T2 T3 T4
* // / \
* // T3 T4
* @param y
* @return
*/
private Node<K, V> leftRotate(Node<K, V> y){
Node<K, V> x = y.right;
Node<K, V> T2 = x.left;
//向左旋轉(zhuǎn)過程
x.left = y;
y.right = T2;
//更新節(jié)點的高度height值
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
3.2.3 LR
我們將這種情況抽象出來与涡，得到下圖：
我們需要對節(jié)點y進行平衡的維護。步驟如下圖所示：
3.2.4 RL
我們將這種情況抽象出來持偏，得到下圖：
我們需要對節(jié)點y進行平衡的維護驼卖。步驟如下圖所示：
添加節(jié)點代碼
/**
* 向AVL樹添加新的元素(key,value)
* @param key
* @param value
*/
public void add(K key, V value){
//向根節(jié)點添加元素e
root = add(root, key, value);
}
/**
* 向以node為根的AVL樹中插入元素(key,value)，遞歸算法
* @param node
* @param key
* @param value
* @return 返回插入新元素的AVL樹的根
*/
private Node<K, V> add(Node<K, V> node, K key, V value){
if(node == null){
size ++;
return new Node<>(key, value);
}
//遞歸調(diào)用鸿秆，元素添加到node.left
if(key.compareTo(node.key) < 0){
node.left = add(node.left, key, value);
}else if(key.compareTo(node.key) > 0){
//遞歸調(diào)用酌畜，元素添加到node.right
node.right = add(node.right, key, value);
}else {
node.value = value;
}
//更新節(jié)點的高度height
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
//計算平衡因子
int balanceFactor = getBalanceFactor(node);
//平衡維護
//LL
// 左子樹比右子樹高度超過了1，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在左子樹的左子樹的左側(cè)
if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0){
//右旋轉(zhuǎn)
return rightRotate(node);
}
//RR
// 右子樹比左子樹高度超過了1卿叽，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在右子樹的右子樹的右側(cè)
if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0){
//左旋轉(zhuǎn)
return leftRotate(node);
}
//LR
// 左子樹比右子樹高度超過了1桥胞，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在左子樹的左子樹的右側(cè)
if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
//先對node.left進行左旋轉(zhuǎn)
node.left = leftRotate(node.left);
//然后對node進行右旋轉(zhuǎn)
return rightRotate(node);
}
//RL
// 右子樹比左子樹高度超過了1恳守，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在右子樹的右子樹的左側(cè)
if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){
//先對node.right進行右旋轉(zhuǎn)
node.right = rightRotate(node.right);
//然后對node進行左旋轉(zhuǎn)
return leftRotate(node);
}
//返回當前根節(jié)點
return node;
}
3.3 刪除節(jié)點
在刪除AVL樹節(jié)點前需要知道二分搜索樹的節(jié)點刪除操作，和二分搜索樹刪除節(jié)點不同的是我們刪除AVL樹的節(jié)點后需要進行平衡的維護操作贩虾。
/**
* 返回以node為根的二分搜索樹的最小值所在的節(jié)點
* @param node
* @return
*/
private Node<K, V> minimum(Node<K, V> node){
if(node.left == null){
return node;
}
return minimum(node.left);
}
/**
* 從二分搜索樹中刪除元素鍵為key的節(jié)點, 并返回value, 不存在返回null
* @param key
* @return
*/
public V remove(K key){
Node<K, V> node = getNode(root, key);
if(node == null){
//不存在直接返回null
return null;
}
//存在
root = remove(root, key);
return node.value;
}
/**
* 刪除以node為根的二分搜索樹中鍵為key的節(jié)點催烘，遞歸遞歸方式
* 返回刪除節(jié)點后新的二分搜索樹的根
* @param node
* @param key
* @return
*/
private Node<K, V> remove(Node<K, V> node, K key){
//節(jié)點為空，直接返回
if(node == null){
return null;
}
//聲明要返回去的node
Node<K, V> retNode;
if(key.compareTo(node.key) < 0){
//待刪除元素key小于當前節(jié)點的鍵缎罢，向左遞歸尋找
node.left = remove(node.left, key);
retNode = node;
}else if(key.compareTo(node.key) > 0){
//待刪除元素key大于當前節(jié)點的鍵伊群，向右遞歸尋找
node.right = remove(node.right, key);
retNode = node;
}else {
//待刪除節(jié)點左子樹為空
if(node.left == null){
Node<K, V> rightNode = node.right;
node.right = null;
size --;
retNode = rightNode;
}
//待刪除節(jié)點右子樹為空
else if(node.right == null){
Node<K, V> rightNode = node.left;
node.left = null;
size --;
retNode = rightNode;
}else {
//待刪除節(jié)點左、右子樹不為空
//找到比待刪除節(jié)點大的最小節(jié)點策精，即待刪除節(jié)點右子樹最小節(jié)點
//用這個節(jié)點頂替待刪除節(jié)點的位置
//找到比待刪除節(jié)點大的最小節(jié)點舰始，即待刪除節(jié)點右子樹最小節(jié)點
Node<K, V> successor = minimum(node.right);
//刪除比待刪除節(jié)點大的最小節(jié)點，并將返回值給succeer的右孩子
//successor.right = removeMin(node.right);
successor.right = remove(node.right, successor.key);
//node.left賦值給successor.left
successor.left = node.left;
//node節(jié)點和二分搜索樹脫離關(guān)系
node.left = node.right = null;
retNode = successor;
}
}
if(retNode == null){
//如果刪除了該節(jié)點咽袜，返回的二叉樹節(jié)點的根節(jié)點為空的話
return null;
}
//更新節(jié)點的高度height
retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;
//計算平衡因子
int balanceFactor = getBalanceFactor(retNode);
//平衡維護
//LL
// 左子樹比右子樹高度超過了1蔽午，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在左子樹的左子樹的左側(cè)
if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0){
//右旋轉(zhuǎn)
return rightRotate(retNode);
}
//RR
// 右子樹比左子樹高度超過了1，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在右子樹的右子樹的右側(cè)
if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0){
//左旋轉(zhuǎn)
return leftRotate(retNode);
}
//LR
// 左子樹比右子樹高度超過了1酬蹋，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在左子樹的左子樹的右側(cè)
if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
//先對node.left進行左旋轉(zhuǎn)
retNode.left = leftRotate(retNode.left);
//然后對node進行右旋轉(zhuǎn)
return rightRotate(retNode);
}
//RL
// 右子樹比左子樹高度超過了1及老，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在右子樹的右子樹的左側(cè)
if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){
//先對node.right進行右旋轉(zhuǎn)
retNode.right = rightRotate(retNode.right);
//然后對node進行左旋轉(zhuǎn)
return leftRotate(retNode);
}
//如果刪除節(jié)點后，沒有打破平衡范抓，直接返回當前根節(jié)點
return retNode;
}
3.4 完整代碼
import java.util.ArrayList;
import java.util.List;
/**
* @Author: huangyibo
* @Date: 2022/2/26 20:24
* @Description: AVL Tree
*/
public class AVLTree<K extends Comparable<K>, V> {
//AVLTree 樹節(jié)點類
private class Node<K extends Comparable<K>, V>{
public K key;
public V value;
public Node<K, V> left;
public Node<K, V> right;
//當前節(jié)點所處的高度值
public int height;
public Node(K key, V value){
this.key = key;
this.value = value;
this.left = null;
this.right = null;
//初始化新的節(jié)點都是葉子節(jié)點骄恶，高度都為1
this.height = 1;
}
@Override
public String toString() {
return key.toString() +" : " + value.toString();
}
}
// 根節(jié)點
private Node<K, V> root;
// 樹容量
private Integer size;
public AVLTree(){
root = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int getSize() {
return size;
}
/**
* 判斷該二叉樹是否是一棵二分搜索樹
* @return
*/
private boolean isBST(){
List<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<K,V> node, List<K> keys) {
if(node == null){
return;
}
inOrder(node.left, keys);
keys.add(node.key);
inOrder(node.right, keys);
}
/**
* 判斷該二叉樹是否是一棵平衡二叉樹
* @return
*/
private boolean isBalanced(){
return isBalanced(root);
}
/**
* 判斷該二叉樹是否是一棵平衡二叉樹, 遞歸調(diào)用函數(shù)
* @param node
* @return
*/
private boolean isBalanced(Node<K,V> node){
//node == null 代表該樹是一顆平衡二叉樹，
//平衡二叉樹左右子樹高度相差不超過1
// 因為空樹的左右子樹高度相差不超過1
if(node == null){
return true;
}
//獲取平衡因子
int balanceFactor = getBalanceFactor(node);
//左右子樹高度相差超過1匕垫，則不是平衡二叉樹
if(Math.abs(balanceFactor) > 1){
return false;
}
//遞歸調(diào)用該節(jié)點的左右子樹僧鲁，判斷是否是平衡二叉樹
return isBalanced(node.left) && isBalanced(node.right);
}
/**
* 返回node節(jié)點的高度值
* @param node
* @return
*/
private int getHeight(Node<K, V> node){
if(node == null){
return 0;
}
return node.height;
}
/**
* 獲取節(jié)點node的平衡因子
* @param node
* @return
*/
private int getBalanceFactor(Node<K, V> node){
if(node == null){
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
/**
* 右旋轉(zhuǎn)
* // 對節(jié)點y進行向右旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點x
* // y x
* // / \ / \
* // x T4 向右旋轉(zhuǎn) (y) z y
* // / \ - - - - - - - -> / \ / \
* // z T3 T1 T2 T3 T4
* // / \
* // T1 T2
* @param y
* @return
*/
private Node<K, V> rightRotate(Node<K, V> y){
Node<K, V> x = y.left;
Node<K, V> T3 = x.right;
//向右旋轉(zhuǎn)過程
x.right = y;
y.left = T3;
//更新節(jié)點的高度height值
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
/**
* 向左旋轉(zhuǎn)
* // 對節(jié)點y進行向左旋轉(zhuǎn)操作象泵，返回旋轉(zhuǎn)后新的根節(jié)點x
* // y x
* // / \ / \
* // T1 x 向左旋轉(zhuǎn) (y) y z
* // / \ - - - - - - - -> / \ / \
* // T2 z T1 T2 T3 T4
* // / \
* // T3 T4
* @param y
* @return
*/
private Node<K, V> leftRotate(Node<K, V> y){
Node<K, V> x = y.right;
Node<K, V> T2 = x.left;
//向左旋轉(zhuǎn)過程
x.left = y;
y.right = T2;
//更新節(jié)點的高度height值
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
/**
* 向AVL樹添加新的元素(key,value)
* @param key
* @param value
*/
public void add(K key, V value){
//向根節(jié)點添加元素e
root = add(root, key, value);
}
/**
* 向以node為根的AVL樹中插入元素(key,value)寞秃，遞歸算法
* @param node
* @param key
* @param value
* @return 返回插入新元素的AVL樹的根
*/
private Node<K, V> add(Node<K, V> node, K key, V value){
if(node == null){
size ++;
return new Node<>(key, value);
}
//遞歸調(diào)用，元素添加到node.left
if(key.compareTo(node.key) < 0){
node.left = add(node.left, key, value);
}else if(key.compareTo(node.key) > 0){
//遞歸調(diào)用偶惠，元素添加到node.right
node.right = add(node.right, key, value);
}else {
node.value = value;
}
//更新節(jié)點的高度height
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
//計算平衡因子
int balanceFactor = getBalanceFactor(node);
//平衡維護
//LL
// 左子樹比右子樹高度超過了1春寿，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在左子樹的左子樹的左側(cè)
if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0){
//右旋轉(zhuǎn)
return rightRotate(node);
}
//RR
// 右子樹比左子樹高度超過了1，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在右子樹的右子樹的右側(cè)
if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0){
//左旋轉(zhuǎn)
return leftRotate(node);
}
//LR
// 左子樹比右子樹高度超過了1忽孽，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在左子樹的左子樹的右側(cè)
if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
//先對node.left進行左旋轉(zhuǎn)
node.left = leftRotate(node.left);
//然后對node進行右旋轉(zhuǎn)
return rightRotate(node);
}
//RL
// 右子樹比左子樹高度超過了1绑改，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在右子樹的右子樹的左側(cè)
if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){
//先對node.right進行右旋轉(zhuǎn)
node.right = rightRotate(node.right);
//然后對node進行左旋轉(zhuǎn)
return leftRotate(node);
}
//返回當前根節(jié)點
return node;
}
/**
* 根據(jù)key從當前以當前node為根節(jié)點中尋找value, 不存在返回null
* @param node
* @param key
* @return
*/
private Node<K, V> getNode(Node<K, V> node, K key){
//遞歸終止條件
if(node == null){
return null;
}
//待尋找key比當前節(jié)點key小，遞歸調(diào)用node.left
if(key.compareTo(node.key) < 0){
return getNode(node.left, key);
}else if(key.compareTo(node.key) > 0){
//待尋找key比當前節(jié)點key大兄一，遞歸調(diào)用node.right
return getNode(node.right, key);
}else {
//待尋找key和當前節(jié)點key相等厘线，直接返回
return node;
}
}
public boolean contains(K key) {
return getNode(root, key) != null;
}
public void set(K key, V value) {
Node<K, V> node = getNode(root, key);
if(node == null){
//不存在直接拋異常
throw new IllegalArgumentException(key + " doesn't exist!");
}
//key已存在，則更新
node.value = value;
}
public V get(K key) {
Node<K, V> node = getNode(root, key);
return node == null ? null : node.value;
}
/**
* 返回以node為根的二分搜索樹的最小值所在的節(jié)點
* @param node
* @return
*/
private Node<K, V> minimum(Node<K, V> node){
if(node.left == null){
return node;
}
return minimum(node.left);
}
/**
* 從二分搜索樹中刪除元素鍵為key的節(jié)點, 并返回value, 不存在返回null
* @param key
* @return
*/
public V remove(K key){
Node<K, V> node = getNode(root, key);
if(node == null){
//不存在直接返回null
return null;
}
//存在
root = remove(root, key);
return node.value;
}
/**
* 刪除以node為根的二分搜索樹中鍵為key的節(jié)點出革，遞歸遞歸方式
* 返回刪除節(jié)點后新的二分搜索樹的根
* @param node
* @param key
* @return
*/
private Node<K, V> remove(Node<K, V> node, K key){
//節(jié)點為空造壮，直接返回
if(node == null){
return null;
}
//聲明要返回去的node
Node<K, V> retNode;
if(key.compareTo(node.key) < 0){
//待刪除元素key小于當前節(jié)點的鍵，向左遞歸尋找
node.left = remove(node.left, key);
retNode = node;
}else if(key.compareTo(node.key) > 0){
//待刪除元素key大于當前節(jié)點的鍵骂束，向右遞歸尋找
node.right = remove(node.right, key);
retNode = node;
}else {
//待刪除節(jié)點左子樹為空
if(node.left == null){
Node<K, V> rightNode = node.right;
node.right = null;
size --;
retNode = rightNode;
}
//待刪除節(jié)點右子樹為空
else if(node.right == null){
Node<K, V> rightNode = node.left;
node.left = null;
size --;
retNode = rightNode;
}else {
//待刪除節(jié)點左耳璧、右子樹不為空
//找到比待刪除節(jié)點大的最小節(jié)點硝全，即待刪除節(jié)點右子樹最小節(jié)點
//用這個節(jié)點頂替待刪除節(jié)點的位置
//找到比待刪除節(jié)點大的最小節(jié)點，即待刪除節(jié)點右子樹最小節(jié)點
Node<K, V> successor = minimum(node.right);
//刪除比待刪除節(jié)點大的最小節(jié)點楞抡，并將返回值給succeer的右孩子
//successor.right = removeMin(node.right);
successor.right = remove(node.right, successor.key);
//node.left賦值給successor.left
successor.left = node.left;
//node節(jié)點和二分搜索樹脫離關(guān)系
node.left = node.right = null;
retNode = successor;
}
}
if(retNode == null){
//如果刪除了該節(jié)點伟众，返回的二叉樹節(jié)點的根節(jié)點為空的話
return null;
}
//更新節(jié)點的高度height
retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;
//計算平衡因子
int balanceFactor = getBalanceFactor(retNode);
//平衡維護
//LL
// 左子樹比右子樹高度超過了1，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在左子樹的左子樹的左側(cè)
if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0){
//右旋轉(zhuǎn)
return rightRotate(retNode);
}
//RR
// 右子樹比左子樹高度超過了1召廷，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在右子樹的右子樹的右側(cè)
if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0){
//左旋轉(zhuǎn)
return leftRotate(retNode);
}
//LR
// 左子樹比右子樹高度超過了1凳厢，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在左子樹的左子樹的右側(cè)
if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
//先對node.left進行左旋轉(zhuǎn)
retNode.left = leftRotate(retNode.left);
//然后對node進行右旋轉(zhuǎn)
return rightRotate(retNode);
}
//RL
// 右子樹比左子樹高度超過了1，說明當前節(jié)點的平衡被打破
// 且新添加的節(jié)點是在右子樹的右子樹的左側(cè)
if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){
//先對node.right進行右旋轉(zhuǎn)
retNode.right = rightRotate(retNode.right);
//然后對node進行左旋轉(zhuǎn)
return leftRotate(retNode);
}
//如果刪除節(jié)點后竞慢，沒有打破平衡先紫，直接返回當前根節(jié)點
return retNode;
}
}
四、AVL樹實現(xiàn)映射(Map)
- Map接口
public interface Map<K, V> {
/**
* 添加元素
* @param key
* @param value
*/
void add(K key, V value);
/**
* 刪除元素筹煮，返回元素對應的value
* @param key
* @return
*/
V remove(K key);
/**
* 是否包含key
* @param key
* @return
*/
boolean contains(K key);
/**
* 修改元素key對應的value
* @param key
* @param value
*/
void set(K key, V value);
/**
* 獲取key對應的value
* @param key
* @return
*/
V get(K key);
/**
* 映射的元素個數(shù)
* @return
*/
int getSize();
/**
* 映射是否為空
* @return
*/
boolean isEmpty();
}
- AVLTreeMap實現(xiàn)
/**
* @Author: huangyibo
* @Date: 2022/2/27 0:47
* @Description: AVLTreeMap 底層基于AVLTree
*/
public class AVLTreeMap<K extends Comparable<K>, V> implements Map<K, V> {
private AVLTree<K,V> avlTree;
public AVLTreeMap(){
avlTree = new AVLTree<>();
}
@Override
public void add(K key, V value) {
avlTree.add(key,value);
}
@Override
public V remove(K key) {
return avlTree.remove(key);
}
@Override
public boolean contains(K key) {
return avlTree.contains(key);
}
@Override
public void set(K key, V value) {
avlTree.set(key, value);
}
@Override
public V get(K key) {
return avlTree.get(key);
}
@Override
public int getSize() {
return avlTree.getSize();
}
@Override
public boolean isEmpty() {
return avlTree.isEmpty();
}
}
五遮精、AVL樹實現(xiàn)集合(Set)
- 集合(Set)接口
public interface Set<E> {
/**
* 添加元素
* @param e
*/
void add(E e);
/**
* 刪除元素
* @param e
*/
void remove(E e);
/**
* 集合是否包含元素
* @param e
* @return
*/
boolean contains(E e);
/**
* 集合的元素個數(shù)
* @return
*/
int getSize();
/**
* 集合是否為空
* @return
*/
boolean isEmpty();
}
- AVLTreeSet實現(xiàn)
/**
* @Author: huangyibo
* @Date: 2022/2/27 0:52
* @Description: AVLTreeSet 底層基于AVLTree
*/
public class AVLTreeSet<E extends Comparable<E>> implements Set<E> {
private AVLTree<E, Object> avlTree;
public AVLTreeSet(){
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();
}
}
