文章目錄

前言
一.定義
二.基本操作
- 1.查找，
- 2.插入(如何調整)
- - 如何調整
  - 代碼實作插入

前言

首先我們來思考一下一個普通二叉樹儲存資料，如果想查找一個資料，由于普通二叉樹儲存資料是随機的，要找到資料的時間複雜度為O(n)。後面為了友善
，我們又學習二叉搜尋樹，它的定義是将比根節點小的數放左邊，比根節點大的數放右邊，并且每一課子樹都是二叉搜尋樹這樣使得資料在樹上存儲有一定
的規律，在一定情況下查找起來很友善。但是，二叉搜尋數當給出資料的順序不同時，二叉搜尋樹也會不同。比如如果給出的序列為{1，2，3，4，5}或
{3，2，1，4，5}兩顆二叉搜尋樹會截然不同，查找效率也會不同。

我們知道一顆樹的查找效率與樹的高度有關，最好的樹結構當然是滿二叉樹或者是完全二叉樹，我們稱這種樹是平衡的。由我們知道二叉搜尋樹在一定情況下可以達到很好的查找效率。但是，通常情況二叉搜尋樹的結點插入順序并不能事先确定，動态查找(查找時同時進行删除與插入操作)的時候總還是會改變數的結構，不能做到平衡。是以，我們就需要考慮如何保證既能完成動态查找，又能保持一個較完美樹結構的二叉搜尋樹。這樣我們就有兩個問題需要考慮：一個是标準，什麼樣的樹才是一顆樹結構好的樹，第二是平衡化處理，怎樣使其達到平衡。

一.定義

平衡二叉樹又稱AVL樹(由發明它的兩位數學家名字命名)，它仍然是一顆二叉搜尋樹，是以具備二叉搜尋樹的所有性質，隻是加上了"平衡"的限制。
平衡二叉樹要不是一顆空樹，要不是具備以下條件的非空二叉搜尋樹：
1. 左右子樹高度差的絕對值不能超過1(平衡因子，相當于一種标準)。
2. 左右子樹仍然是一顆平衡二叉樹。
有了平衡因子的定義，我們就可以找出不平衡的樹，然後再對其進行平衡化處理，處理的具體内容分如下。處理完後使樹的高度能保持在O(logn)級别，使得
查找操作的時間複雜度為O(logn).

資料結構——平衡二叉樹(AVL樹)之插入前言一.定義二.基本操作

圖1圖2圓上為平衡因子的值，明顯圖1不是平衡二叉樹，有提個點的平衡因子超過了1。圖2是平衡二叉樹。

二.基本操作

1.查找，

由于平衡二叉樹仍是一顆二叉搜尋樹，其查找操作并不會改變平衡因子，是以與二叉搜尋樹的操作相同。可見部落格：二叉搜尋樹的查找。

2.插入(如何調整)

如何調整

假設這裡有一顆平衡二叉樹：(上方代表平衡因子)

資料結構——平衡二叉樹(AVL樹)之插入前言一.定義二.基本操作

LL型

當要往D的左子樹或者右子樹插入結點時，此時破壞了原來平衡二叉樹的平衡結構，如圖：此時A結點的平衡因子超過了1，我們稱A結點為發現問題結點，六角星為産生問題結點。

資料結構——平衡二叉樹(AVL樹)之插入前言一.定義二.基本操作

此時，我們需要看發現問題結點與産生問題結點路徑上，從發現問題結點開始的連續三個結點。入上圖的A->B->D。我們發現這三個結點都在發現問題結點A左子樹的左子樹上，我們稱這種不平衡狀态為LL型(向左傾斜)不平衡。

如何調整，LL型不平衡的調整政策主要将這三個結點(A,B,D)順時針旋轉，并且仍然要是一顆二叉搜尋樹。

由于二叉搜尋樹的性質：

将B結點的右子樹成為A的左子樹。(B的左子樹比B大，比A小)
讓A成為B的右子樹(A比B大)
将根節點設為B

資料結構——平衡二叉樹(AVL樹)之插入前言一.定義二.基本操作

顯然隻有隻有從根節點到插入結點路徑上的結點才會發生平衡因子的變化，是以隻需要對這條路徑上的失衡的結點進行調整，并且隻需要把最靠近插入節點的失衡節點調整到正常，路徑上的所有結點都會平衡。是以發現問題的結點不一定是根節點

注意：看的是發現問題結點到産生問題結點路徑上，從發現問題結點開始的連續三個結點的方向，确定是什麼型。并且主要也是調整這三個結點。

代碼如下：

void SigelleftCir(Bactree **tree){//LL旋轉
	Bactree *temp = NULL;
	temp = (*tree)->left;
	(*tree)->left = temp->right;
	temp->right = (*tree);
	(*tree)->hight = (GetHight((*tree)->left) > GetHight((*tree)->right) ? GetHight((*tree)->left) : GetHight((*tree)->right)) + 1;//調整後要保持每個結點高度正确。
	temp->hight = (GetHight(temp->left) > GetHight(temp->right) ? GetHight(temp->left) : GetHight(temp->right)) + 1;
	(*tree) = temp; //要指派給(*tree),不然temp才是正确的樹

}

RR型

RR型的處理方法與LL型類似，如圖：

資料結構——平衡二叉樹(AVL樹)之插入前言一.定義二.基本操作

産生問題結點為六角星結點(插入E的左子樹或者右子樹)，發現問題結點為A結點。路徑上從發現問題結點開始的連續三個結點為(A,C,E)結點，分别在發現問題結點右子樹的右子樹上，是以為RR型(向右傾斜)不平衡。

調整方式：主要将這三個結點(A,C,E)逆時針旋轉，并且仍然要是一顆二叉搜尋樹。

将C結點的左子樹成為A的右子樹。
讓A成為C的左子樹
将根節點設為C

資料結構——平衡二叉樹(AVL樹)之插入前言一.定義二.基本操作

void SigelrightCir(Bactree **tree){//RR旋轉，與LL一樣
	Bactree *temp = NULL;
	temp = (*tree)->right;
	(*tree)->right = temp->left;
	temp->left = (*tree);
	(*tree)->hight = (GetHight((*tree)->left) > GetHight((*tree)->right) ? GetHight((*tree)->left) : GetHight((*tree)->right)) + 1;
	temp->hight = (GetHight(temp->left) > GetHight(temp->right) ? GetHight(temp->left) : GetHight(temp->right)) + 1;
	(*tree) = temp;

LR型

資料結構——平衡二叉樹(AVL樹)之插入前言一.定義二.基本操作

産生問題結點為六角星(插入E的左子樹或者右子樹)，發現問題結點為A結點。路徑上從發現問題結點開始的連續三個結點為(A,B,E)結點，分别在發現問題結點左子樹的右子樹上，是以為LR型不平衡。

調整方式：“左-右雙旋”，主要先将B結點作為根節點逆時針旋轉(左旋)，再以A結點作為根節點順時針旋轉(右旋)。(畫圖以白色六角星作為插入)

資料結構——平衡二叉樹(AVL樹)之插入前言一.定義二.基本操作

代碼實作調整LR型就很簡單了，先右旋，再左旋

void LeftrightCir(Bactree **tree){//LR旋轉
	SigelrightCir(&((*tree)->left));
	SigelleftCir(tree);
}

RL型

資料結構——平衡二叉樹(AVL樹)之插入前言一.定義二.基本操作

産生問題結點為六角星(插入D的左子樹或者右子樹)，發現問題結點為A結點。路徑上從發現問題結點開始的連續三個結點為(A,C,D)結點，分别在發現問題結點右子樹的左子樹上，是以為RL型不平衡。

調整方式："右-左雙旋"主要先将C結點作為根節點順時針旋轉(右旋)，再以A結點作為根節點逆時針旋轉(左旋)。(畫圖以白色六角星作為插入)

資料結構——平衡二叉樹(AVL樹)之插入前言一.定義二.基本操作

代碼實作調整RL型就很簡單了，先左旋，再右旋

void RightleftCir(Bactree **tree){//RL旋轉
	SigelleftCir(&((*tree)->right));
	SigelrightCir(tree);
}

代碼實作插入

#include<stdio.h>
#include<stdlib.h>
#include<Windows.h>
#pragma warning(disable:4996)

typedef int Elementtype;
typedef struct Balacetree{//二叉樹資訊
	Elementtype val;
	int hight;
	struct Balacetree *left;
	struct Balacetree *right;

}Bactree;


Bactree *TreeNodeCreate(Elementtype x){//建立樹節點
	Bactree *tree = (Bactree *)malloc(sizeof(Bactree));
	tree->val = x;
	tree->hight = 1;
	tree->left = NULL;
	tree->right = NULL;
	return tree;
}

int GetHight(Bactree *tree){//求樹高度
	if (!tree){
		return 0;
	}
	int H;
	int LH;
	int RH;
	LH = GetHight(tree->left);
	RH = GetHight(tree->right);
	H = LH > RH ? LH : RH;
	return H + 1;
}
void SigelleftCir(Bactree **tree){//LL旋轉
	Bactree *temp = NULL;
	temp = (*tree)->left;
	(*tree)->left = temp->right;
	temp->right = (*tree);
	(*tree)->hight = (GetHight((*tree)->left) > GetHight((*tree)->right) ? GetHight((*tree)->left) : GetHight((*tree)->right)) + 1;//調整後要保持每個結點高度正确。
	temp->hight = (GetHight(temp->left) > GetHight(temp->right) ? GetHight(temp->left) : GetHight(temp->right)) + 1;
	(*tree) = temp; //要指派給(*tree),不然temp才是正确的數

}
void SigelrightCir(Bactree **tree){//RR旋轉，與LL一樣
	Bactree *temp = NULL;
	temp = (*tree)->right;
	(*tree)->right = temp->left;
	temp->left = (*tree);
	(*tree)->hight = (GetHight((*tree)->left) > GetHight((*tree)->right) ? GetHight((*tree)->left) : GetHight((*tree)->right)) + 1;
	temp->hight = (GetHight(temp->left) > GetHight(temp->right) ? GetHight(temp->left) : GetHight(temp->right)) + 1;
	(*tree) = temp;

}

void LeftrightCir(Bactree **tree){//LR旋轉
	SigelrightCir(&((*tree)->left));
	SigelleftCir(tree);
}
void RightleftCir(Bactree **tree){//RL旋轉
	SigelleftCir(&((*tree)->right));
	SigelrightCir(tree);
}

Bactree *BalaceTreePush(Bactree **tree, Elementtype x){
	if (!(*tree)){     //插入結點
		*tree=TreeNodeCreate(x);
		return *tree;
	}
	if ((*tree)->val > x){  //x小的插入左邊
		(*tree)->left = BalaceTreePush(&((*tree)->left), x);//往右邊找，将結點傳回給左指針
		//為什麼放循環裡，放循環裡确認了一個方向，是左邊
		if (GetHight((*tree)->left) - GetHight((*tree)->right) >= 2){//平衡因子
			if ((*tree)->left->val > x){//确認了第二個方向 左邊
				SigelleftCir(tree);//LL
			}
			else{//右邊
				LeftrightCir(tree);//LR
			}
		}
	}
	else{
		(*tree)->right = BalaceTreePush(&((*tree)->right), x);
		if (GetHight((*tree)->left) - GetHight((*tree)->right) <= -2){//注意是-2
			if ((*tree)->right->val < x){
				SigelrightCir(tree);
			}
			else{
				RightleftCir(tree);
			}
		}
	}
	(*tree)->hight = (GetHight((*tree)->left) > GetHight((*tree)->right) ? GetHight((*tree)->left) : GetHight((*tree)->right)) + 1;//更新高度
	return *tree;

}

void Print(Bactree *tree){
	if (tree){
		Print(tree->left);
		printf("%d ", tree->val);
		Print(tree->right);
	}
}


int main(){
	Bactree *T = NULL;
	BalaceTreePush(&T, -10);
	BalaceTreePush(&T, -3);
	BalaceTreePush(&T, 0);
	BalaceTreePush(&T, 5);
	BalaceTreePush(&T, 9);
	BalaceTreePush(&T, 10);
	Print(T);

	system("pause");
	return 0;
}

資料結構——平衡二叉樹(AVL樹)之插入前言一.定義二.基本操作

文章目錄

前言

一.定義

二.基本操作

1.查找，

2.插入(如何調整)

如何調整

代碼實作插入

繼續閱讀

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

基礎算法之二分查找

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

poj3249

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

PAT 1089 Insert or Merge[難]

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器