C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(shù)(AVL樹(shù))實(shí)現(xiàn)方法示例
本文實(shí)例講述了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(shù)(AVL樹(shù))實(shí)現(xiàn)方法。分享給大家供大家參考,具體如下:
AVL樹(shù)是每個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度最多差1的二叉查找樹(shù)。
要維持這個(gè)樹(shù),必須在插入和刪除的時(shí)候都檢測(cè)是否出現(xiàn)破壞樹(shù)結(jié)構(gòu)的情況。然后立刻進(jìn)行調(diào)整。
看了好久,網(wǎng)上各種各種的AVL樹(shù),千奇百怪。
關(guān)鍵是要理解插入的時(shí)候旋轉(zhuǎn)的概念。
// // AvlTree.h // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 2017年 FableGame. All rights reserved. // #ifndef __HelloWorld__AvlTree__ #define __HelloWorld__AvlTree__ #include <iostream> namespace Fable { int max(int a, int b) { return a > b? a:b; } //二叉查找樹(shù),對(duì)于Comparable,必須實(shí)現(xiàn)了><=的比較 template<typename Comparable> class AvlTree { public: //構(gòu)造函數(shù) AvlTree(){} //復(fù)制構(gòu)造函數(shù) AvlTree(const AvlTree& rhs) { root = clone(rhs.root); } //析構(gòu)函數(shù) ~AvlTree() { makeEmpty(root); } //復(fù)制賦值運(yùn)算符 const AvlTree& operator=(const AvlTree& rhs) { if (this != &rhs) { makeEmpty(root);//先清除 root = clone(rhs.root);//再?gòu)?fù)制 } return *this; } //查找最小的對(duì)象 const Comparable& findMin()const { findMin(root); } //查找最大的對(duì)象 const Comparable& findMax()const { findMax(root); } //是否包含了某個(gè)對(duì)象 bool contains(const Comparable& x)const { return contains(x, root); } //樹(shù)為空 bool isEmpty()const { return root == nullptr; } //打印整棵樹(shù) void printTree()const { printTree(root); } //清空樹(shù) void makeEmpty() { makeEmpty(root); } //插入某個(gè)對(duì)象 void insert(const Comparable& x) { insert(x, root); } //移除某個(gè)對(duì)象 void remove(const Comparable& x) { remove(x, root); } private: struct AvlNode { Comparable element; AvlNode* left; AvlNode* right; int height; AvlNode(const Comparable& theElement, AvlNode* lt, AvlNode* rt, int h = 0) :element(theElement), left(lt), right(rt), height(h){} }; typedef AvlNode* AvlNodePtr; AvlNodePtr root;//根結(jié)點(diǎn) //順時(shí)針旋轉(zhuǎn) void clockwiseRotate(AvlNodePtr& a) { AvlNodePtr b = a->left;//左葉子 a->left = b->right;//a的左葉子變?yōu)閎的右葉子,b本來(lái)的子結(jié)點(diǎn)都比a小的。 b->right = a;//b的右結(jié)點(diǎn)指向a,b的高度上升了。 a->height = max(height(a->left), height(a->right)) + 1;//重新計(jì)算a的高度 b->height = max(height(b->left), a->height) + 1;//重新計(jì)算b的高度 a = b;//a的位置現(xiàn)在是b,當(dāng)前的根結(jié)點(diǎn) } //逆時(shí)針旋轉(zhuǎn) void antiClockWiseRotate(AvlNodePtr& a) { AvlNodePtr b = a->right;//右結(jié)點(diǎn) a->right = b->left;//a接收b的左結(jié)點(diǎn) b->left = a;//自己成為b的左結(jié)點(diǎn) a->height = max(height(a->left), height(a->right)) + 1;//計(jì)算高度 b->height = max(b->height, height(a->right)) + 1;//計(jì)算高度 a = b;//新的根結(jié)點(diǎn) } //對(duì)左邊結(jié)點(diǎn)的雙旋轉(zhuǎn) void doubleWithLeftChild(AvlNodePtr& k3) { antiClockWiseRotate(k3->left);//逆時(shí)針旋轉(zhuǎn)左結(jié)點(diǎn) clockwiseRotate(k3);//順時(shí)針旋轉(zhuǎn)自身 } //對(duì)右邊結(jié)點(diǎn)的雙旋轉(zhuǎn) void doubleWithRightChild(AvlNodePtr& k3) { clockwiseRotate(k3->right);//順時(shí)針旋轉(zhuǎn)有節(jié)點(diǎn) antiClockWiseRotate(k3);//逆時(shí)針旋轉(zhuǎn)自身 } //插入對(duì)象,這里使用了引用 void insert(const Comparable& x, AvlNodePtr& t) { if (!t) { t = new AvlNode(x, nullptr, nullptr); } else if (x < t->element) { insert(x, t->left);//比根結(jié)點(diǎn)小,插入左邊 if (height(t->left) - height(t->right) == 2)//高度差達(dá)到2了 { if (x < t->left->element)//插入左邊 { clockwiseRotate(t);//順時(shí)針旋轉(zhuǎn) } else { doubleWithLeftChild(t);//雙旋轉(zhuǎn) } } } else if (x > t->element) { insert(x, t->right);//比根結(jié)點(diǎn)大,插入右邊 if (height(t->right) - height(t->left) == 2)//高度差達(dá)到2 { if (t->right->element < x)//插入右邊 { antiClockWiseRotate(t);//旋轉(zhuǎn) } else { doubleWithRightChild(t);//雙旋轉(zhuǎn) } } } else { //相同的 } t->height = max(height(t->left), height(t->right)) + 1;//計(jì)算結(jié)點(diǎn)的高度 } void removeMin(AvlNodePtr& x, AvlNodePtr& t)const { if (!t) { return;//找不到 } if (t->left) { removeMin(t->left);//使用了遞歸的方式 } else { //找到最小的結(jié)點(diǎn)了 x->element = t->element; AvlNodePtr oldNode = t; t = t->right; delete oldNode;//刪除原來(lái)要?jiǎng)h除的結(jié)點(diǎn) } if (t) { t->height = max(height(t->left), height(t->right)) + 1;//計(jì)算結(jié)點(diǎn)的高度 if(height(t->left) - height(t->right) == 2) { //如果左兒子高度大于右兒子高度 if(height(t->left->left) >= height(t->left->right))//并且左兒子的左子樹(shù)高度大于左兒子的右子樹(shù)高度 { clockwiseRotate(t); //順時(shí)針旋轉(zhuǎn) } else { doubleWithLeftChild(t);//雙旋轉(zhuǎn)左子樹(shù) } } else { if(height(t->right->right) - height(t->right->left) == 2) //如果右子樹(shù)大于左子樹(shù) { antiClockWiseRotate(t);//逆時(shí)針旋轉(zhuǎn) } else { doubleWithRright(t);//雙旋轉(zhuǎn)右子樹(shù) } } } } //刪除某個(gè)對(duì)象,這里必須要引用 void remove(const Comparable& x, AvlNodePtr& t)const { if (!t) { return;//樹(shù)為空 } else if (x < t->element) { remove(x, t->left);//比根結(jié)點(diǎn)小,去左邊查找 } else if (x > t->element) { remove(x, t->right);//比根結(jié)點(diǎn)大,去右邊查找 } else if (!t->left && !t->right)//找到結(jié)點(diǎn)了,有兩個(gè)葉子 { removeMin(t, t->right);//這里選擇的方法是刪除右子樹(shù)的最小的結(jié)點(diǎn) } else { AvlNodePtr oldNode = t; t = (t->left) ? t->left : t->right;//走到這里,t最多只有一個(gè)葉子,將t指向這個(gè)葉子 delete oldNode;//刪除原來(lái)要?jiǎng)h除的結(jié)點(diǎn) } if (t) { t->height = max(height(t->left), height(t->right)) + 1;//計(jì)算結(jié)點(diǎn)的高度 if(height(t->left) - height(t->right) == 2) { //如果左兒子高度大于右兒子高度 if(height(t->left->left) >= height(t->left->right))//并且左兒子的左子樹(shù)高度大于左兒子的右子樹(shù)高度 { clockwiseRotate(t); //順時(shí)針旋轉(zhuǎn) } else { doubleWithLeftChild(t);//雙旋轉(zhuǎn)左子樹(shù) } } else { if(height(t->right->right) - height(t->right->left) == 2) //如果右子樹(shù)大于左子樹(shù) { antiClockWiseRotate(t);//逆時(shí)針旋轉(zhuǎn) } else { doubleWithRright(t);//雙旋轉(zhuǎn)右子樹(shù) } } } } //左邊子樹(shù)的結(jié)點(diǎn)肯定比當(dāng)前根小的,所以一直往左邊尋找 AvlNodePtr findMin(AvlNodePtr t)const { if (!t) { return nullptr;//找不到 } if (!t->left) { return t; } return findMin(t->left);//使用了遞歸的方式 } //右邊子樹(shù)的結(jié)點(diǎn)肯定比當(dāng)前根大,所以一直往右邊找 AvlNodePtr findMax(AvlNodePtr t)const { if (t) { while (t->right)//使用了循環(huán)的方式 { t = t->right; } } return t; } //判斷是否包含某個(gè)對(duì)象,因?yàn)橐褂眠f歸,所以還有一個(gè)public版本的 bool contains(const Comparable& x, AvlNodePtr t)const { if (!t) { return false;//空結(jié)點(diǎn)了 } else if (x < t->element) { //根據(jù)二叉樹(shù)的定義,比某個(gè)結(jié)點(diǎn)小的對(duì)象,肯定只能存在與這個(gè)結(jié)點(diǎn)的左邊的子樹(shù) return contains(x, t->left); } else if (x > t->element) { //根據(jù)二叉樹(shù)的定義,比某個(gè)結(jié)點(diǎn)大的對(duì)象,肯定只能存在與這個(gè)結(jié)點(diǎn)的右邊的子樹(shù) return contains(x, t->right); } else { //相等,就是找到啦。 return true; } } //清空子樹(shù) void makeEmpty(AvlNodePtr& t) { if (t) { makeEmpty(t->left);//清空左邊 makeEmpty(t->right);//清空右邊 delete t;//釋放自身 } t = nullptr;//置為空 } //打印子樹(shù),這里沒(méi)有使用復(fù)雜的排位,純屬打印 void printTree(AvlNodePtr t)const { if (!t) { return; } std::cout << t->element << std::endl;//輸出自身的對(duì)象 printTree(t->left);//打印左子樹(shù) printTree(t->right);//打印右子樹(shù) } AvlNodePtr clone(AvlNodePtr t)const { if (!t) { return nullptr; } return new AvlNode(t->element, clone(t->left), clone(t->right)); } int height(AvlNodePtr t)const { return t == nullptr ? -1 : t->height; } }; } #endif
簡(jiǎn)單測(cè)試一下。
// // AvlTree.cpp // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 2017年 FableGame. All rights reserved. // #include "AvlTree.h" using namespace Fable; int main(int argc, char* argv[]) { AvlTree<int> a; for(int i = 0; i < 100; ++i) { a.insert(i); } return 0; }
這個(gè)刪除的方法完全是自己寫的,可能不是很高效。
希望本文所述對(duì)大家C語(yǔ)言程序設(shè)計(jì)有所幫助。
- 數(shù)據(jù)結(jié)構(gòu)之AVL樹(shù)詳解
- C++實(shí)現(xiàn)AVL樹(shù)的完整代碼
- 圖解AVL樹(shù)數(shù)據(jù)結(jié)構(gòu)輸入與輸出及實(shí)現(xiàn)示例
- 圖解紅黑樹(shù)及Java進(jìn)行紅黑二叉樹(shù)遍歷的方法
- java算法實(shí)現(xiàn)紅黑樹(shù)完整代碼示例
- C語(yǔ)言實(shí)現(xiàn)紅黑樹(shù)的實(shí)例代碼
- 紅黑樹(shù)的使用詳解
- Linux內(nèi)核中紅黑樹(shù)算法的實(shí)現(xiàn)詳解
- python代碼實(shí)現(xiàn)AVL樹(shù)和紅黑樹(shù)
相關(guān)文章
C語(yǔ)言實(shí)現(xiàn)班級(jí)檔案管理系統(tǒng)課程設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)班級(jí)檔案管理系統(tǒng)課程設(shè)計(jì),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-12-12C++ Primer中&、*符號(hào)的多重定義與int *p和int* p的區(qū)別講解
今天小編就為大家分享一篇關(guān)于C++Primer中&、*符號(hào)的多重定義與int *p和int* p的區(qū)別講解,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧2019-04-04Prim(普里姆)算法求最小生成樹(shù)的思想及C語(yǔ)言實(shí)例講解
Prim算法能夠在帶權(quán)的圖中搜索出最小生成樹(shù),這也是各大ACM和面試及考研題目中的熱點(diǎn),下面我們就來(lái)詳細(xì)看一下Prim(普里姆)算法求最小生成樹(shù)的思想及C語(yǔ)言實(shí)例講解2016-06-06C語(yǔ)言實(shí)現(xiàn)掃雷經(jīng)典游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)掃雷經(jīng)典游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-07-07C語(yǔ)言實(shí)現(xiàn)隨機(jī)抽取紙牌程序
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)隨機(jī)抽取紙牌程序,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-03-03