[資料結構] 搜尋樹與AVL樹

文章目錄

- 1. 搜尋樹
- - 1.1. 了解二叉搜尋樹
  - 1.2. 搜尋樹性能分析
- 2. AVL樹
- - 2.1. 了解AVL樹
  - 2.2. AVL樹節點的資料結構
  - 2.3. AVL樹的插入
  - 2.4. AVL樹的旋轉*
  - 2.5. AVL樹的删除
  - 2.6. AVL樹性能分析

1. 搜尋樹

1.1. 了解二叉搜尋樹

二叉搜尋樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹:

若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
它的左右子樹也分别為二叉搜尋樹

如圖所示

[資料結構] 搜尋樹與AVL樹

當進行資料搜尋時

[資料結構] 搜尋樹與AVL樹
進行資料插入時過程與資料搜尋相同, 找到一個适合自己的空節點
資料删除

[資料結構] 搜尋樹與AVL樹

1.2. 搜尋樹性能分析

插入和删除操作都必須先查找，查找效率代表了二叉搜尋樹中各個操作的性能.
理想情況下, 插入的樹是完全二叉樹

[資料結構] 搜尋樹與AVL樹
最壞情況下, 插入的樹成了單鍊樹

[資料結構] 搜尋樹與AVL樹
最優情況下，二叉搜尋樹為完全二叉樹，其平均比較次數為：logn
最差情況下，二叉搜尋樹退化為單支樹，其平均比較次數為：n / 2

2. AVL樹

2.1. 了解AVL樹

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

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

它的左右子樹都是AVL樹
左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)
如果一棵二叉搜尋樹是高度平衡的，它就是AVL樹。如果它有n個結點，其高度可保持在，搜尋時間複雜度O(logn)

[資料結構] 搜尋樹與AVL樹

2.2. AVL樹節點的資料結構

template <class T>
class AVLTreeNode
{
public:
	AVLTreeNode(T data)
		: _data(data)
		, _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _bf(0)
	{ }

	T _data;
	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	int _bf;	// 該節點平衡因子
};

2.3. AVL樹的插入

AVL樹的插入過程可以分為兩步：

1. 按照二叉搜尋樹的方式插入新節點

2. 調整節點的平衡因子

新增節點的平衡因子是0, 新增節點的祖先平衡因子可能受影響

1. 新增在parent的右子樹, parent->bf + = 1

2. 新增在parent的左子樹, parent->bf - = 1
通過cur的位置更新parent的平衡因子, 更新完成後

1. 如果parent->bf == 1 / -1, 說明parent為根的子樹的高度變了, 繼續向上更新

2. 如果parent->bf == 2 / -2, 說明parent為根的子樹已經不平衡, 需要旋轉處理

3. 如果parent->bf == 0, 說明parent所在的子樹原來高度是 1/-1,現在把矮的補齊, parent所在的子樹高度不變, 停止更新

bool insert(const T& data)
	{
		// 如果樹内無節點
		if (_pRoot == nullptr)
		{
			_pRoot = new Node(data);
			return true;
		}
		// 1. 按照二叉搜尋樹的方式插入新節點
		Node* pCur = _pRoot;
		Node* parent = nullptr;
		while (pCur)
		{
			parent = pCur;
			if (data < pCur->_data)
			{
				pCur = pCur->_pLeft;
			}
			else if (data > pCur->_data)
			{
				pCur = pCur->_pRight;
			}
			else
			{
				// 插入相同節點, 傳回失敗
				return false;
			}
		}
		pCur = new Node(data);
		if (parent->_data < data)
		{
			parent->_pRight = pCur;
		}
		else
		{
			parent->_pLeft = pCur;
		}
		pCur->_pParent = parent;

		// 2. 調整節點的平衡因子
		while (parent != nullptr)
		{
			if (parent->_pLeft == pCur)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				pCur = parent;
				parent = pCur->_pParent;
			}
			else if (parent->_bf == -2 || parent->_bf == 2)
			{
				// 旋轉操作
			}
		}
		return true;
	}

2.4. AVL樹的旋轉*

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

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

[資料結構] 搜尋樹與AVL樹

[資料結構] 搜尋樹與AVL樹

注意判斷parent的父節點和subLR是否存在

void RotateR(Node* parent)
	{
		Node* pSubL = parent->_pLeft;
		Node* pSubLR = pSubL->_pRight;

		pSubL->_pRight = parent;
		Node* pParent = parent->_pParent;
		parent->_pParent = pSubL;

		if (pSubLR != nullptr)
		{
			pSubLR->_pParent = parent;
		}
		parent->_pLeft = pSubLR;

		if (parent == _pRoot)
		{
			_pRoot = pSubL;
			pSubL->_pParent = nullptr;
		}
		else
		{
			if (pParent->_pLeft == parent)
			{
				pParent->_pLeft = pSubL;
			}
			else
			{
				pParent->_pRight = pSubL;
			}
			pSubL->_pParent = pParent;
		}
		
		parent->_bf = pSubL->_bf = 0;
	}

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

[資料結構] 搜尋樹與AVL樹

[資料結構] 搜尋樹與AVL樹

void RotateL(Node* parent)
	{
		Node* pSubR = parent->_pRight;
		Node* pSubRL = pSubR->_pLeft;

		pSubR->_pLeft = parent;
		Node* pParent = parent->_pParent;
		parent->_pParent = pSubR;

		parent->_pRight = pSubRL;
		if (pSubRL != nullptr)
		{
			pSubRL->_pParent = parent;
		}
		if (parent == _pRoot)
		{
			_pRoot = pSubR;
			pSubR->_pParent = nullptr;
		}
		else
		{
			if (pParent->_pRight == parent)
			{
				pParent->_pRight = pSubR;
			}
			else
			{
				pParent->_pLeft = pSubR;
			}
			pSubR->_pParent = pParent;
		}
		parent->_bf = pSubR->_bf = 0;
	}

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

[資料結構] 搜尋樹與AVL樹

共會出現三種可能的情況

[資料結構] 搜尋樹與AVL樹
注意觀察閃電标志的平衡因子, 可以分析得到這三個點不同插入情況下平衡因子的值
完善上方代碼可得

void RotateLR(Node* parent)
	{
		Node* pSubL = parent->_pRight;
		Node* pSubLR = pSubR->_pLeft;
		int bf = pSubLR->_bf;

		RotateL(parent->_pLeft);
		RotateR(parent);

		if (bf == 1)
		{
			parent->_bf = 0;
			pSubL->_bf = 1;
			pSubLR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			pSubL->_bf = 0;
			pSubLR->_bf = 0;
		}
		else
		{
			parent->_bf = 0;
			pSubL->_bf = 0;
			pSubLR->_bf = 0;
		}
	}

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

同情況三代碼如下:

void RotateRL(Node* parent)
	{
		Node* pSubR = parent->_pRight;
		Node* pSubRL = pSubR->_pLeft;
		int bf = pSubRL->_bf;

		RotateR(parent->_pRight);
		RotateL(parent);

		if (bf == 1)
		{
			parent->_bf = -1;
			pSubR->_bf = 0;
			pSubRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			pSubR->_bf = 1;
			pSubRL->_bf = 0;
		}
		else
		{
			parent->_bf = 0;
			pSubR->_bf = 0;
			pSubRL->_bf = 0;
		}
	}

2.5. AVL樹的删除

因為AVL樹也是二叉搜尋樹，可按照二叉搜尋樹的方式将節點删除，然後再更新平衡因子，隻不過與删除不同的是，删除節點後的平衡因子更新，最差情況下一直要調整到根節點的位置.

2.6. AVL樹性能分析

AVL樹是一棵絕對平衡的二叉搜尋樹，其要求每個節點的左右子樹高度差的絕對值都不超過1，這樣可以保證查詢時高效的時間複雜度，即。但是如果要對AVL樹做一些結構修改的操作，性能非常低下，比如：插入時要維護其絕對平衡，旋轉的次數比較多，更差的是在删除時，有可能一直要讓旋轉持續到根的位置。

是以：如果需要一種查詢高效且有序的資料結構，而且資料的個數為靜态的(即不會改變)，可以考慮AVL樹，但一個結構經常修改，就不太适合. 此時, 紅黑樹就出場了!

源代碼: https://github.com/Zhangddy/DataStructure/tree/master/AVL%E6%A0%91

完.

[資料結構] 搜尋樹與AVL樹

文章目錄

1. 搜尋樹

1.1. 了解二叉搜尋樹

1.2. 搜尋樹性能分析

2. AVL樹

2.1. 了解AVL樹

2.2. AVL樹節點的資料結構

2.3. AVL樹的插入

2.4. AVL樹的旋轉*

2.5. AVL樹的删除

2.6. AVL樹性能分析

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

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

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

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

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

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

Dijkstra--簡易版（最短路徑）

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

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

hdu7108哈希