C++?AVL樹概念與實現(xiàn)詳解

更新時間：2026年05月05日 11:04:55 作者：進擊的荊棘

這篇文章主要介紹了C++?AVL樹概念與實現(xiàn),文章帶你深入平衡二叉樹原理,掌握旋轉(zhuǎn)平衡機制,從零實現(xiàn)?AVL?樹,理解?C++?高效數(shù)據(jù)結(jié)構(gòu)的設(shè)計與核心思想,需要的朋友可以參考下

1.AVL的概念

●AVL樹是最先發(fā)明的自平衡二叉查找樹，AVL是一顆空樹，或具備下列性質(zhì)的二叉搜索樹：它的左右子樹都是AVL樹，且左右子樹的高度差的絕對值不超過1。AVL樹是一顆高度平衡搜索二叉樹，通過控制高度差去控制平衡。

●AVL樹得名于它的發(fā)明者G.M.Adelson-Velsky和E.M.Landis，他們在1962年的論文《An algorithm for the organization of information》中發(fā)表了它。

●AVL樹實現(xiàn)這里我們引入一個平衡因子（balance facor）的概念，每個節(jié)點都有一個平衡因子，任何節(jié)點的平衡因子等于右子樹的高度減去左子樹的高度，也就是說任何節(jié)點的平衡因子等于0/1/-1，AVL樹并不是必須要平衡因子，但是有了平衡因子可以更方便我們?nèi)ミM行觀察和控制樹是否平衡，就像一個風(fēng)向標(biāo)一樣。

●為什么AVL樹是高度平衡搜索二叉樹，要求高度差不超過1，而不是高度差是0呢？0不是更好的平衡嗎？通過畫圖我們可以發(fā)現(xiàn)，不是不想這樣設(shè)計，而是有些情況無法做到高度差為0。如：一棵樹是2個節(jié)點，4個節(jié)點等情況下，高度差最好就是1，無法做到高度差是0.

●AVL樹整體節(jié)點數(shù)量和分布和完全二叉樹類似，高度可以控制在logN，那么增刪查改的效率也可以控制在O（logN），相比二叉搜索樹有了本質(zhì)的提升。

2.AVL樹的實現(xiàn)

2.1AVL樹的結(jié)構(gòu)

template<class k,class v>
struct AVLTreeNode{
    //需要parent指針，后續(xù)更新平衡因子需要
    pair<k,v> _kv;
    AVLTreeNode<k,v>* _left;
    AVLTreeNode<k,v>* _right;
    AVLTreeNode<k,v>* _parent;
    int _bf;//平衡因子
    AVLTreeNode(const pair<k,v>& kv)
        :_kv(kv)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_bf(0)
    {}
};
template<class k,class v>
class AVLTree{
    typedef AVLTreeNode<k,v> Node;
public:
private:
    Node* _root=nullptr;
};

2.2AVL樹的插入

2.2.1AVL樹插入一個值的大概過程

1.插入一個值按二叉搜索樹規(guī)則進行插入。

2.新增節(jié)點后，只會影響祖先節(jié)點的高度，也就是可能會影響部分祖先節(jié)點的平衡因子，所以更新從新增節(jié)點->根節(jié)點路徑上的平衡因子，實際中最壞情況下要更新到根，有些情況更新到中間就可以停止了。

3.更新平衡因子過程中沒有出現(xiàn)問題，則插入結(jié)束。

4.更新平衡因子過程中出現(xiàn)不平衡，對不平衡子樹旋轉(zhuǎn)，旋轉(zhuǎn)后本質(zhì)調(diào)平衡的同時，本質(zhì)降低了子樹的高度，不會再影響上一層，所以插入結(jié)束。

2.2.2平衡因子更新

更新原則：

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

●只有子樹高度變化才會影響當(dāng)前節(jié)點平衡因子

●插入節(jié)點，會增加高度，所以新增節(jié)點再parent的右子樹，parent的平衡因子++，新增節(jié)點在parent的左子樹，parent平衡因子--

●parent所在子樹的高度是否變化決定了是否會繼續(xù)往上更新

更新停止條件：

●更新后parent的平衡因子等于0，更新中parent的平衡因子變化為-1->0，說明更新前parent子樹一邊高一邊低，新增的節(jié)點插入在低的那邊，插入后parent所在的子樹高度不變，不會影響parent的父親節(jié)點的平衡因子，更新結(jié)束。

●更新后parent的平衡因子等于1或-1，更新前更新中parent的平衡因子變化為0->1或0->-1，說明更新前parent子樹兩邊一樣高，新增的插入節(jié)點后，parent所在的子樹一邊高一邊低，parent所在的子樹符合平衡要求，但是高度增加了1，會影響parent的父親節(jié)點的平衡因子，所以要繼續(xù)向上更新。

●更新后parent的平衡因子等于2或-2，更新前更新中parent的平衡因子變化為1->2或-1->-2，說明更新前parent子樹一邊高一邊低，新增的插入節(jié)點在高的那邊，parent所在的子樹高的那邊更高了，破壞了平衡，parent所在的子樹不符合平衡要求，需要旋轉(zhuǎn)處理，旋轉(zhuǎn)的目標(biāo)有兩個：1、把parent子樹旋轉(zhuǎn)平衡。2、降低parent子樹的高度，恢復(fù)到插入節(jié)點以前的高度。所以旋轉(zhuǎn)后也不需要繼續(xù)向上更新，插入結(jié)束。

●不斷更新，更新到根，根的平衡因子是1或-1也停止了。

更新到10節(jié)點，平衡因子為2，10所在的子樹已經(jīng)不平衡，需要旋轉(zhuǎn)處理

更新到中間節(jié)點，3為根的子樹高度不變，不會影響上一層，更新結(jié)束

最壞更新到根停止

2.2.3插入節(jié)點更新平衡因子的代碼實現(xiàn)

bool Insert(const pair<k,v>& kv){
        if(!_root){
            _root=new Node(kv);
            return true;
        }
        Node* parent=nullptr;
        Node* cur=_root;
        while(cur){
            if(cur->_kv.first<kv.first){
                parent=cur;
                cur=cur->_right;
            }
            else if(cur->_kv.first>kv.first){
                parent=cur;
                cur=cur->_left;
            }
            else return false;
        }
        //開始插入
        cur=new Node(kv);
        if(cur->_kv.first<parent->_kv.first)
            parent->_left=cur;
        else parent->_right=cur;
        //父指針指向父節(jié)點
        cur->_parent=parent;
        //控制平衡
        while(parent){
            //當(dāng)節(jié)點插入左邊時，父節(jié)點平衡因子--
            if(cur==parent->_left)
                parent->_bf--;
            //當(dāng)節(jié)點插入右邊時，父節(jié)點平衡因子++
            else parent->_bf++;
            //查看樹是否依舊平衡
            if(parent->_bf==0){
                //說明父節(jié)點之前是1或-1，插入新節(jié)點后，樹可能不平衡
                break;
            }
            else if(parent->_bf==1||parent->_bf==-1){
                cur=parent;
                parent=cur->_parent;
            }
            else if(parent->_bf==2||parent->_bf==-2){
                //不平衡，旋轉(zhuǎn)
                break;
            }
            //防止樹一開始就不平衡
            else assert(false);
        }
        return true;
    }

2.3旋轉(zhuǎn)

2.3.1旋轉(zhuǎn)的原則

1.保持搜索樹的規(guī)則

2.讓旋轉(zhuǎn)的樹從不滿足并平衡，其次降低旋轉(zhuǎn)樹的高度

旋轉(zhuǎn)總共分為四種，左單選/右單旋/左右雙旋/右左雙旋。

2.3.2右單旋

●圖1展示的是10為根的樹，有a/b/c抽象為三顆高度為h的子樹（h>=0），a/b/c均符合AVL樹的要求。10可能是整棵樹的根，也可能是一整棵樹中局部的子樹的根。這里a/b/c是高度為h的子樹，是一種概括抽象表示，它代表了所有右單旋的場景，實際右單旋形態(tài)有很多種，圖2/圖3/圖4/圖5進行詳細描述。

●在a子樹中插入一個新節(jié)點，導(dǎo)致a子樹的高度從h變成h+1，不斷向上更新平衡因子，導(dǎo)致10的平衡因子從-1變成-2，10為根的樹左右高度差超過1，違反平衡規(guī)則。10為根的樹左邊太高了，需要往右邊旋轉(zhuǎn)，控制兩棵樹的平衡。

●旋轉(zhuǎn)核心步驟，因為5<b子樹的值<10，將b變成10的左子樹，10變成5的右子樹，5變成這棵樹新的根，符合搜索樹的規(guī)則，控制了平衡，同時這棵樹的高度恢復(fù)到了插入之前的h+2，符合旋轉(zhuǎn)原則。若插入之前10整棵樹的局部子樹，旋轉(zhuǎn)后不會再影響上一層，插入結(jié)束。

2.3.3右單旋代碼實現(xiàn)

void RotateR(Node* parent){
        Node* subL=parent->_left;
        Node* subLR=subL->_right;
        parent->_left=subLR;
        //鏈接父節(jié)點
        if(subLR)
            subLR->_parent=parent;
        //防止找不到父結(jié)點的父結(jié)點
        Node* pparent=parent->_parent;
        subL->_right=parent;
        parent->_parent=subL;
        if(parent==_root){
            _root=subL;
            subL->_parent=nullptr;
        }
        else{
            if(pparent->_left==parent)
                pparent->_left=subL;
            else pparent->_right=subL;
            subL->_parent=pparent;
        }
        //更新平衡因子
        parent->_bf=0;
        subL->_bf=0;
    }

2.3.4左單旋

●圖6展示的是10為根的樹，有a/b/c抽象為三棵高度為h的子樹（h>=0），a/b/c均符合AVL樹的要求。10可能是整棵樹的根，也可能是一整棵樹中局部的子樹的根。這里a/b/c是高度為h的子樹，是一種概括抽象表示，它代表了所有右單旋的場景，實際右單旋形態(tài)有很多種，具體跟上面左旋類似。

●在a子樹中插入一個新節(jié)點，導(dǎo)致a子樹的高度從h變成h+1，不斷向上跟新平衡因子，導(dǎo)致10的平衡因子從1變成2，10為跟的樹左右高度差超過1，違反平衡規(guī)則。10為跟的樹右邊太高了，需要往左邊旋轉(zhuǎn)，控制兩棵樹的平衡。

●旋轉(zhuǎn)核心步驟，因為10<b子樹的值<15，將b變成10的右子樹，10變成15的左子樹，15變成這棵樹新的根，符合搜索樹的規(guī)則，控制了平衡，同時這顆的高度恢復(fù)到了插入之前的h+2，符合旋轉(zhuǎn)原則。若插入之前10整棵樹的一個局部子樹，旋轉(zhuǎn)后不會再影響上一層，插入結(jié)束。

2.3.5左單旋的實現(xiàn)

void RotateL(Node* parent){
        Node* subR=parent->_right;
        Node* subRL=subR->_left;
        parent->_right=subRL;
        //鏈接父節(jié)點
        if(subRL)
            subRL->_parent=parent;
        //防止找不到父結(jié)點的父結(jié)點
        Node* pparent=parent->_parent;
        subR->_left=parent;
        parent->_parent=subR;
        if(pparent==nullptr){
            _root=subR;
            subR->_parent=nullptr;
        }
        else{
            if(parent==pparent->_left)
                pparent->_left=subR;
            else pparent->_right=subR;
            subR->_parent=pparent;
        }
        //更新平衡因子
        parent->_bf=subR->_bf=0;
    }

2.3.6左右雙旋

通過圖7和圖8可以看到，左邊高時，若插入位置不是在a子樹，而是插入在b子樹，b子樹高度從h變成h+1，引發(fā)旋轉(zhuǎn)，右單旋無法解決問題，右單旋后，我們的樹依舊不平衡。右單旋解決的是存粹的左邊高，需要用兩次旋轉(zhuǎn)才能解決，以5為旋轉(zhuǎn)點進行一個左單旋，以10為旋轉(zhuǎn)點進行一個右單旋，這棵樹就平衡了。

●圖7和圖8分別為左右雙旋中h==0和h==1具體場景分析，下面將a/b/c子樹抽象為高度h的AVL子樹進行分析，另外把b子樹的細節(jié)進一步展開為8和左子樹高度為h-1的e和f子樹，因為我們要對b的父親5為旋轉(zhuǎn)點進行左單旋，左單旋需要動b樹中的左子樹。b子樹中新增節(jié)點的位置不同，平衡因子更新的細節(jié)也不同，通過觀察8的平衡因子不同，這里可以分3個場景討論。

●場景1：h>=1時，新增節(jié)點插入在e子樹，e子樹高度從h-1并為h并不斷更新8->5->10平衡因子，引發(fā)旋轉(zhuǎn)，其中8的平衡因子為-1，旋轉(zhuǎn)后8和5平衡因子為0，10平衡因子為1。

●場景2：h>=1時，新增節(jié)點插入在f子樹，f子樹高度從h-1變?yōu)閔并不斷更新8->5->10平衡因子，引發(fā)旋轉(zhuǎn)，其中8的平衡因子為1，旋轉(zhuǎn)后8和10平衡因子為0，5平衡因子為-1.

●場景3：h==0，a/b/c都是空樹，b自己就是一個新增節(jié)點，不斷更新5->10平衡因子，引發(fā)旋轉(zhuǎn)，其中8的平衡因子為0，旋轉(zhuǎn)后8和10和5平衡因子均為0。

2.3.7左右雙旋代碼實現(xiàn)

oid RotateLR(Node* parent){
        Node* subL=parent->_left;
        Node* subLR=subL->_right;
        int bf=subLR->_bf;
        RotateL(parent->_left);
        RotateR(parent);
        if(bf==0){//更新平衡因子
            subL->_bf=0;
            subLR->_bf=0;
            parent->_bf=0;
        }
        else if(bf==-1){
            subL->_bf=0;
            subLR->_bf=0;
            parent->_bf=1;
        }
        else if(bf==1){
            subL->_bf=-1;
            subLR->_bf=0;
            parent->_bf=0;
        }
        else {
            assert(false);
        }
    }

2.3.8右左雙旋

●跟左右雙旋類似，下面將a/b/c子樹抽象為高度h的AVL子樹進行分析，另外需要把b子樹的細節(jié)進一步展開為12和左子樹高度為h-1的e和f子樹，因為我們要對b的父親15為旋轉(zhuǎn)點進行右單旋，右單旋需要動b樹中的右子樹。b子樹中新增節(jié)點的位置不同，平衡因子更新的細節(jié)也不同，通過觀察12的平衡因子不同，這里可以分三個場景討論。

●場景1：h>=1時，新增節(jié)點插入在e子樹，e子樹高度從h-1變?yōu)閔并不斷更新12->15->10平衡因子，引發(fā)旋轉(zhuǎn)，其中12的平衡因子為-1，旋轉(zhuǎn)后10和12平衡因子為0，15平衡因子為1.

●場景2：h>=1時，新增節(jié)點插入在f子樹，f子樹高度從h-1變?yōu)閔并不斷更新12->15->10平衡因子，引發(fā)旋轉(zhuǎn)，其中12的平衡因子為1，旋轉(zhuǎn)后15和12平衡因子為0，10平衡因子為-1。

●場景3：h==0時，a/b/c都是空樹，b自己就是一個新增節(jié)點，不斷更新15->10平衡因子，引發(fā)旋轉(zhuǎn)，其中12的平衡因子為0，旋轉(zhuǎn)后10和12和15平衡因子均為0.

2.3.9右左雙旋代碼實現(xiàn)

void RotateRL(Node* parent){
        Node* subR=parent->_right;
        Node* subRL=subR->_left;
        int bf=subRL->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        if(bf==0){//更新平衡因子
            subR->_bf=0;
            subRL->_bf=0;
            parent->_bf=0;
        }
        else if(bf==-1){
            subR->_bf=1;
            subRL->_bf=0;
            parent->_bf=0;
        }
        else if(bf==1){
            subR->_bf=0;
            subRL->_bf=0;
            parent->_bf=-1;
        }
        else {
            assert(false);
        }
    }

2.4AVL樹的查找

拿二叉搜索樹的邏輯就可以實現(xiàn)，搜索效率為O（logN）

Node* Find(const k& key){
        Node* cur=_root;
        while(cur){
            if(cur->_kv.first<key){
                cur=cur->_right;
            }
            else if(cur->_kv.first>key){
                cur=cur->_left;
            }
            else return cur;
        }
        return nullptr;
    }

2.5AVL樹平衡檢查

實現(xiàn)的AVL樹是否合格，可以通過檢查左右子樹高度差的程度進行反向驗證，同時檢查節(jié)點的平衡因子更新是否出現(xiàn)問題。

int _Height(Node* root){
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
bool _IsBalanceTree(Node* root){
		// 空樹也是AVL樹
		if (nullptr == root)
			return true;
		// 計算pRoot結(jié)點的平衡因子：即pRoot左右子樹的高度差
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
		// 如果計算出的平衡因子與pRoot的平衡因子不相等，或者
		// pRoot平衡因子的絕對值超過1，則一定不是AVL樹
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "高度差異常" << endl;
			return false;
		}
		if (root->_bf != diff)
		{
			cout << root->_kv.first << "平衡因子異常" << endl;
			return false;
		}
		// pRoot的左和右如果都是AVL樹，則該樹一定是AVL樹
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
	}
void TestAVLTree1(){
	AVLTree<int, int> t;
	// 常規(guī)的測試用例
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的帶有雙旋場景的測試用例
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert({ e, e });
	}
	t.InOrder();
	cout << t.IsBalanceTree() << endl;
}
void TestAVLTree2(){
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalanceTree() << endl;
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;
	size_t begin1 = clock();
	// 確定在的值
	for (auto e : v)
	{
		t.Find(e);
	}
	// 隨機值
	/*for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}*/
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}

以上就是C++ AVL樹概念與實現(xiàn)詳解的詳細內(nèi)容，更多關(guān)于C++ AVL樹的實現(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: