平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有別于AVL算法）鸠窗，且具有以下性質(zhì)：
它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹榔幸。
這個方案很好的解決了二叉查找樹退化成鏈表的問題，把插入冻河，查找钝计，刪除的時間復(fù)雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉(zhuǎn)會使插入和刪除犧牲掉O(logN)左右的時間瘫絮，不過相對二叉查找樹來說涨冀，查找時間上穩(wěn)定了很多。
二叉樹不平衡的情景麦萤，及其解決方案
這里為了避免一直看概念比較”干“鹿鳖，會結(jié)合代碼進行說明
節(jié)點的定義
public class AvlTree<T extends Comparable<T>> {
/**
* 樹的根節(jié)點
*/
private AvlNode root;
/**
* 樹的高度
*/
private int height;
private class AvlNode {
/**
* 節(jié)點值
*/
private T data;
/**
* 當(dāng)前節(jié)點所在樹的高度
*/
int height;
/**
* 左右子樹
*/
private AvlNode left, right;
AvlNode(T data) {
left = right = null;
this.data = data;
this.height = 0;
}
}
}
1. 左左
左旋
節(jié)點6的左子樹高度為3扁眯，右子樹高度為1，而且6節(jié)點的任意子樹的左子樹的高度都大于等于右子樹的高度栓辜，這種形態(tài)的二叉樹直接進行左旋即可恋拍。
編碼實現(xiàn)
/**
* 左旋
* 4 2
* / \ / \
* 2 5 ---> 1 4
* / \ / / \
* 1 3 0 3 5
* /
* 0
*
* @param avlNode 當(dāng)前根節(jié)點
* @return 左旋后的當(dāng)前根節(jié)點
*/
private AvlNode ll(AvlNode avlNode) {
if (avlNode==null) {
return null;
}
// 獲取當(dāng)前傳入二叉樹根節(jié)點的左兒子
AvlNode leftNode = avlNode.left;
// 左旋
avlNode.left = leftNode.right;
leftNode.right = avlNode;
// 重新計算高度
leftNode.height = Integer.max(this.height(leftNode.left), this.height(leftNode.right))+1;
avlNode.height = Integer.max(this.height(avlNode), this.height(avlNode))+1;
// 此時當(dāng)前二叉樹的根節(jié)點為剛剛的左兒子
return leftNode;
}
2. 右右
右旋
節(jié)點2的右子樹的高度為3，左子樹的高度為1藕甩，而且2節(jié)點的任意右子樹的高度都大于等于左子樹施敢，這種形態(tài)的二叉樹直接進行右旋即可。
編碼實現(xiàn)
/**
* 右旋
* 2 4
* / \ / \
* 1 4 2 5
* / \ ---> / \ \
* 3 5 1 3 6
* \
* 6
*
* @param avlNode 當(dāng)前根節(jié)點
* @return 右旋后的當(dāng)前根節(jié)點
*/
private AvlNode rr(AvlNode avlNode) {
if (avlNode==null) {
return null;
}
// 獲取當(dāng)前傳入二叉樹根節(jié)點的右兒子
AvlNode rightNode = avlNode.right;
// 右旋
avlNode.right = rightNode.left;
rightNode.left = avlNode;
// 重新計算高度
rightNode.height = Integer.max(this.height(rightNode.left), this.height(rightNode.right))+1;
avlNode.height = Integer.max(this.height(avlNode.left), this.height(avlNode.right))+1;
// 此時當(dāng)前二叉樹的根節(jié)點為剛剛的右兒子
return rightNode;
}
2. 左右
左右
節(jié)點6的左子樹的高度為2狭莱，右子樹的高度為1僵娃，但是不具備任意左子樹的高度都大于等于右子樹，即腋妙，節(jié)點2的左子樹的高度為1默怨，但是右子樹的高度為2，這種情況首先需要將節(jié)點2進行右旋骤素，轉(zhuǎn)換成”左左“形式匙睹，然后在對節(jié)點6進行左旋，最終達到平衡济竹。
編碼實現(xiàn)
/**
* 左右模式痕檬，先右旋，然后左旋
* 6 6 4
* / \ / \ / \
* 2 7 4 7 2 6
* / \ ---> / \ ---> / \ / \
* 1 4 2 5 1 3 5 7
* / \ / \
* 3 5 1 3
* @param avlNode 當(dāng)前根節(jié)點
* @return 旋轉(zhuǎn)后的當(dāng)前根節(jié)點
*/
private AvlNode lr(AvlNode avlNode){
if(avlNode==null){
return null;
}
avlNode.left = rr(avlNode.left);
return rr(avlNode);
}
3. 右左
右左
節(jié)點2的左子樹的高度為1送浊，右子樹的高度為3梦谜，但是不具備任意右子樹的高度都大于等于左子樹的高度情況，即袭景，節(jié)點6的左子樹高度為2唁桩，右子樹的高度為1，這種情況首先要將節(jié)點6進行左旋耸棒，轉(zhuǎn)換成”右右“形式荒澡，然后對節(jié)點2進行右旋，最終達到平衡与殃。
編碼實現(xiàn)
/**
* 右左模式仰猖，先左旋，然后右旋
* 2 2 4
* / \ / \ / \
* 1 6 1 4 2 6
* / \ ---> / \ ---> / \ / \
* 4 7 3 6 1 3 5 7
* / \ / \
* 3 5 5 7
*
* @param avlNode 當(dāng)前根節(jié)點
* @return 旋轉(zhuǎn)后的根節(jié)點
*/
private AvlNode rl(AvlNode avlNode){
if(avlNode==null){
return null;
}
avlNode.right = ll(avlNode.right);
return rr(avlNode);
}
整體創(chuàng)建二叉樹的過程就是這樣的
- 插入新的節(jié)點
- 調(diào)整數(shù)的平衡
- 重新計算節(jié)點高度
/**
* 插入節(jié)點
*
* @param data 節(jié)點值
*/
public void insert(T data) {
root = insertCore(data, root);
height = root.height;
}
/**
* 插入節(jié)點核心邏輯
*
* @param data 數(shù)據(jù)
* @param root 當(dāng)前節(jié)點根節(jié)點
* @return 根節(jié)點
*/
private AvlNode insertCore(T data, AvlNode root) {
if (root == null) {
return new AvlNode(data);
}
if (root.data.compareTo(data) > 0) {
root.left = insertCore(data, root.left);
// 是否需要平衡
if ((height(root.left) - height(root.right) > 1)) {
if (height(root.left.left)>height(root.left.right)) {
// LL情況
root = ll(root);
} else {
// LR情況
root = lr(root);
}
}
} else if (root.data.compareTo(data) < 0) {
root.right = insertCore(data, root.right);
// 是否需要平衡
if ((height(root.right) - height(root.left) > 1)) {
if (height(root.right.right)>height(root.right.left)) {
// RR情況
root = rr(root);
} else {
// RL情況
root = rl(root);
}
}
}
// 重新計算節(jié)點高度
if(root != null){
root.height = Integer.max(height(root.left), height(root.right)) + 1;
}
// 節(jié)點和當(dāng)前root節(jié)點相等奈籽，直接返回
return root;
}
刪除節(jié)點
刪除節(jié)點的方式有很多種饥侵，這里只是其中的一種
同插入操作一樣，刪除結(jié)點時也有可能破壞平衡性衣屏，這就要求我們刪除的時候要進行平衡性調(diào)整躏升。
刪除分為以下幾種情況：
- 首先在整個二叉樹中搜索要刪除的結(jié)點，如果沒搜索到直接返回不作處理狼忱，否則執(zhí)行以下操作：
- 要刪除的節(jié)點是當(dāng)前根節(jié)點T膨疏。
- 如果左右子樹都非空一睁。在高度較大的子樹中實施刪除操作。
分兩種情況：- 左子樹高度大于右子樹高度佃却，將左子樹中最大的那個元素賦給當(dāng)前根節(jié)點者吁，然后刪除左子樹中元素值最大的那個節(jié)點。
- 左子樹高度小于右子樹高度饲帅，將右子樹中最小的那個元素賦給當(dāng)前根節(jié)點复凳，然后刪除右子樹中元素值最小的那個節(jié)點。
- 如果左右子樹中有一個為空灶泵，那么直接用那個非空子樹或者是NULL替換當(dāng)前根節(jié)點即可育八。
- 如果左右子樹都非空一睁。在高度較大的子樹中實施刪除操作。
- 要刪除的節(jié)點元素值小于當(dāng)前根節(jié)點T值，在左子樹中進行刪除赦邻。遞歸調(diào)用髓棋，在左子樹中實施刪除。否則在右子樹中遞歸調(diào)用實施刪除惶洲。
- 刪除節(jié)點后按声，需要判斷當(dāng)前根節(jié)點是否仍然滿足平衡條件，如果滿足平衡條件恬吕，只需要更新當(dāng)前根節(jié)點T的高度信息签则。否則，需要進行旋轉(zhuǎn)調(diào)整币呵。
編碼實現(xiàn)
/**
* 找到樹中最小的值
*
* @param root 樹的根節(jié)點
* @return min avlNode
*/
private AvlNode findMin(AvlNode root) {
return (root == null || root.left == null) ? root : findMin(root.left);
}
/**
* 找到樹中最大的值
*
* @param root 樹的根節(jié)點
* @return max avlNode
*/
private AvlNode finMax(AvlNode root) {
return (root == null || root.right == null) ? root : finMax(root.right);
}
/**
* 刪除節(jié)點
*
* @param data 節(jié)點值
*/
public void delete(T data) {
root = deleteCore(data, root);
height = root!=null?root.height:0;
}
/**
* 刪除節(jié)點核心邏輯
*
* @param data 數(shù)據(jù)
* @param root 當(dāng)前節(jié)點根節(jié)點
* @return 根節(jié)點
*/
private AvlNode deleteCore(T data, AvlNode root) {
if (root == null) {
return null;
}
if (root.data.compareTo(data) > 0) {
// 根節(jié)點比刪除的節(jié)點大，刪除的節(jié)點在左子樹
root.left = deleteCore(data, root.left);
// 平衡樹
if (height(root.right) - height(root.left) > 1) {
// 判斷平衡模式
if (height(root.right.left) > height(root.right.right)) {
// RL模式
root = rl(root);
} else {
// RR模式
root = rr(root);
}
}
} else if (root.data.compareTo(data) < 0) {
// 根節(jié)點比刪除的節(jié)點小侨颈，刪除的單節(jié)點在右子樹
root.right = deleteCore(data, root.right);
// 平衡樹
if (height(root.left) - height(root.right) > 1) {
// 判斷平衡模式
if (height(root.left.right) > height(root.left.left)) {
// LR模式
root = lr(root);
} else {
// LL模式
root = ll(root);
}
}
} else {
// 當(dāng)前的根節(jié)點即為需要刪除的節(jié)點
if (root.left != null && root.right != null) {
// 左右子樹都非空余赢，判斷左右子樹的高度，選擇高度較高的一個
if (root.left.height > root.right.height) {
// 左子樹較高哈垢，那么從左子樹中找到值最大的節(jié)點妻柒，跟要刪除的節(jié)點的值(當(dāng)前的根節(jié)點)進行替換，然后刪除該節(jié)點
AvlNode maxNode = finMax(root.left);
root.data = maxNode.data;
// 刪除左子樹中值最大的節(jié)點
root.left = deleteCore(maxNode.data, root.left);
} else {
// 右子樹較高耘分，那么從右子樹中找到值最小的節(jié)點举塔，跟要刪除的節(jié)點的值(當(dāng)前的根節(jié)點)進行替換，然后刪除該節(jié)點
AvlNode minNode = findMin(root.right);
root.data = minNode.data;
// 刪除右子樹中值最小的節(jié)點
root.right = deleteCore(minNode.data, root.right);
}
} else {
// 選擇任意一個非空節(jié)點作為根節(jié)點返回
root = root.left != null ? root.left : root.right;
}
}
// 重新計算節(jié)點的高度
if(root!=null){
root.height = Integer.max(height(root.left), height(root.right)) + 1;
}
return root;
}
查找
查找跟普通的二叉樹查找相同求泰，就不墨跡概念了央渣，直接上代碼
/**
* 判斷節(jié)點是否在二叉樹中
*
* @param data data
* @return bool
*/
public boolean contains(T data){
AvlNode p = root;
while (p!=null&&p.data!=data){
if(p.data.compareTo(data)>0){
p=p.left;
}else {
p=p.right;
}
}
return p!=null&&p.data.compareTo(data)==0;
}
