C++ AVLTree高度平衡的二元搜尋樹深入分析

2023-03-09 06:05:44

一、AVL樹的概念

二元搜尋樹雖可以縮短查詢的效率，但如果資料有序或接近有序二元搜尋樹將退化為單支樹，查詢元素相當於在順序表中搜尋元素，效率低下。

因此，兩位俄羅斯的數學家G.M.Adelson-Velskii和E.M.Landis在1962年發明了一種解決上述問題的方法：當向二元搜尋樹中插入新結點後，如果能保證每個結點的左右子樹高度之差的絕對值不超過1(需要對樹中的結點進行調整)，即可降低樹的高度，從而減少平均搜尋長度。

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

它的左右子樹都是AVL樹

左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)

平衡因子= 右子樹高度-左子樹高度

如果一棵二元搜尋樹是高度平衡的，它就是AVL樹。如果它有n個結點，其高度可保持在O(log2N) ，搜尋時間複雜度O(log2N)

二、AVL樹節點的定義

節點結構：三叉鏈結構（左、右、父），以及平衡因子bf+建構函式（左右為空，平衡因子初始化為0）

template<class K,class V>
struct AVLTreeNode
{
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;//balance factor
	AVLTreeNode(const pair<K,V>&kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}
};

三、AVL樹的插入

AVL樹在二元搜尋樹的基礎上引入了平衡因子，因此AVL樹也可以看成是二元搜尋樹。步驟過程：

找到插入的位置：根據二元搜尋樹的做法

進行插入：判斷插入的位置是parent的左還是右

更新平衡因子：如果不平衡的話，就要進行旋轉

找到插入位置（比較節點大小即可）：

插入的節點key值 > 當前位置的key值，往右子樹走
插入的節點key值 < 當前位置的key值，往左子樹走
插入的節點key值等於當前位置的key值，不能插入，返回false

插入之後，與二元搜尋樹不同的是：我們還需要去進行平衡因子的更新，調平衡：

如果新增加的在右，平衡因子加加

如果新增加的在左，平衡因子減減

更新一個結點之後我們需要去進行判斷，子樹的高度是否發生了變化：

1.如果parent的平衡因子是0：說明之前parent的平衡因子是1或-1，說明之前parent一邊高、一邊低；這次插入之後填入矮的那邊，parent所在的子樹高度不變，不需要繼續往上更新

2.如果parent的平衡因子是1或者-1：說明之前parent的平衡因子是0，兩邊一樣高，插入之後一邊更高，parent所在的子樹高度發生變化，繼續往上更新

3.平衡因子是2或-2，說明之前parent的平衡因子是1或-1，現在插入嚴重不平衡，違反規則，需要進行旋轉處理

最壞的情況下：需要一直更新到根root：

我們更新平衡因子時第一個更新的就是parent,如果parent->_bf1或parent->_bf-1需要繼續往上進行平衡因子的更新，向上迭代，直到parent為空的情況：

else if (parent->_bf == 1 || parent->_bf == -1)
{
    cur = parent;
    parent = parent->_parent;
}

當parent->_bf = 2或parent->_bf==-2時，我們就需要進行旋轉了：

C++ AVLTree高度平衡的二元搜尋樹深入分析

目錄

一、AVL樹的概念

二、AVL樹節點的定義

三、AVL樹的插入

熱門文章