怎样创造一个网站,网站搜索怎么做php,腾讯网页游戏排行榜,服务营销论文文章目录 一、AVL树的概念二、AVL树的实现1. AVL树的结构2. AVL树的插⼊2.1 AVL树插⼊⼀个值的⼤概过程2.2 平衡因⼦更新更新原则更新停止条件 2.3 插⼊结点及更新平衡因⼦的代码实现 3. 旋转旋转的原则右单旋左单旋左右双旋右左双旋 4.高度5.结点个数6.判断是否是AVL树7. 中序… 文章目录 一、AVL树的概念二、AVL树的实现1. AVL树的结构2. AVL树的插⼊2.1 AVL树插⼊⼀个值的⼤概过程2.2 平衡因⼦更新更新原则更新停止条件 2.3 插⼊结点及更新平衡因⼦的代码实现 3. 旋转旋转的原则右单旋左单旋左右双旋右左双旋 4.高度5.结点个数6.判断是否是AVL树7. 中序遍历8.查找 三、源代码AVL.htest.cpp 一、AVL树的概念 AVL树是最先发明的自平衡⼆叉查找树AVL是⼀颗空树或者具备下列性质的⼆叉搜索树 它的左右子树都是AV树且左右子树的高度差的绝对值不超过1。 AVL树是⼀颗高度平衡搜索⼆叉树 通过控制高度差去控制平衡。
AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家他们在1962年的论文《An algorithm for the organization of information》中发表了它。 AVL树实现这里我们引入⼀个平衡因子(balance factor)的概念每个结点都有⼀个平衡因子任何 结点的平衡因子等于右子树的高度减去左子树的高度也就是说任何结点的平衡因子等于0/1/-1 AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡 就像⼀个风向标⼀样。 思考⼀下为什么AVL树是高度平衡搜索⼆叉树要求高度差不超过1而不是高度差是0呢0不是更好的平衡吗画画图分析我们发现不是不想这样设计而是有些情况是做不到高度差是0的。⽐如⼀棵树是2个结点4个结点等情况下高度差最好就是1无法作为高度差是0。AVL树整体结点数量和分布和完全⼆叉树类似⾼度可以控制在logN 那么增删查改的效率也可 以控制在O(logN) 相⽐⼆叉搜索树有了本质的提升。 二、AVL树的实现
1. AVL树的结构
#pragma once
#includeiostream
using namespace std;
templateclass K, class V
struct AVLTreeNode
{// 需要parent指针后续更新平衡因子可以看到pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factorAVLTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:
private:Node * _root nullptr;
};2. AVL树的插⼊
2.1 AVL树插⼊⼀个值的⼤概过程
插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。新增结点以后只会影响祖先结点的⾼度也就是可能会影响部分祖先结点的平衡因⼦所以更新从新增结点-根结点路径上的平衡因⼦实际中最坏情况下要更新到根有些情况更新到中间就可以停⽌了具体情况我们下⾯再详细分析。更新平衡因⼦过程中没有出现问题则插⼊结束。更新平衡因⼦过程中出现不平衡对不平衡⼦树旋转旋转后本质调平衡的同时本质降低了⼦树的⾼度不会再影响上⼀层所以插⼊结束。
2.2 平衡因⼦更新
更新原则
平衡因子 右子树高度-左子树高度只有子树高度变化才会影响当前结点平衡因子插入结点会增加高度所以新增结点在parent的右子树parent的平衡因子新增结点在 parent的左子树parent平衡因子 - -parent所在子树的高度是否变化决定了是否会继续往上更新
更新停止条件
更新后parent的平衡因子等于0更新中parent的平衡因子变化为-1-0 或者 1-0说明更新前 parent子树⼀边高⼀边低新增的结点插入在低的那边插入后parent所在的子树高度不变不会影响parent的父亲结点的平衡因子更新结束。更新后parent的平衡因子等于1 或 -1更新前更新中parent的平衡因子变化为0-1 或者 0--1说明更新前parent子树两边⼀样高新增的插入结点后parent所在的子树⼀边高⼀边低parent所在的子树符合平衡要求但是高度增加了1会影响parent的父亲结点的平衡因子所以要继续向上 更新。更新后parent的平衡因子等于2 或 -2更新前更新中parent的平衡因子变化为1-2 或者 -1--2说明更新前parent子树⼀边高⼀边低新增的插入结点在高的那边parent所在的子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的⽬标有两个1、把parent子树旋转平衡。2、降低parent子树的高度恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新插入结束。
更新到10结点平衡因子为210所在的子树已经不平衡需要旋转处理 更新到中间结点3为根的子树高度不变不会影响上⼀层更新结束 最坏更新到根停⽌
2.3 插⼊结点及更新平衡因⼦的代码实现
bool Insert(const pairK, V kv)
{if (_root nullptr){_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 (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent){if (parent-_left cur){parent-_bf--;}else{parent-_bf;}if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){//继续向上更新cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//旋转//右单旋if (parent-_bf -2 cur-_bf -1){RotateR(parent);}//左单旋else if (parent-_bf 2 cur-_bf 1){RotateL(parent);}else if (parent-_bf -2 cur-_bf 1){//左右旋RotateLR(parent);}else if (parent-_bf 2 cur-_bf -1){//右左旋RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;
}3. 旋转
旋转的原则
保持搜索树的规则让旋转的树从不满⾜变平衡其次降低旋转树的⾼度
旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋
右单旋
本图1展⽰的是10为根的树有a/b/c抽象为三棵高度为h的子树(h0)a/b/c均符合AVL树的要求。10可能是整棵树的根也可能是⼀个整棵树中局部的子树的根。这里a/b/c是高度为h的子树 是⼀种概括抽象表示他代表了所有右单旋的场景实际右单旋形态有很多种具体图2/图3/图4/ 图5进行了详细描述。在a子树中插入⼀个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平 衡因子从-1变成-210为根的树左右高度差超过1违反平衡规则。10为根的树左边太高了需要 往右边旋转控制两棵树的平衡。旋转核心步骤因为5 b子树的值 10将b变成10的左子树10变成5的右子树5变成这棵树新的根符合搜索树的规则控制了平衡同时这棵的高度恢复到了插入之前的h2符合旋转原 则。如果插入之前10整棵树的⼀个局部子树旋转后不会再影响上⼀层插入结束了。 //右旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;Node* Pparent parent-_parent;if (subLR){subLR-_parent parent;}subL-_right parent;parent-_parent subL;parent-_left subLR;if (Pparent nullptr){_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;}左单旋
本图6展示的是10为根的树有a/b/c抽象为三棵高度为h的子树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的子树的根。这里a/b/c是高度为h的子树 是⼀种概括抽象表示他代表了所有右单旋的场景实际右单旋形态有很多种具体跟上⾯左旋类似。在a子树中插入⼀个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平 衡因子从1变成210为根的树左右高度差超过1违反平衡规则。10为根的树右边太高了需要往 左边旋转控制两棵树的平衡。旋转核心步骤因为10 b子树的值 15将b变成10的右子树10变成15的左子树15变成这棵树新的根符合搜索树的规则控制了平衡同时这棵的高度恢复到了插入之前的h2符合旋转原则。如果插入之前10整棵树的⼀个局部子树旋转后不会再影响上⼀层插入结束了。 //左旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;Node* Pparent parent-_parent;if (subRL){subRL-_parent parent;}subR-_left parent;parent-_parent subR;parent-_right subRL;if (Pparent nullptr){_root subR;subR-_parent nullptr;}else{if (Pparent-_left parent){Pparent-_left subR;}else{Pparent-_right subR;}subR-_parent Pparent;}parent-_bf 0;subR-_bf 0;
}左右双旋
通过图7和图8可以看到左边高时如果插入位置不是在a子树而是插入在b子树b子树高度从h变成h1引发旋转右单旋无法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯粹的左边高但是插入在b子树中10为跟的子树不再是单纯的左边高对于10是左边高但是对于5是右边高需要用两次旋转才能解决以5为旋转点进行⼀个左单旋以10为旋转点进行⼀个右单旋这棵树这棵树就平衡了。 图7和图8分别为左右双旋中h0和h1具体场景分析下面我们将a/b/c子树抽象为高度h的AVL子树进行分析另外我们需要把b子树的细节进⼀步展开为8和左子树高度为h-1的e和f子树因为我们要对b的父亲5为旋转点进行左单旋左单旋需要动b树中的左子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察8的平衡因子不同这里我们要分三个场景讨论。
场景1h 1时新增结点插⼊在e子树e子树高度从h-1变为h并不断更新8-5-10平衡因子引发旋转其中8的平衡因子为-1旋转后8和5平衡因子为010平衡因子为1。场景2h 1时新增结点插⼊在f子树f子树高度从h-1变为h并不断更新8-5-10平衡因子引发旋转其中8的平衡因子为1旋转后8和10平衡因子为05平衡因子为-1。场景3h 0时a/b/c都是空树b⾃⼰就是⼀个新增结点不断更新5-10平衡因子引发旋转其中8的平衡因子为0旋转后8和10和5平衡因子均为0。
//左右旋
void RotateLR(Node* parent)
{//subL subLR parentNode* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(subL);RotateR(parent);if (bf 0){subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else if (bf 1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else if (bf -1){subL-_bf 0;subLR-_bf 0;parent-_bf 1;}else{assert(false);}
}右左双旋
跟左右双旋类似下⾯我们将a/b/c子树抽象为⾼度h的AVL子树进⾏分析另外我们需要把b子树的细节进⼀步展开为12和左子树⾼度为h-1的e和f子树因为我们要对b的⽗亲15为旋转点进⾏右单旋右单旋需要动b树中的右子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察12的平衡因子不同这⾥我们要分三个场景讨论。
场景1h 1时新增结点插⼊在e子树e子树⾼度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为-1旋转后10和12平衡因子为015平衡因子为1。场景2h 1时新增结点插⼊在f子树f子树⾼度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为1旋转后15和12平衡因子为010平衡因子为-1。场景3h 0时a/b/c都是空树b自己就是⼀个新增结点不断更新15-10平衡因子引发旋转其中12的平衡因子为0旋转后10和12和15平衡因子均为0。 //右左旋
void RotateRL(Node* parent)
{//parent subRL subRNode* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);if (bf 0){subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else if (bf 1){subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else{assert(false);}
}
4.高度
//高度
int _Height(Node* root)
{if (root nullptr){return 0;}int left _Height(root-_left);int right _Height(root-_right);return left right ? left 1 : right 1;
}5.结点个数
//结点个数
int _Size(Node* root)
{if (root nullptr){return 0;}return _Size(root-_left) _Size(root-_right) 1;
}6.判断是否是AVL树
//判断
bool _IsBalanceTree(Node* root)
{//空树也是AVL树if (root nullptr){return true;}int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);int diff rightHeight - leftHeight;if (abs(diff) 2){cout root-_kv.first 高度差异常 endl;return false;}if (root-_bf ! diff){cout root-_kv.first 平衡因子异常 endl;return false;}return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);
}7. 中序遍历
//中序遍历
void _InOrder(Node* root)
{if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);
}8.查找
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;
}三、源代码
AVL.h
#pragma once
#include iostream
#include assert.h
using namespace std;templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK,V* _left;AVLTreeNodeK,V* _right;AVLTreeNodeK,V* _parent;pairK,V _kv;int _bf;//节点的平衡因子AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){if (_root nullptr){_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 (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent){if (parent-_left cur){parent-_bf--;}else{parent-_bf;}if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){//继续向上更新cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//旋转//右单旋if (parent-_bf -2 cur-_bf -1){RotateR(parent);}//左单旋else if (parent-_bf 2 cur-_bf 1){RotateL(parent);}else if (parent-_bf -2 cur-_bf 1){//左右旋RotateLR(parent);}else if (parent-_bf 2 cur-_bf -1){//右左旋RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}//右旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;Node* Pparent parent-_parent;if (subLR){subLR-_parent parent;}subL-_right parent;parent-_parent subL;parent-_left subLR;if (Pparent nullptr){_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;}//左旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;Node* Pparent parent-_parent;if (subRL){subRL-_parent parent;}subR-_left parent;parent-_parent subR;parent-_right subRL;if (Pparent nullptr){_root subR;subR-_parent nullptr;}else{if (Pparent-_left parent){Pparent-_left subR;}else{Pparent-_right subR;}subR-_parent Pparent;}parent-_bf 0;subR-_bf 0;}//左右旋void RotateLR(Node* parent){//subL subLR parentNode* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(subL);RotateR(parent);if (bf 0){subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else if (bf 1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else if (bf -1){subL-_bf 0;subLR-_bf 0;parent-_bf 1;}else{assert(false);}}//右左旋void RotateRL(Node* parent){//parent subRL subRNode* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);if (bf 0){subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else if (bf 1){subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else{assert(false);}}int Height(){return _Height(_root);}int Size(){return _Size(_root);}bool IsBalanceTree(){return _IsBalanceTree(_root);}void InOrder(){_InOrder(_root);cout endl;}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;}private://高度int _Height(Node* root){if (root nullptr){return 0;}int left _Height(root-_left);int right _Height(root-_right);return left right ? left 1 : right 1;}//结点个数int _Size(Node* root){if (root nullptr){return 0;}return _Size(root-_left) _Size(root-_right) 1;}//判断bool _IsBalanceTree(Node* root){//空树也是AVL树if (root nullptr){return true;}int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);int diff rightHeight - leftHeight;if (abs(diff) 2){cout root-_kv.first 高度差异常 endl;return false;}if (root-_bf ! diff){cout root-_kv.first 平衡因子异常 endl;return false;}return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);}//中序遍历void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}private:Node* _root nullptr;
};
test.cpp
//#include a.h
#include AVL.h
#include vectorvoid test01()
{AVLTreeint, int t;/*pairint, int p(1, 2);cout p.first p.second endl;t.Insert(p);t.Insert({1,1});*/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.Size() endl;cout t.Height() endl;cout t.IsBalanceTree() endl;
}void test02()
{const int N 1000000;vectorint v;v.reserve(N);srand((unsigned)time(0));for (size_t i 0; i N; i){v.push_back((int)(rand() i));}size_t begin2 clock();AVLTreeint, 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(((int)(rand() i)));}size_t end1 clock();cout Find: end1 - begin1 endl;
}int main()
{//test01();test02();return 0;
}
