AVL樹的建立的完整C代碼怎么編寫

AVL樹的建立的完整C代碼怎么編寫，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

平衡二叉樹的相關概念

二叉搜索樹上實現查找的時間復雜度與從根節點到所查對象節點的路徑成正比，最壞情況下等于樹的高度。

在構造二叉搜索樹時，如果輸入對象的序列恰好是按其關鍵碼大小有序，則結果將產生一棵單支樹。

例如：輸入序列為{11,39,46,38,75}

在這樣的樹上查找所需要的時間是O(n)（與節點個數成正比）。

平衡樹（Balanced Tree）：高度為O(logn)的樹。

平衡二叉樹（Balanced Binary Tree）：由阿德爾森一維爾斯和蘭迪斯（Adelson-Velskii and Landis）于1962年首先提出的，所以又稱為AVL樹。

空二叉樹是AVL樹；

如果T是一棵非空的二叉搜索樹，TL和TR分別是其左子樹和右子樹，那么當T滿足以下條件時，T是一棵AVL樹：
1）TL和TR 是AVL樹；
2）|hL-hR|≤1，hL和hR分別是左子樹和右子樹的高度。

n個元素的AVL樹的高度是O(logn)；
一棵n元素的AVL搜索樹能在O(高度)=O(logn) 的時間內完成搜索；
將一個新元素插入到一棵n元素的AVL搜索樹中，可得到一棵n+1元素的AVL樹，這種插入過程可以在O(logn)時間內完成；
從一棵n元素的AVL搜索樹中刪除一個元素，可得到一棵n-1元素的AVL樹，這種刪除過程可以在O(logn)時間內完成。

為每個節點增加一個平衡因子bf。節點x 的平衡因子bf (x)定義為：bf (x)= hL-hR 。
即：x的左子樹的高度-x 的右子樹的高度。

從AVL樹的定義可以知道，平衡因子的可能取值為-1、0、1。

如果樹中任意一個結點的平衡因子的絕對值大于 1，則這棵二叉樹就失去平衡。

如果一棵AVL樹有n個節點，其高度可以保持在O(logn)，因此平均搜索長度也可以保持在O(logn)。
二叉搜索樹的算法完全適用于AVL樹。

若一棵二叉搜索樹是平衡二叉樹，插入某個節點后，可能會變成非平衡二叉樹；
【解決辦法】對該二叉樹進行平衡處理，使其變成一棵平衡二叉樹。

非AVL樹的平衡化處理

• 每插入一個新節點時，AVL樹中相關節點的平衡狀態會發生改變。

• 因此，在插入一個新節點后，需要從插入位置沿通向根的路徑回溯，檢查各節點的平衡因子（左、右子樹的高度差）；

• 如果在某一節點發現高度不平衡，停止回溯；

• 從發生不平衡的節點起，沿剛才回溯的路徑取直接下兩層的節點，做平衡化旋轉。平衡化旋轉有兩類：

1. 單旋轉（LL旋轉和LR旋轉）

2. 雙旋轉（LR旋轉和RL旋轉）

如果這三個節點處于一條直線上，則采用單旋轉進行平衡化。

如果這三個節點處于一條折線上，則采用雙旋轉進行平衡化。

LL 平衡旋轉：

若在 C 的左子樹的左子樹上插入 結點，使 C 的平衡因子從 1 增加 至 2， 需要進行一次順時針旋轉。 (以 B 為旋轉軸）

RR 平衡旋轉：

若在 A 的右子樹的右子樹上插入 結點，使 A 的平衡因子從 -1 改變為 -2，需要進行一次逆時針旋轉。(以 B 為旋轉軸）

LR 平衡旋轉：

若在 C 的左子樹的右子樹上插入 結點，使 C 的平衡因子從 1 增加 至 2， 需要先進行逆時針旋轉，  再順時針旋轉。 (以插入的結點 B 為旋轉軸）

RL 平衡旋轉：

若在 A 的右子樹的左子樹上插入 結點，使 A 的平衡因子從 -1 改變 為 -2，需要先進行順時針旋轉，再逆時針旋轉。(以插入的結點 B 為旋轉軸）

LL旋轉：新插入節點在不平衡節點的左子樹的左子樹中；

RR旋轉：新插入節點在不平衡節點的右子樹的右子樹中；

LR旋轉：新插入節點在不平衡節點的左子樹的右子樹中；

RL旋轉：新插入節點在不平衡節點的右子樹的左子樹中。

AVL樹的建立完整C代碼

/* AVL樹的創建完整C代碼 */

#include <stdio.h>
#include <stdlib.h>
#define max(a,b) ( ((a)>(b)) ? (a):(b) )

typedef int ElemType;

//定義了平衡二叉樹的結構體
typedef struct AVLNode {
	ElemType data;
	int height;
	struct AVLNode *lchild, *rchild;
}AVLNode, *AVLTree;

//計算高度的函數
int GetHeight( AVLTree t )
{
	if( NULL == t )
		return -1;
	else
		return (1+max(GetHeight(t->lchild),GetHeight(t->rchild)));
}

//右旋操作
void SingleRotateWithRight( AVLTree *t )
{
	AVLTree p;

	p = (*t)->lchild;
	(*t)->lchild = p->rchild;
	p->rchild = (*t);

	//結點的位置改變，更新結點的高度值
	(*t)->height = GetHeight( *t );
	p->height = GetHeight( p );
	*t = p;
}

//左旋操作
void SingleRotateWithLeft( AVLTree *t )
{
	AVLTree p;

	p = (*t)->rchild ;
	(*t)->rchild = p->lchild ;
	p->lchild = (*t) ;

	//結點為位置改變，更新新結點的高度值
	(*t)->height = GetHeight( *t );
	p->height = GetHeight( p );

	*t = p;
}

//雙旋轉操作--先左后右
void DoubleRotateWithLeft( AVLTree *t )		//LR型失衡AVL
{
	 SingleRotateWithLeft( &(*t)->lchild );
	 SingleRotateWithRight( t );
}

//雙旋操作--先右后左
void DoubleRotateWithRight( AVLTree *t )	//RL型失衡AVL
{
	SingleRotateWithRight( &(*t)->rchild );
	SingleRotateWithLeft( t );
}

//AVL樹的結點插入函數
void Insert( AVLTree *t, ElemType e )
{
	if( NULL == *t ) {
		(*t) = (AVLTree)malloc(sizeof(AVLNode));
		(*t)->data = e;
		(*t)->height = 0;
		(*t)->lchild = (*t)->rchild = NULL;
	}

	else if( e < (*t)->data ) {		//插入到左子樹中
		Insert( &(*t)->lchild, e );
		if( GetHeight((*t)->lchild) - GetHeight((*t)->rchild) == 2 ) {	//AVL樹不平衡
			if( e < (*t)->lchild->data ) 		//LL插入到左子樹左邊
				SingleRotateWithRight( &(*t) );
			else
				DoubleRotateWithLeft( &(*t) );	//LR插入到左子樹右邊，先對左子樹左旋，再對當前根節點右旋
		}
	}

	else if( e > (*t)->data ) {
		Insert( &(*t)->rchild, e );
		if( GetHeight((*t)->lchild) - GetHeight((*t)->rchild) == -2 ) {
			if( e > (*t)->rchild->data )			//插入到右子樹右邊
				SingleRotateWithLeft( &(*t) );
			else
				DoubleRotateWithRight( &(*t) );    //插入到右子樹左邊，先對右子樹右旋，再對當前根節點左旋
		}
	}

	(*t)->height = max( GetHeight((*t)->lchild), GetHeight((*t)->rchild)) + 1;
}

//定義創建AVL樹的函數
void CreateAVL( AVLTree *t, ElemType *a, int n )
{
	(*t) = NULL;
	for( int i=0; i<n; i++ )
		Insert( t, a[i] );
}


//中序遍歷打印AVL樹
void InOrderPrint( AVLTree t )
{
	if( NULL == t )
		return;

	InOrderPrint( t->lchild );
	printf("%d ", t->data);
	InOrderPrint( t->rchild );
}


int main()
{
	int n;
	AVLTree t;
	printf("請輸入AVL樹的結點數:\n");
	scanf("%d", &n);
	ElemType *a = (ElemType *)malloc(sizeof(ElemType)*n);
	printf("請輸入結點數據:\n");
	for( int i=0; i<n; i++ )
		scanf("%d", &a[i]);

	CreateAVL( &t, a, n );
	printf("該AVL樹的中序遍歷結果為:\n");
	InOrderPrint( t );

	printf("\n");

	return 0;
}

測試數據以及測試結果

經過單步調試可得AVL樹為：

測試通過。

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。