引入
上一篇寫了二叉排序樹，構建一個二叉排序樹，如果構建序列是完全有序的，則會出現這樣的情況：
顯然這種情況會使得二叉搜索樹退化成鏈表，當出現這樣的情況，二叉排序樹的查找也就退化成了線性查找，所以我們需要合理調整二叉排序樹的形態，使得樹上的每個結點都盡量有兩個子結點，這樣整個二叉樹的高度就會大約在\(log(n)\) 左右，其中 \(n\) 為結點個數，
基本性質
? AVL樹也稱為平衡二叉樹，是一種自平衡的二叉排序樹，本質上仍然是一顆二叉排序樹，只是增加了“平衡”的要求，平衡是指，對AVL樹中任何節點的兩個子樹的高度之差（稱為平衡因子）的絕對值不超過 \(1\) ，能保證上面這一點，AVL樹的高度就能始終保持在 \(O(logn)\) 級別，
資料結構定義
由于需要對每個結點都得到平衡因子，因此在AVL樹的結構中加入一個變數height，用來記錄當前結點為根結點的子樹的高度：
typedef struct Node
{
char data;
int height;
struct Node* Left;
struct Node* Right;
}*AVLTree;
獲取 root 結點高度：
int getHeight(Node *root){
if(!root) return 0;//空節點高度為0
return root->height;
}
基本操作
查找
? AVL樹是一顆二叉查找樹，因此查找操作與二叉查找樹相同，因為AVL樹的高度為 \(O(logn)\) 級別，所以查找操作的時間復雜度為 \(O(logn)\)，
可以得到和二叉查找樹完全相同的代碼：
//找不到回傳NULL，找到回傳該節點，
//非遞回
Node* Find(AVLTree t, int x) {
if (!t)return NULL;
if (t->data =https://www.cnblogs.com/czc1999/p/= x) return t;
if (x < t->data) return BSTreeFind(t->Left, x);
if (x > t->data) return BSTreeFind(t->Right, x);
}
//非遞回
Node* Find(AVLTree T,int x) {
BSTree p = T;
while (p) {
if (x == p->data)
return p;
p = x > p->data ? p->Right : p->Left;
}
return NULL;
}
插入
左旋
先拋開AVL樹的插入問題，看下面左邊的二叉排序樹，大家本來和平共處，突然有一天 B 覺得自己的權值比 A 大，要造反，但是B要做根結點，必須也要保證調整后的樹仍然是一顆二叉排序樹，
☆上所有權值都比A小， ? 上所有權值都比B大，無需在調整中進行位置變動；因為調整后B的左孩子變成了A，那么▲必須移動到其他地方去，因為A、B、▲的權值關系滿足 A<▲<B ，所以讓▲成為A的右子樹即可，
這個調整程序稱為左旋，分解調整程序如下：
代碼如下：
void L(AVLTree *root){
Node* temp = (*root)->Right; //root指向結點A，temp指向結點B
(*root)->Right = temp->Left; //圖示步驟2
temp->Left = *root; //圖示步驟3
root->height = max(getHeight(root->Left), getHeight(root->Rihgt)) + 1;//更新結點A高度
temp = max(getHeight(temp->Left), getHeight(temp->Rihgt)) + 1;//更新結點B高度
*root = temp;//圖示步驟4
}
右旋
右旋是左旋的逆程序，如下：
分解調整程序如下：
代碼如下：
void R(AVLTree *root) {
Node* temp = (*root)->Left;//root指向結點B，temp指向結點A
(*root)->Left = temp->Right;
temp->Right = *root;
root->height = max(getHeight(root->Left), getHeight(root->Rihgt)) + 1;
temp = max(getHeight(temp->Left), getHeight(temp->Rihgt)) + 1;
*root = temp;
}
? 接下來討論AVL樹的插入操作，假設現在已經有一顆平衡二叉樹，那么在向其中插入一個結點時，一定會有結點的平衡因子發生改變，此時就可能會有結點的平衡因子大于1 ，這樣以該結點為根結點的子樹就是失去平衡的，會使平衡二叉樹發生失衡的情況可以分為下面四種：
LL、RR型
左左（LL）、右右（RR），LL，RR只表示樹型（導致樹失去平衡的插入位置），不是左旋、右旋的意思，
對于LL型，需要以A結點為根進行右旋；
對于RR型，需要以A為根結點進行左旋，
所以代碼如下：
void RR_Rotate(AVLTree *root){
L(root);
}
void LL_Rotate(AVLTree *root) {
R(root);
}
LR，RL型
左右（LR）、右左（RL），
對于LR型，需要先以B結點為根結點進行一次左旋，再以A結點為根結點進行一次右旋，
對于RL型，需要先以B結點為根結點進行一次右旋，再以A結點為根結點進行一次左旋，
void LR_Rotate(AVLTree *root) {
L(&(*root)->Left);
R(root);
}
void RL_Rotate(AVLTree *root) {
R(&(*root)->Right);
L(root);
}
插入結點
插入演算法就是出現不平衡狀態時，判斷需要使用哪種旋轉方式來使得二叉樹保持平衡
AVLTree InsertAVLTree(AVLTree root, int x) {
if (root == NULL) {
root = new Node;
root->Left = NULL;
root->Right = NULL;
root->data = https://www.cnblogs.com/czc1999/p/x;
return root;
}
if (x > root->data) {
//遞回回傳插入位置的父節點或者祖父……，
root->Right = InsertAVLTree(root->Right, x);
//如果插入之后失去了平衡
if (height(root->Left) - height(root->Right) == -2) {
//如果插入的值大于,當前節點的左孩子節點，說明該節點是插在root的右子樹上的
if (x > root->Left->data) RR_Rotate(&root);
else RL_Rotate(&root);
}
}
else if (x < root->data) {
root->Left = InsertAVLTree(root->Left, x);
if (height(root->Left) - height(root->Right) == 2) {
if (x < root->Left->data) LL_Rotate(&root);
else LR_Rotate(&root);
}
}
else {
cout <<"the number is already included." << endl;
return NULL;
}
return root;
}
洗掉結點
和二叉排序樹的節點的洗掉差不多，就是多出來一個判斷從哪個子樹洗掉節點的問題，
void AVLTreeDel(AVLTree *root, int data)
{
if (!*root) {
cout << "delete failed" << endl;
return;
}
Node *p = *root;
if (data =https://www.cnblogs.com/czc1999/p/= p->data) {
//左右子樹都非空
if (p->Left && p->Right) {
//在高度更大的那個子樹上進行洗掉操作
//進左子樹，右轉到底，進右子樹，左轉到底，轉彎碰壁，殺孩子，
if (height(p->Left) > height(p->Right)) {
Node *pre=NULL,*q = p->Left;
if (!q->Right)
q->Right = p->Right;
else {
while (q->Right) {
pre = q;
q = q->Right;
}
pre->Right = q->Left;
q->Left = p->Left;
q->Right = p->Right;
}
*root = q;
}
else {
Node *pre = NULL, *q = p->Right;
if (!q->Left)
q->Left = p->Left;
else {
while (q->Left) {
pre = q;
q = q->Left;
}
pre->Left = q->Right;
q->Left = p->Left;
q->Right = p->Right;
}
*root=q;
}
}
else
(*root) = (*root)->Left ? (*root)->Left : (*root)->Right;
delete p;
}
else if (data < p->data){//要洗掉的節點在左子樹中
//在左子樹中進行遞回洗掉
AVLTreeDel(&(*root)->Left, data);
//判斷是否仍然滿足平衡條件
if (height(p->Right) - height(p->Left) == 2){
//如果當前節點右孩子的左子樹更高
if (height(p->Right->Left) > height(p->Right->Right))
RL_Rotate(root);
else
RR_Rotate(root);
}
}
else{
AVLTreeDel(&(*root)->Right, data);
if (height(p->Left) - height(p->Right) == 2) {
if (height((*root)->Left->Left) > height((*root)->Left->Right))
LL_Rotate(root);
else
LR_Rotate(root);
}
}
}
完整測驗代碼：
#pragma once
#include "top.h"
typedef BTreeNode Node, *AVLTree;
void RR_Rotate(AVLTree *root){
Node* Right = (*root)->Right;
(*root)->Right = Right->Left;
Right->Left = *root;
*root = Right;
}
void LL_Rotate(AVLTree *root) {
Node* Left = (*root)->Left;
(*root)->Left = Left->Right;
Left->Right = *root;
*root = Left;
}
void LR_Rotate(AVLTree *root) {
RR_Rotate(&(*root)->Left);
return LL_Rotate(root);
}
void RL_Rotate(AVLTree *root) {
LL_Rotate(&(*root)->Right);
RR_Rotate(root);
}
AVLTree AVLTreeInsert(AVLTree root, int x) {
if (root == NULL) {
root = new Node;
root->Left = NULL;
root->Right = NULL;
root->data = https://www.cnblogs.com/czc1999/p/x;
return root;
}
if (x > root->data) {
root->Right = AVLTreeInsert(root->Right, x);
//遞回回傳插入位置的父節點或者祖父……，如果失去了平衡
if (height(root->Left) - height(root->Right) == -2) {
//如果插入的值大于,當前節點的右孩子節點，說明該節點是插在root的右子樹上的
//if (x > root->Left->data) RR_Rotate(&root);不能保證該節點一定有左子樹
if (x > root->Right->data)RR_Rotate(&root);
else RL_Rotate(&root);
}
}
else if (x < root->data) {
root->Left = AVLTreeInsert(root->Left, x);
if (height(root->Left) - height(root->Right) == 2) {
if (x < root->Left->data) LL_Rotate(&root);
else LR_Rotate(&root);
}
}
else {
cout <<"the number is already included." << endl;
return NULL;
}
return root;
}
AVLTree AVLTreeCreat(int *a, int length) {
AVLTree T = NULL;
for (int i = 0; i < length; i++) {
T = AVLTreeInsert(T, a[i]);
}
return T;
}
Node* AVLFind(AVLTree T, int x) {
Node *p = T;
while (p) {
if (x == p->data) break;
p = x > p->data ? p->Right : p->Left;
}
return p;
}
AVLTree AVLMax(AVLTree p)
{
if (!p) return NULL;
if (p->Right == NULL)
return p;
return AVLMax(p->Right);
}
AVLTree AVLMin(AVLTree p)
{
if (!p)
return NULL;
if (p->Left == NULL)
return p;
return AVLMin(p->Left);
}
void AVLTreeDel(AVLTree *root, int data)
{
if (!*root) {
cout << "delete failed" << endl;
return;
}
Node *p = *root;
if (data =https://www.cnblogs.com/czc1999/p/= p->data) {
//左右子樹都非空
if (p->Left && p->Right) {
//在高度更大的那個子樹上進行洗掉操作
//進左子樹，右轉到底，進右子樹，左轉到底，轉彎碰壁，殺孩子，
if (height(p->Left) > height(p->Right)) {
Node *pre=NULL,*q = p->Left;
if (!q->Right)
q->Right = p->Right;
else {
while (q->Right) {
pre = q;
q = q->Right;
}
pre->Right = q->Left;
q->Left = p->Left;
q->Right = p->Right;
}
*root = q;
}
else {
Node *pre = NULL, *q = p->Right;
if (!q->Left)
q->Left = p->Left;
else {
while (q->Left) {
pre = q;
q = q->Left;
}
pre->Left = q->Right;
q->Left = p->Left;
q->Right = p->Right;
}
*root=q;
}
}
else
(*root) = (*root)->Left ? (*root)->Left : (*root)->Right;
delete p;
}
else if (data < p->data){//要洗掉的節點在左子樹中
//在左子樹中進行遞回洗掉
AVLTreeDel(&(*root)->Left, data);
//判斷是否仍然滿足平衡條件
if (height(p->Right) - height(p->Left) == 2){
//如果當前節點右孩子的左子樹更高
if (height(p->Right->Left) > height(p->Right->Right))
RL_Rotate(root);
else
RR_Rotate(root);
}
}
else{
AVLTreeDel(&(*root)->Right, data);
if (height(p->Left) - height(p->Right) == 2) {
if (height((*root)->Left->Left) > height((*root)->Left->Right))
LL_Rotate(root);
else
LR_Rotate(root);
}
}
}
int height(BTree L) {
if (L == NULL)
return 0;
int left = height(L->Left);
int right = height(L->Right);
return left >= right ? left + 1 : right + 1;
}
void checkCreat() {
int length = 10;
int *a = getNoRepateRandomArray(length, 10);
for (int i = 0; i < length; i++) {
cout << a[i] <<",";
}
cout << endl;
AVLTree T = AVLTreeCreat(a, length);
int t = rand() % length;
AVLTreeDel(&T, a[t]);
for (int i = t; i < length - 1; i++) {
a[i] = a[i + 1];
}
Preorder(T);
cout << endl;
Inorder(T);
cout << endl;
Postorder(T);
cout << endl;
free(a);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/131556.html
標籤：其他