md還不會用博客園的編輯器，排版炸了，可以去csdn看，
https://blog.csdn.net/wonder13579/article/details/105415879
首先我們來復習一下基礎知識吧
二叉查找樹
左子樹的所有節點，值都小于本節點，右子樹的所有節點，值都大于本節點，
由于這個性質，在查找時可以把要查值和節點比較，如果大于當前節點，就去右子樹找，小于就去左子樹找，這樣，每次比較一個節點，就把待查資料排除了一半，可以達到logn的查找效率，
10次比較，就能處理1,024個資料，
20次比較，就能處理1,048,576個資料，
此外，中序遍歷一顆二叉查找樹，顯然結果應該是升序的，
缺點：形成依賴于節點插入順序，當有序插入時，會退化為鏈表，
例：當依次插入1，2，3，4，就會產生這樣的查找樹，此時它跟一個鏈表是一樣的，為了解決這個問題，出現了平衡二叉樹，
平衡二叉樹
定義：是一顆二叉查找樹，并且左右子樹深度差距不超過1，其左右子樹也是平衡二叉樹，
平衡二叉樹通過旋轉操作實作平衡，分LL，LR，RR，RL四種，觀察時注意看圖，
首先記住，平衡二叉樹還是一個二叉查找樹，它的中序遍歷結果還是有序的，
而旋轉操作，只是把中序遍歷結果中，中心節點的位置，向左或者向右移動了一位，避免退化為鏈表，
紅黑樹
簡單介紹，以后可能把紅黑樹也實作了，給平衡二叉樹添加了紅黑性質，只保證黑色節點是完全平衡的，這讓它的平衡操作沒有那么頻繁，但是最差的情況下，只比最好的情況多一倍，
定義
（1）每個節點或者是黑色，或者是紅色，
（2）根節點是黑色，
（3）每個葉子節點（NIL）是黑色， [注意：這里葉子節點，是指為空(NIL或NULL)的葉子節點！]
（4）如果一個節點是紅色的，則它的子節點必須是黑色的，
（5）從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點，
下面開始討論實作程序
討論具體程序之前，我們先給出二叉樹的定義，以及我使用的工具函式，
工具函式包括一個disp，用來把二叉樹轉換為leetcode格式，然后就可以用leetcode可視化節點了，還有一個顯示二叉樹主要資料的，方便除錯，
平衡二叉樹的旋轉
注意，L指left左，R指right右，LL就是跟左左節點有關，以此類推，
LL旋轉，調整根，根左邊節點，根左邊節點的左邊節點，
RR旋轉，調整根，根右邊節點，根右邊節點的右邊節點，
LR旋轉，調整根，根左邊節點，根左邊節點的右邊節點，
RL旋轉，調整根，根右邊節點，根右邊節點的左邊節點，
這個旋轉程序，算是平衡二叉樹最難的部分，光看懂旋轉都很難，我找到一種比較簡單的方法總算把它給理解了，
首先記住，平衡二叉樹還是一個二叉查找樹，它的中序遍歷結果還是有序的，
而旋轉操作，只是把中序遍歷結果中，中心節點的位置，向左或者向右移動了一位，避免退化為鏈表，
由此我們可以直接得到旋轉前后的節點順序，剩下的就是觀察那些節點被變化了，編程實作這些變化，即可完成旋轉操作，
口說無憑，我們根據實體來觀察，
RR旋轉
如圖所示，進行了一次RR旋轉，
中序遍歷的結果都是[1,2,3,4,5,6,7]，不同的是旋轉后4成為了根節點，
仔細觀察旋轉程序，發現變化的節點是2，4，3.
即4變成了根節點，3變成了2的右節點，2變成了4的左節點，
想想為什么要這么做，下面一段注意結合圖理解，調整前根節點的左右子樹高度差大于1，不符合平衡二叉樹定義，現在換4做根節點，他就可以符合了，而原來的2節點比4小，應該成為4的左節點，原來4的左節點3就消失了，應該找個位置再把它放回去，好了，清楚了，按這個順序把它寫成代碼：
其他旋轉程序
有了RR旋轉，LL旋轉就是左右換了一下，差不多，看看LR旋轉
對于LR旋轉其實就是先對根的左節點做一次RR旋轉，再對根自己做一次LL旋轉，
全部四種旋轉程序
實作平衡二叉樹的插入
如果是一個簡單的查找二叉樹，只要遞回插入新節點即可，
平衡二叉樹在這個基礎上，加入計算左右子樹高度差的程序，如果不平衡，只要進行對應的旋轉操作即可讓它重新平衡，
手寫平衡二叉樹的洗掉
洗掉比插入要復雜的多，
需要在子樹中找到一個節點，然后用它替換要洗掉的節點的位置，
同時每次調整都需要重新計算節點深度，對不平衡的節點需要進行旋轉操作，
洗掉的主要程序
首先，遞回找到需要洗掉的節點，類似于查找，如果目標值大于當前節點，在右邊找，否則去左邊找，
對要洗掉的節點，在其深度更大的一個子樹進行操作（遞回），
如左子樹深度更大，就在左子樹查找最大的節點，用它替換要洗掉的節點的位置，
此處查找最大節點程序寫了個子函式，依然使用遞回，在后面介紹，
最后，需要重新計算遞回路徑上所有節點的高度，如果出現了不平衡，需要使用旋轉調整，
洗掉子程序，尋找替代節點
找到替代節點并把它摘出來的程序，因為左右子樹處理程序類似，用在左子樹中找最大舉例，
因為平衡二叉樹還是有序的，只要一直取右子樹即可找到最大節點，
注意找到后，需要調整替代節點的父節點，因為替代節點被摘出去了，父節點不能再指向它，
父節點應該指向替代節點的左節點，
對于右子樹的處理程序類似，
調整子程序
對于一個節點，如果左子樹高度比右子樹高度大超過1，需要調整左子樹，
通過判斷要洗掉的值，和左子樹值的大小，可以確定該使用LL旋轉，還是LR旋轉，
在每個遞回的結束，都需要進行調整，
測驗
我把1到15依次加入平衡二叉樹，然后依次洗掉根節點，輸出每個操作完成后的樹，
結果正常，輸出如下，可以拿到leetcode上看看效果，
[1,null,null]
[1,null,2,null,null]
[2,1,3,null,null,null,null]
[2,1,3,null,null,null,4,null,null]
[2,1,4,null,null,3,5,null,null,null,null]
[4,2,5,1,3,null,6,null,null,null,null,null,null]
[4,2,6,1,3,5,7,null,null,null,null,null,null,null,null]
[4,2,6,1,3,5,7,null,null,null,null,null,null,null,8,null,null]
[4,2,6,1,3,5,8,null,null,null,null,null,null,7,9,null,null,null,null]
[4,2,8,1,3,6,9,null,null,null,null,5,7,null,10,null,null,null,null,null,null]
[4,2,8,1,3,6,10,null,null,null,null,5,7,9,11,null,null,null,null,null,null,null,null]
[8,4,10,2,6,9,11,1,3,5,7,null,null,null,12,null,null,null,null,null,null,null,null,null,null]
[8,4,10,2,6,9,12,1,3,5,7,null,null,11,13,null,null,null,null,null,null,null,null,null,null,null,null]
[8,4,12,2,6,10,13,1,3,5,7,9,11,null,14,null,null,null,null,null,null,null,null,null,null,null,null,null,null]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null]
[9,4,12,2,6,10,14,1,3,5,7,null,11,13,15,null,null,null,null,null,null,null,null,null,null,null,null,null,null]
[10,4,12,2,6,11,14,1,3,5,7,null,null,13,15,null,null,null,null,null,null,null,null,null,null,null,null]
[11,4,13,2,6,12,14,1,3,5,7,null,null,null,15,null,null,null,null,null,null,null,null,null,null]
[12,4,14,2,6,13,15,1,3,5,7,null,null,null,null,null,null,null,null,null,null,null,null]
[7,4,14,2,6,13,15,1,3,5,null,null,null,null,null,null,null,null,null,null,null]
[6,4,14,2,5,13,15,1,3,null,null,null,null,null,null,null,null,null,null]
[5,3,14,2,4,13,15,1,null,null,null,null,null,null,null,null,null]
[4,2,14,1,3,13,15,null,null,null,null,null,null,null,null]
[13,2,14,1,3,null,15,null,null,null,null,null,null]
[14,2,15,1,3,null,null,null,null,null,null]
[3,2,15,1,null,null,null,null,null]
[2,1,15,null,null,null,null]
[15,1,null,null,null]
[1,null,null]
資料
紅黑樹，超強動靜圖詳解，簡單易懂
https://zhuanlan.zhihu.com/p/79980618?utm_source=cn.wiz.note
源代碼
/*
平衡二叉樹
*/
// #include "tool.h"
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
class AVLTree{
public:
class AVLTreeNode{
public:
int val;
int height;
AVLTreeNode *left;
AVLTreeNode *right;
public:
AVLTreeNode(int _val){
val=_val;
height=0;
left=NULL;
right=NULL;
}
};
//不得不使用全域變數，有些遞回函式需要回傳多個值
AVLTreeNode *_my_temp;
/*這部分是為了輸出樹的結構資訊，按照leetcode樹節點可視化格式輸出*/
void Disp(){
if(root==NULL){
cout<<"[]"<<endl;
return;
}
vector<int> ans;
queue<AVLTreeNode *> q;
q.push(root);
while(!q.empty()){
AVLTreeNode *p = q.front();q.pop();
if(p==NULL){
ans.push_back(-1);
}else{
ans.push_back(p->val);
if(p->left!=NULL)q.push(p->left);
else q.push(NULL);
if(p->right!=NULL)q.push(p->right);
else q.push(NULL);
}
}
cout<<"["<<ans[0];
for(int i=1;i<ans.size();i++){
if(ans[i]==-1)cout<<",null";
else cout<<","<<ans[i];
}
cout<<"]"<<endl;
}
//輸出所有節點資訊，
void Show(AVLTreeNode *node){
printf("val=%d,height=%d,path=%d,left=%d,right=%d\n"
,node->val,node->height,node,node->left,node->right);
if(node->left!=NULL)Show(node->left);
if(node->right!=NULL)Show(node->right);
}
void Show(){
Show(root);
}
/****************************************************************/
AVLTreeNode *root=NULL;
//取得節點高度
int GetHeight(AVLTreeNode * node){
if(node==NULL)return -1;
return node->height;
}
//調整節點高度
void SetHeight(AVLTreeNode * node){
int leftDeep = node->left!=NULL?node->left->height:-1;
int rightDeep = node->right!=NULL?node->right->height:-1;
node->height = max(leftDeep,rightDeep)+1;
// printf("val=%d,leftdeep=%d,rightdeep=%d,height=%d\n",node->val,leftDeep,rightDeep,node->height);
}
void Add(int val){
root = Add(root,val);
Disp();
}
//插入操作
AVLTreeNode *Add(AVLTreeNode * node,int val){
if(node==NULL){
node = new AVLTreeNode(val);
return node;
}
if(val < node->val){
node->left=Add(node->left,val);
if(GetHeight(node->left)-GetHeight(node->right)>1){
if(val<node->left->val)node=LLRotate(node);
else node=LRRotate(node);
}
}else{
node->right=Add(node->right,val);
if(GetHeight(node->right)-GetHeight(node->left)>1){
if(val>node->right->val)node=RRRotate(node);
else node=RLRotate(node);
}
}
SetHeight(node);
return node;
}
//洗掉操作
bool Delete(int val){
root = Delete(root,val);
return false;
}
AVLTreeNode *Delete(AVLTreeNode * node,int val){
//首先查找要洗掉的節點
if(node==NULL)return NULL;
else if(node->val<val)node->right = Delete(node->right,val);
else if(node->val>val)node->left = Delete(node->left,val);
else {
// printf("Delete find target,path=%d\n",node);
//在高度高的一側，尋找替代節點
//左側
if(GetHeight(node->left)>GetHeight(node->right)){
node->left = DeleteSubLeft(node->left);
}else{
//右側
node->right = DeleteSubRight(node->right);
}
AVLTreeNode *temp=_my_temp;
if(temp!=NULL){
//這個值是從遞回程序賦值的全域變數取回的，是要替代的節點
// printf("find replace node,path=%d\n",temp);
temp->left=node->left;
temp->right=node->right;
}
delete node;
node=temp;
}
//重新計算每個節點高度，并計算
SetHeight(node);
node = Adjust(node,val);
return node;
}
//尋找替代節點的程序
AVLTreeNode *DeleteSubLeft(AVLTreeNode * node){
if(node==NULL)return NULL;
if(node->right!=NULL){
node->right = DeleteSubLeft(node->right);
SetHeight(node);
node = Adjust(node,_my_temp->val);
return node;
}
//這里必須回傳多個值，用了全域變數
_my_temp = node;
return node->left;
}
//尋找替代節點的程序
AVLTreeNode *DeleteSubRight(AVLTreeNode * node){
if(node==NULL)return NULL;
if(node->left!=NULL){
node->left = DeleteSubRight(node->left);
SetHeight(node);
node = Adjust(node,_my_temp->val);
return node;
}
//這里必須回傳多個值，用了全域變數
_my_temp = node;
return node->right;
}
//調整節點，通過旋轉調整平衡二叉樹
//添加一個引數，表示引起改變的值的大小，方便判斷進行那種旋轉，
AVLTreeNode *Adjust(AVLTreeNode * node,int val){
if(node==NULL)return NULL;
int leftHeight = GetHeight(node->left);
int rightHeight = GetHeight(node->right);
if(leftHeight-rightHeight>1){
if(val<node->left->val)
node = LLRotate(node);
else node = LRRotate(node);
}else if(rightHeight-leftHeight>1){
if(val>node->right->val)
node=RRRotate(node);
else node = RLRotate(node);
}
SetHeight(node);
}
//查找
AVLTreeNode *Find(int target){
AVLTreeNode *node = Find(root,target);
printf("find ans path=%d\n",node);
return node;
}
AVLTreeNode *Find(AVLTreeNode * node,int target){
if(node==NULL)return NULL;
if(node->val!=target){
if(target>node->val)
return Find(node->right,target);
else return Find(node->left,target);
}
return node;
}
//尋找某節點下最小的節點
AVLTreeNode *GetMin(AVLTreeNode *node){
while(node->left==NULL)return node;
return GetMin(node->left);
}
//尋找某節點下最大的節點
AVLTreeNode *GetMax(AVLTreeNode *node){
while(node->right==NULL)return node;
return GetMin(node->right);
}
/*四種旋轉操作*/
AVLTreeNode * LLRotate(AVLTreeNode *node){
if(node==NULL||node->left==NULL)return node;
AVLTreeNode *temp=node->left;
node->left=temp->right;
temp->right=node;
SetHeight(node);
SetHeight(temp);
return temp;
}
AVLTreeNode * RRRotate(AVLTreeNode *node){
if(node==NULL||node->right==NULL)return node;
AVLTreeNode *temp=node->right;
node->right=temp->left;
temp->left=node;
SetHeight(node);
SetHeight(temp);
return temp;
}
AVLTreeNode *LRRotate(AVLTreeNode *node){
//對左子樹RR旋轉
node->left = RRRotate(node->left);
//對node LL旋轉
node = LLRotate(node);
}
AVLTreeNode *RLRotate(AVLTreeNode *node){
//對右子樹LL旋轉
node->right = LLRotate(node->right);
//對node RR旋轉
node = RRRotate(node);
}
//測驗用，用來訪問類的物件
void Test(){
AVLTreeNode *node=NULL;
//根據順序把資料插入平衡二叉樹
// int size=15,all[]={8,4,12,2,6,10,14,1,3,5,7,9,11,13,15};
for(int i=1;i<=15;i++){
Add(i);
}
Disp();
//依次洗掉平衡二叉樹頂點的元素
for(int i=1;i<15;i++){
Delete(root->val);
Disp();
// Show();
}
}
};
int main(){
AVLTree *tree = new AVLTree();
tree->Test();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/63646.html
標籤：其他
上一篇：線索二叉樹的線索化及遍歷