介紹
AVL樹是最常見(jiàn)的自平衡二叉搜索樹了系吩。關(guān)于二叉搜索樹大致的描述如下：
- 每個(gè)節(jié)點(diǎn)只有左右兩個(gè)子節(jié)點(diǎn)
- 每個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)的值小于該節(jié)點(diǎn)值求晶，每個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)的值大于該節(jié)點(diǎn)的值
AVL樹是一顆平衡二叉樹，所謂平衡的概念如下：
二叉搜索樹中任何一個(gè)節(jié)點(diǎn)舵变，左子樹的高度與右子樹的高度差小于等于1。子樹的高度定義為子樹的左右子樹中高度大的值瘦穆。
當(dāng)一個(gè)二叉搜索樹為平衡二叉樹的時(shí)候纪隙，查詢效率是很高的，時(shí)間復(fù)雜度為O(lgn)扛或。但如果對(duì)這個(gè)樹做了多次的插入與刪除操作后绵咱，這個(gè)樹就很可能失去了平衡，變成了一個(gè)鏈表結(jié)構(gòu)熙兔。
AVL樹插入與刪除節(jié)點(diǎn)后都需要重新計(jì)算當(dāng)前節(jié)點(diǎn)是否平衡悲伶，如果不平衡艾恼，則通過(guò)旋轉(zhuǎn)來(lái)使節(jié)點(diǎn)保持平衡。
旋轉(zhuǎn)
旋轉(zhuǎn)有四種情況麸锉，左旋轉(zhuǎn)兩種钠绍，右旋轉(zhuǎn)兩種，其中左旋轉(zhuǎn)與右旋轉(zhuǎn)是鏡對(duì)稱動(dòng)作花沉，我們只看左旋轉(zhuǎn)就好柳爽。參考如下兩張圖，應(yīng)該可以很清晰的說(shuō)明兩種左旋轉(zhuǎn)的過(guò)程碱屁。注意：旋轉(zhuǎn)前后磷脯，顏色相同的節(jié)點(diǎn)代表了值相同的節(jié)點(diǎn)。 右旋的操作娩脾，可以自己去畫一下赵誓。
左旋一
左旋一
左旋二
左旋二
關(guān)于刪除
突然發(fā)現(xiàn)，二叉查找樹中節(jié)點(diǎn)的刪除其實(shí)也不是一個(gè)特別簡(jiǎn)單的過(guò)程柿赊。所以單開一個(gè)小節(jié)來(lái)描述一下俩功。
通用方法
當(dāng)需要?jiǎng)h除一個(gè)節(jié)點(diǎn)的時(shí)候我們需要的操作如下：
- 持有該節(jié)點(diǎn)的父節(jié)點(diǎn)與子節(jié)點(diǎn)
- 斷開父節(jié)點(diǎn)到該節(jié)點(diǎn)的連接，以及該節(jié)點(diǎn)到子節(jié)點(diǎn)的連接
- 如果該節(jié)點(diǎn)沒(méi)有右子節(jié)點(diǎn)闹瞧，則將該節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)置為父節(jié)點(diǎn)的左子節(jié)點(diǎn)绑雄，結(jié)束
- 如果該節(jié)點(diǎn)有右子節(jié)點(diǎn)，則需要從右子節(jié)點(diǎn)中找到最小值的節(jié)點(diǎn)奥邮，然后做如下操作
4.1 如果最小值節(jié)點(diǎn)就是當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)万牺，則將最小值節(jié)點(diǎn)設(shè)置為父節(jié)點(diǎn)的左子節(jié)點(diǎn)，然后把原左子節(jié)點(diǎn)設(shè)置為最小值節(jié)點(diǎn)的左子節(jié)點(diǎn)洽腺，結(jié)束
4.2 如果最小值節(jié)點(diǎn)不是當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)脚粟，則需要在右子節(jié)點(diǎn)的子樹中刪除最小值節(jié)點(diǎn)，然后創(chuàng)建新的最小時(shí)節(jié)點(diǎn)蘸朋，將新的最小時(shí)節(jié)點(diǎn)設(shè)置為父節(jié)點(diǎn)的左子節(jié)點(diǎn)核无，然后把原左子節(jié)點(diǎn)設(shè)置為新的最小值節(jié)點(diǎn)的左子節(jié)點(diǎn)，右子節(jié)點(diǎn)為新的最小值節(jié)點(diǎn)的右子節(jié)點(diǎn)藕坯，結(jié)束团南。
看圖
紅色的節(jié)點(diǎn)表示刪除后需要重新計(jì)算高度并判斷是否需要旋轉(zhuǎn)的節(jié)點(diǎn)
步驟3的刪除操作
步驟3的場(chǎng)景
步驟4.1的刪除操作
步驟4.1的場(chǎng)景
步驟4.2的刪除操作
步驟4.2的場(chǎng)景
這個(gè)圖里，oldRight到minNode的虛線表示的意思是minNode不一定是oldRight的直接左子節(jié)點(diǎn)炼彪，有可能是很多層之后的一個(gè)子節(jié)點(diǎn)吐根。但肯定在oldRight為根的樹中，它是最左邊的辐马。
Talk is cheap
/**
* AVL樹節(jié)點(diǎn)類
* 節(jié)點(diǎn)中持有的對(duì)象的類必須實(shí)現(xiàn)Comparable接口
* 此類中封裝了計(jì)算子樹高度拷橘，計(jì)算自身節(jié)點(diǎn)高度，判斷是否需要旋轉(zhuǎn)，以及旋轉(zhuǎn)實(shí)現(xiàn)的方法 作為樹節(jié)點(diǎn)的基礎(chǔ)功能
*
* @author goofy.wang
*/
public class AVLNode<T extends Comparable> implements Comparable<AVLNode<T>>{
private T value;
private int leftDepth;
private int rightDepth;
private AVLNode<T> left;
private AVLNode<T> right;
public AVLNode(T value) {
this(value, null, null);
}
public AVLNode(T value, AVLNode<T> left, AVLNode<T> right) {
this.value = value;
this.left = left;
this.right = right;
}
public AVLNode<T> getLeft() {
return this.left;
}
public void setLeft(AVLNode<T> left) {
this.left = left;
}
public AVLNode<T> getRight() {
return this.right;
}
public void setRight(AVLNode<T> right) {
this.right = right;
}
public void setValue(T value){
this.value = value;
}
public T getValue(){
return this.value;
}
public boolean hasLeft(){
return this.left != null;
}
public boolean hasRight(){
return this.right != null;
}
/**
* 獲取當(dāng)前節(jié)點(diǎn)深度的方法
* @return
*/
public int getDepth(){
int maxSubDepth = this.leftDepth > this.rightDepth ? this.leftDepth : this.rightDepth;
return maxSubDepth + 1;
}
/**
* 計(jì)算左右子樹深度的方法
*/
public void calculateDepth(){
this.leftDepth = this.left == null ? 0 : this.left.getDepth();
this.rightDepth = this.right == null ? 0 : this.right.getDepth();
}
/**
* 判斷是否需要旋轉(zhuǎn)
* @return
*/
public boolean needRotate(){
return Math.abs(this.leftDepth - this.rightDepth) > 1;
}
/**
* 旋轉(zhuǎn)方法冗疮，內(nèi)部判斷需要左旋還是右旋
*/
public void rotate(){
if(this.leftDepth > this.rightDepth){
this.leftRotateToRight();
}else{
this.rightRotateToLeft();
}
this.calculateDepth();
}
/**
* 左旋方法
* if 實(shí)現(xiàn)旋轉(zhuǎn)一
* else 實(shí)現(xiàn)旋轉(zhuǎn)二
*/
private void leftRotateToRight(){
AVLNode<T> leftRight = this.left.getRight();
T currentValue = this.getValue();
if(leftRight == null){
T leftValue = this.left.getValue();
AVLNode<T> newRight = new AVLNode<T>(currentValue, null, this.getRight());
newRight.calculateDepth();
this.setValue(leftValue);
this.setRight(newRight);
this.setLeft(this.getLeft().getLeft());
}else{
T leftRightValue = leftRight.getValue();
AVLNode<T> leftRightLeft = leftRight.getLeft();
AVLNode<T> leftRightRight = leftRight.getRight();
AVLNode<T> newRight = new AVLNode<T>(currentValue, leftRightRight, this.getRight());
newRight.calculateDepth();
this.setValue(leftRightValue);
this.setRight(newRight);
this.left.setRight(leftRightLeft);
this.left.calculateDepth();
}
}
/**
* 右旋方法萄唇，與左旋鏡對(duì)稱
*/
private void rightRotateToLeft(){
AVLNode<T> rightLeft = this.right.getLeft();
T currentValue = this.getValue();
if(rightLeft == null){
T rightValue = this.right.getValue();
AVLNode<T> newLeft = new AVLNode<T>(currentValue, this.left, null);
newLeft.calculateDepth();
this.setValue(rightValue);
this.setLeft(newLeft);
this.setRight(this.right.getRight());
}else{
T rightLeftValue = rightLeft.getValue();
AVLNode<T> rightLeftLeft = rightLeft.getLeft();
AVLNode<T> rightLeftRight = rightLeft.getRight();
AVLNode<T> newLeft = new AVLNode<T>(currentValue, this.left, rightLeftLeft);
newLeft.calculateDepth();
this.setValue(rightLeftValue);
this.setLeft(newLeft);
this.right.setLeft(rightLeftRight);
this.right.calculateDepth();
}
}
/**
* 比較方法
* @param o
* @return
*/
@Override
public int compareTo(AVLNode<T> o) {
return this.value.compareTo(o.getValue());
}
}
/**
* AVL樹類
* 此類用于組織AVLNode節(jié)點(diǎn)，使得這些節(jié)點(diǎn)以正確的平衡二叉樹方式關(guān)聯(lián)在一起
* 并在添加與刪除元素后术幔，控制樹節(jié)點(diǎn)完成高度計(jì)算另萤，平衡性判斷，以及旋轉(zhuǎn)等行為
*
* @author goofy.wang
*/
public class AVLTree<T extends Comparable> {
private AVLNode<T> root;
/**
* 添加節(jié)點(diǎn)的方法诅挑，如果值在樹中存在相等的節(jié)點(diǎn)仲墨，則將此節(jié)點(diǎn)中的值替換為當(dāng)前值
* @param nodeValue
*/
public void append(T nodeValue){
AVLNode<T> newNode = new AVLNode<T>(nodeValue);
if(this.root == null){
this.root = newNode;
}else{
this.innerAppend(this.root, newNode);
}
}
/**
* 判斷樹中是否存在某個(gè)值對(duì)象的方法
* @param nodeValue
* @return
*/
public boolean contains(T nodeValue){
if(this.root == null){
return false;
}
AVLNode<T> condition = new AVLNode<T>(nodeValue);
if(root.compareTo(condition) == 0){
return true;
}else{
return this.containsInChilren(this.root, condition);
}
}
/**
* 從樹中刪除某個(gè)值對(duì)象的方法
* @param nodeValue
* @return 如果存在該元素且刪除完成返回true，如果不存在該元素則返回false
*/
public boolean remove(T nodeValue){
if(root == null){
return false;
}
AVLNode<T> toBeRemove = new AVLNode<T>(nodeValue);
if(root.compareTo(toBeRemove) == 0){
if(root.hasRight()){
AVLNode<T> minumumNodeFromRight = this.getMinumumNode(this.root.getRight());
if(this.root.getRight().compareTo(minumumNodeFromRight) == 0){
AVLNode<T> left = this.root.getLeft();
this.root.getRight().setLeft(left);
this.root = this.root.getRight();
}else{
this.innerDelete(this.root.getRight(), minumumNodeFromRight);
minumumNodeFromRight.setRight(this.root.getRight());
minumumNodeFromRight.setLeft(this.root.getLeft());
this.root = minumumNodeFromRight;
}
this.calcAndRotateIfNeeded(this.root);
}else{
this.root = this.root.getLeft();
}
}else{
this.innerDelete(this.root, toBeRemove);
}
return false;
}
private void innerAppend(AVLNode<T> currentNode, AVLNode<T> newNode){
int compareResult = currentNode.compareTo(newNode);
if(compareResult > 0){
if(currentNode.hasLeft()){
this.innerAppend(currentNode.getLeft(), newNode);
}else{
currentNode.setLeft(newNode);
}
}else if(compareResult < 0){
if(currentNode.hasRight()){
this.innerAppend(currentNode.getRight(), newNode);
}else{
currentNode.setRight(newNode);
}
}else{
currentNode.setValue(newNode.getValue());
}
/**
*
* 此方法是標(biāo)準(zhǔn)的二叉樹插入操作揍障，唯一要注意的是下面這行代碼
* 因?yàn)槲覀兪沁f歸調(diào)用innerAppend方法，直到把要插入的節(jié)點(diǎn)放到正確的位置上
* 所以在節(jié)點(diǎn)被放置完畢后,此節(jié)點(diǎn)的所有父節(jié)點(diǎn)都需要重新計(jì)算一次高度俩由，并在必要時(shí)進(jìn)行旋轉(zhuǎn)
*
* 只有一個(gè)例外毒嫡，就是當(dāng)節(jié)點(diǎn)是更新操作的時(shí)候，是不需要執(zhí)行下面這行代碼的
* 其實(shí)我們可以通過(guò)boolean變量來(lái)控制是否要執(zhí)行幻梯，不過(guò)我比較懶
*
*/
this.calcAndRotateIfNeeded(currentNode);
}
private boolean containsInChilren(AVLNode<T> currentNode, AVLNode<T> condition){
if(currentNode == null){
return false;
}
int compareResult = currentNode.compareTo(condition);
if(compareResult > 0){
return this.containsInChilren(currentNode.getLeft(), condition);
}else if(compareResult < 0){
return this.containsInChilren(currentNode.getRight(), condition);
}else{
return true;
}
}
/**
* 刪除方法兜畸，因?yàn)槲覀冊(cè)趫?zhí)行刪除邏輯的時(shí)候，需要處理當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)與子節(jié)點(diǎn)的關(guān)系碘梢，所以把父節(jié)點(diǎn)作為參數(shù)傳遞進(jìn)來(lái)
* 方法內(nèi)不判斷是否要?jiǎng)h除父節(jié)點(diǎn)咬摇，而是判斷是否要?jiǎng)h除父節(jié)點(diǎn)的子節(jié)點(diǎn)
* @param parentNode
* @param condition
* @return
*/
private boolean innerDelete(AVLNode<T> parentNode, AVLNode<T> condition){
int compareResult = parentNode.compareTo(condition);
boolean deleted = false;
if(compareResult > 0 && parentNode.hasLeft()){
/**
* 如果父節(jié)點(diǎn)比當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)大，并且當(dāng)前父節(jié)點(diǎn)存在左節(jié)點(diǎn)
* 則判斷當(dāng)前父節(jié)點(diǎn)的左節(jié)點(diǎn)是否是要?jiǎng)h除的節(jié)點(diǎn)煞躬，如果是就刪除當(dāng)前父節(jié)點(diǎn)的左節(jié)點(diǎn)
* 如果不是則遞歸
*/
AVLNode<T> leftSub = parentNode.getLeft();
if(leftSub.compareTo(condition) == 0){
this.realDeleteLeft(parentNode);
deleted = true;
}else{
deleted = this.innerDelete(leftSub, condition);
}
}else if(parentNode.hasRight()){
AVLNode<T> rightSub = parentNode.getRight();
if(rightSub.compareTo(condition) == 0){
this.realDeleteRight(parentNode);
deleted = true;
}else{
deleted = this.innerDelete(rightSub, condition);
}
}
/**
* 如果確實(shí)刪除了當(dāng)前節(jié)點(diǎn)的某個(gè)層級(jí)子節(jié)點(diǎn)肛鹏，則當(dāng)前節(jié)點(diǎn)需要重新計(jì)算高度，并有可能完成旋轉(zhuǎn)
*/
if(deleted){
this.calcAndRotateIfNeeded(parentNode);
}
return deleted;
}
private void realDeleteLeft(AVLNode<T> parentNode){
AVLNode<T> toBeDelete = parentNode.getLeft();
AVLNode<T> oldLeft = toBeDelete.getLeft();
AVLNode<T> oldRight = toBeDelete.getRight();
if(oldRight == null) {
/**
* 當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)不存在右子樹
* 刪除邏輯3的場(chǎng)景
*/
parentNode.setLeft(oldLeft);
}else{
AVLNode<T> minumumNodeFromRight = this.getMinumumNode(oldRight);
if(minumumNodeFromRight.compareTo(oldRight) == 0){
/**
* 要?jiǎng)h除的右子樹的根節(jié)點(diǎn)沒(méi)有左節(jié)點(diǎn)
* 刪除邏輯4.1的場(chǎng)景
*/
parentNode.setLeft(oldRight);
oldRight.setLeft(oldLeft);
}else{
/**
* 要?jiǎng)h除的節(jié)點(diǎn)的右子樹的根節(jié)點(diǎn)存在比根節(jié)點(diǎn)還小的子節(jié)點(diǎn)
* 但是這個(gè)要找的節(jié)點(diǎn)的位置還不確定恩沛，所以我偷懶用遞歸從右子樹中刪除最小節(jié)點(diǎn)
* 刪除邏輯4.2的場(chǎng)景
*/
this.innerDelete(oldRight, minumumNodeFromRight);
parentNode.setLeft(minumumNodeFromRight);
minumumNodeFromRight.setLeft(oldLeft);
minumumNodeFromRight.setLeft(oldRight);
}
this.calcAndRotateIfNeeded(parentNode.getLeft());
}
}
private void realDeleteRight(AVLNode<T> parentNode){
AVLNode<T> toBeDelete = parentNode.getRight();
AVLNode<T> oldLeft = toBeDelete.getLeft();
AVLNode<T> oldRight = toBeDelete.getRight();
if(oldRight == null){
parentNode.setRight(oldLeft);
}else{
AVLNode<T> minumumNodeFromRight = this.getMinumumNode(oldRight);
if(oldRight.compareTo(minumumNodeFromRight) == 0) {
/**
* 走入這個(gè)分支在扰，說(shuō)明要?jiǎng)h除的節(jié)點(diǎn)的右子樹的根節(jié)點(diǎn)沒(méi)有左子樹
*/
parentNode.setRight(oldRight);
oldRight.setLeft(oldLeft);
}else{
this.innerDelete(oldRight, minumumNodeFromRight);
parentNode.setRight(minumumNodeFromRight);
minumumNodeFromRight.setRight(oldRight);
minumumNodeFromRight.setLeft(oldLeft);
}
this.calcAndRotateIfNeeded(parentNode.getRight());
}
}
/**
* 給定一個(gè)節(jié)點(diǎn)，從這個(gè)節(jié)點(diǎn)和這個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)中找到值最小的節(jié)點(diǎn)
* @param currentNode
* @return
*/
private AVLNode<T> getMinumumNode(AVLNode<T> currentNode){
if(currentNode.hasLeft()){
return this.getMinumumNode(currentNode.getLeft());
}else{
return currentNode;
}
}
/**
* 重新計(jì)算節(jié)點(diǎn)高度雷客，并在需要旋轉(zhuǎn)時(shí)控制節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)的方法
* 當(dāng)某個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)高度發(fā)生變化的時(shí)候芒珠，會(huì)調(diào)用這個(gè)方法
* @param node
*/
private void calcAndRotateIfNeeded(AVLNode<T> node){
node.calculateDepth();
if(node.needRotate()){
node.rotate();
}
}
}
預(yù)告
接下來(lái)我想寫的是多路查找樹中的2-3樹
