C++實現AVL樹的基本操作指南

Posted on 2022-01-05 by WalkonNet

AVL樹的概念

二叉搜索樹雖可以縮短查找的效率，但如果數據有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當於在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數學傢G.M.Adelson-Velskii和E.M.Landis在1962年發明瞭一種解決上述問題的方法：當向二叉搜索樹中插入新結點後，如果能保證每個結點的左右子樹高度之差的絕對值不超過1(需要對樹中的結點進行調整)，即可降低樹的高度，從而減少平均搜索長度。

一棵AVL樹或者是空樹，或者是具有以下性質的二叉搜索樹：

它的左右子樹都是AVL樹
左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)
平衡因子的計算是右子樹的高度減去左子樹的高度的差值結果

如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。如果它有n個結點，其高度可保持在O(log N) ，搜索時間復雜度O( log N)。

AVL樹節點的定義

template<class K, class V>
struct AVLTreeNode 
{
	AVLTreeNode<K, V>* _left; //左孩子
	AVLTreeNode<K, V>* _right; //右孩子
	AVLTreeNode<K, V>* _parent; //父親結點
	 
	pair<K, V> _Kv; //鍵值
	int _bf; //平衡因子

	//構造函數
	AVLTreeNode(const pair<K, V>& Kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_Kv(Kv)
		,_bf(0)
	{ }

};

AVL樹的定義

template<class K, class V>
class AVLTree 
{
	typedef AVLTreeNode<K, V> Node;
public:
	AVLTree() 
		:_root(nullptr)
	{}

private:
	Node* _root;
};

AVL樹的插入

AVL樹就是在二叉搜索樹的基礎上引入瞭平衡因子，因此AVL樹也可以看成是二叉搜索樹。那麼AVL樹的插入

過程可以分為兩步：

按照二叉搜索樹的方式插入新節點

與根結點比較如果比根大就往右子樹插入，如果比根小就往左子樹插入，直到走到合適的位置就插入，由於這裡是三叉鏈所以需要處理結點之間的關聯關系

bool Insert(const pair<K, V> &kv) 
	{
		if (!_root) _root = new Node(kv); //初始根節點

		Node* cur = _root;
		Node* parent = _root;
		while (cur) 
		{
			K key = cur->_Kv.first;
			if (key > kv.first) //比根結點的key值小，
			{
				parent = cur;
				cur = cur->_left;
			}
			else if(key < kv.first)//比根結點的key值大，
			{
				parent = cur;
				cur = cur->_right;
			}
			else 
			{
				return false;  //插入失敗
			}
		}
		
		//開始插入
		cur = new Node(kv);
		Node* newNode = cur;
		if (parent->_Kv.first > newNode->_Kv.first) //新插入的結點key值比根節點小就插入到左子樹
		{
			parent->_left = newNode;
			newNode->_parent = parent;
		}
		else		//新插入的結點key值比根節點大就插入到右子樹
		{
			parent->_right = newNode;
			newNode->_parent = parent;
		}
	}

調整節點的平衡因子

當左右子樹的高度發生瞭變化，那麼就需要對父親及祖先路徑上的所有結點的平衡因子進行調整

//更新祖先路徑的所以結點的平衡因子
		/* 
			總結五種情況：
				1、新增結點出現在父結點的左邊，平衡因子減減
				2、新增結點出現在父結點的右邊，平衡因子加加
				3、父親的平衡因子為0就不再調整
				4、父親結點的平衡因子為1或者-1繼續調整
				5、父親結點的平衡因子為2或者-2那就旋轉
				
		*/
	while (parent) 
	{
		if (parent->_left == cur) parent->_bf--;   //1、
		if (parent->_right == cur) parent++;	   //2、
		if (parent->_bf == 0) break; 			  //3、
		if (parent->_bf == -1 || parent->_bf == 1)//4、 
		{
			cur = parent;
			parent = parent->_parent;
		}
		if (parent->_bf == -2 || parent->_bf == 2) //5、
		{
			//旋轉
			if (parent->_bf == -2) 
			{
				if (cur->_bf == -1) RotateR(parent); //左邊高，右單旋
				else RotateLR(parent); //左右雙旋
			}
			else //右 parent->_bf == 2
			{
				if (cur->_bf == 1) RotateL(parent);//右邊高左單旋轉
				else RotateRL(parent); //右左雙旋
			}

			break;
		}
	}

AVL樹的四種旋轉

旋轉的原則是遵循搜索樹的規則，盡量讓兩邊平衡

如果在一棵原本是平衡的AVL樹中插入一個新節點，可能造成不平衡，此時必須調整樹的結構，使之平衡化。根據節點插入位置的不同，AVL樹的旋轉分為四種：

右單旋

新節點插入較高左子樹的左側—左左：右單旋

不管是哪種單旋都得考慮兩種情況：

1、局部旋轉，如果parent並不是樹的_root結點，那麼就需要調整subL和根結點的關系

2、獨立旋轉，parent就是樹的_root結點，那麼subL就是旋轉後的根節點瞭

3、subLR有可能為null

//右單旋
void RotateR(Node* parent) 
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR; 
	if (subLR) subLR->_parent = parent;  //防止subLR為nullptr

	subL->_right = parent;
	Node* parent_parent = parent->_p	arent; //指針備份
	parent->_parent = subL;
	if (_root == parent) //如果parent就是樹的根 
	{
		_root = subL;  //subL取代parent
		_root->_parent = nullptr;
	}
	else  //如果parent並不是樹的根
	{
		if (parent_parent->_left == parent) parent->_left = subL;
		else parent_parent->_right = subL;

		subL->_parent = parent_parent; //subL去做parent_parent的孩子
	}
	//調節平衡因子
	subL->_bf = parent->_bf = 0;
}

左單旋

新節點插入較高右子樹的右側—右右：左單旋

跟右單旋幾乎是一樣的做法

1、局部旋轉，如果parent並不是樹的_root結點，那麼就需要調整subL和根結點的關系

2、獨立旋轉，parent就是樹的_root結點，那麼subL就是旋轉後的根節點瞭

3、subRL有可能為null

//左單旋
void RotateL(Node* parent) 
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	
	parent->_right = subRL;
	if (subRL) subRL->_parent = parent;
	
	subR->_left = parent;
	Node* parent_parent = parent->_parent;
	parent->_parent = subR;
	
	if (_root == parent) 
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	else  
	{
		if (parent_parent->_left == parent) parent_parent->_left = subR;
		else parent_parent->_right = subR;

		subR->_parent = parent_parent;
	}
	subR->_bf = parent->_bf = 0;
}

左右雙旋

新節點插入較高左子樹的右側—左右：先左單旋再右單旋

1、新增結點在b或c都會影響左右子樹的高度，從而引發雙旋

h > 0情況一：

h > 0，情況二：

h == 0情況三：

//左右旋轉
	void RotateLR(Node* parent) 
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);
		if (bf == -1)  //h > 0，新增結點在b
		{
			parent->_bf = 1;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else if (bf == 1) //h > 0，新增結點在c
		{
			subL->_bf = -1;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else if(bf == 0) //h = 0
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		
	}

右左雙旋

右左雙旋跟左右雙旋的情況基本是類似的，這裡就不列舉多種情況瞭

新節點插入較高右子樹的左側—右左：先右單旋再左單旋

	//右左旋轉
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);
		if (bf == -1)  //h > 0，新增結點在b
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 1) //h > 0，新增結點在c
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 0)//h = 0
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = 0;
		}

	}

查找

Node* Find(const K& key) 
{
	Node* cur = _root;
	while (cur) 
	{
		if (key > cur->_Kv.first) cur = cur->_right; //左子樹
		else if (key < cur->_Kv.first) cur = cur->_left; //右子樹
		else return cur;
	}
}

其他接口

判斷是不是平衡二叉樹

int height(Node* root) //求高度
{
	return !root ? 0 
		   : max(height(root->_left), 
			 height(root->_right)) + 1;
}

void _Inorder(Node* root)//中序遍歷 
{
	if (!root) return;
	_Inorder(root->_left);
	printf("%d : %d\n",root->_Kv.first, root->_Kv.second);
	_Inorder(root->_right);
}

//判斷是不是平衡二叉樹
bool IsAVLTree() 
{
	return _IsAVLTree(_root);
}

bool _IsAVLTree(Node* root)
{
	if (!root) return true;
	int left = height(root->_left);
	int right = height(root->_right);
	//檢查平衡因子	
	if (right - left != root->_bf)
	{
		printf("錯誤的平衡因子 %d :%d\n", root->_Kv.first, root->_Kv.second);
		return false;
	}
	return (abs(right - left) < 2)
		&& _IsAVLTree(root->_left)
		&& _IsAVLTree(root->_right);
}

析構函數

//析構函數
~AVLTree()
{
	Destroy(_root);
	_root = nullptr;
}

void Destroy(Node *root)//後序銷毀結點
{
	if (!root) return;
	Destroy(root->_left);
	Destroy(root->_right);
	delete root;
}

拷貝構造

Node* copy(Node* cp)
{
	if (!cp) return nullptr;

	Node* newnode = new Node(cp->_Kv);
	newnode->_left = copy(cp->_left);
	newnode->_right = copy(cp->_right);
	return newnode;
}

//拷貝構造
AVLTree(const AVLTree<K, V>& job)
{
	if(&job != this)
	_root = copy(job._root);
}

拷貝賦值

void operator=(AVLTree<K, V> tmp)
{
	if (&tmp != this)
	swap(tmp._root, this->_root);
}

重載operator[ ]

V& operator[](const K& key)
{
	return (Insert(make_pair(key, V())).first)->_Kv.second;
}

AVL樹的完整實現代碼博主已經放在 git.

總結

到此這篇關於C++實現AVL樹的文章就介紹到這瞭,更多相關C++實現AVL樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

C++實現AVL樹的基本操作指南

目錄

AVL樹的概念

AVL樹的插入

AVL樹的四種旋轉

右單旋

左單旋

左右雙旋

右左雙旋

查找

其他接口

析構函數

拷貝構造

拷貝賦值

總結

推薦閱讀：

發佈留言取消回覆

近期文章

目錄

AVL樹的概念

AVL樹的插入

AVL樹的四種旋轉

右單旋

左單旋

左右雙旋

右左雙旋

查找

其他接口

析構函數

拷貝構造

拷貝賦值

總結

推薦閱讀：

發佈留言 取消回覆

近期文章

標籤

發佈留言取消回覆