怎么制作网站教程,网站页面设计师,wordpress不能翻页,自己如何免费制作一个网站一、AVL树的定义
AVL全称叫做平衡二叉搜索#xff08;搜索#xff09;树#xff0c;两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种方法#xff1a;
当向二叉搜索树中插入新结点后#xff0c;如果能保证每个结点的左右子树高度之差的绝对值不超…一、AVL树的定义
AVL全称叫做平衡二叉搜索搜索树两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种方法
当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
1.它的左右子树都是AVL树。
2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。
1.1 平衡因子
平衡因子bf节点的右子树高度减去左子树高度。
结点的平衡因子 右子树的高度 - 左子树的高度
如果一棵二叉搜索树是高度平衡的每个节点的平衡因子绝对值1它就是 AVL 树。如果它有n个结点其高度可保持在O(log2^n) 查找时间复杂度O(log2^n) 。
1.2 平衡二叉树的作用
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。如下图所示向一颗空的二叉查找树和AVL树中插入有序数列 {123456}
由上图可知在插入有序结点个数很多的情况下会导致搜索二叉树的高度是O(N)查找时间复杂度O(n) 而AVL树就不会出现这种情况树的高度始终是O(log2^n) 查找时间复杂度O(log2^n) 。
二、AVL树的基本操作实现
AVL树的操作基本和二叉查找树一样例如遍历和查找。但是AVL树的插入和删除操作与平衡二叉树相比有很大的变化。AVL树需要保证每个结点的左右子树高度之差的绝对值不超过1如果我们按照一般的二叉查找树的插入、删除方式可能会破坏AVL树的平衡性所以需要对树中的结点进行调整旋转。
AVL树节点定义: templateclass k, class v
struct AVLTreeNode
{AVLTreeNodek, v* _left;//该节点的左孩子AVLTreeNodek, v* _right;//该节点的左孩子AVLTreeNodek, v* _parent;//该节点的双亲int _bf;//平衡因子//template class T1, class T2 struct pair;两个不同类型成员变量构造的结构体pairk, v _kv;AVLTreeNode(const pairk, v kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}
}; 2.1 AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步
1. 按照二叉搜索树的方式插入新节点。
2. 调整节点的平衡因子bf。结点的平衡因子 右子树的高度 - 左子树的高度 因此如果在一个节点的左子树插入节点bf--在一个节点的右子树插入节点bf。
对当前节点的平衡因子调整后当前节点的所在子树高度发生变化因此需要按照插入路径对当前节点的parent节点依次进行更新。下面对parent节点平衡因子更新后的三种情况进行分析
·parent-_bf 0更新前parent的bf为1或-1更新后其左右子树高度不变左右均衡parent节点所在子树高度不变不影响祖先节点bf。
·parent-_bf 1 || parent-_bf -1更新前parent的bf为0更新后parent节点所在子树高度改变继续向上更新parent节点的bf。
·parent-_bf 2 || parent-_bf -2此时bf为2或-2parent所在子树不平衡需要旋转调整。
bool Insert(const pairk, v kv){if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;//通过parent变量链接节点并给_parent更新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;//每次插入节点后对该节点的parent更新while (parent) //从插入节点的父节点开始沿插入路径向上对祖先节点的bf平衡因子进行更新{//bf右子树高度-左子树高度且绝对值1if (cur parent-_left){parent-_bf--;//插入左边父节点bf-1}else{parent-_bf;//插入右边父节点bf1}//判断是否更新祖先节点if (parent-_bf 0)//更新前parent的bf为1或-1其左右子树高度不变左右均衡parent所在子树高度不变不影响祖先节点{break;}else if (parent-_bf 1 || parent-_bf -1){//更新前parent的bf为0parent所在子树高度改变向上更新祖先节点cur cur-_parent;parent parent-_parent;}// 旋转处理4种情况else if (parent-_bf 2 || parent-_bf -2){//此时bf为2或-2parent所在子树不平衡需要调整if (parent-_bf 2 cur-_bf 1)//左单旋{//parent节点的右子树的高度比左子树高2parent节点的右子树的右子树高度比左子树高度高1RotateL(parent);}else if (parent-_bf -2 cur-_bf -1)//右单旋{//parent节点的左子树的高度比右子树高2parent节点的左子树的左子树高度比右子树高度高1RotateR(parent);}else if (parent-_bf -2 cur-_bf 1)//左右双旋{//parent节点的左子树的高度比右子树高2parent节点的左子树的右子树高度比左子树高度高1RotateLR(parent);}//右左双旋else//parent-_bf 2 cur-_bf -1{//parent节点的右子树的高度比左子树高2parent节点的右子树的左子树高度比右子树高度高1RotateRL(parent);}break;}else{// 插入之前AVL树就有问题assert(false);}}return true;}
AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构 使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种
2.2.1 插入—— 右右型的左单旋
在parent结点的右子树的右子树上做了插入元素的操作parent-_bf 2 cur-_bf 1我们称这种情况为右右型 我们应该进行左旋转。a,b,c高度均为h。 把subRL节点放到parent的右子树上subR节点向左旋转到parent的位置成为新的根节点将subR的左子树指向parent节点。对subR,parent,subRL的_parent进行更新 让原来parent的父亲节点指向subR最后更新parent与subR节点的_bf0。具体代码实现如下
void RotateL(Node* parent)//左单旋{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL) {subRL-_parent parent;//更新subRL的父亲节点}subR-_left parent;Node* ppnode parent-_parent;//记录parent的父节点parent-_parent subR;//更新parent的父亲节点if (parent _root)//考虑parent是该树的根节点{_root subR;subR-_parent nullptr;}else//若parent不是该树的根节点将原来parent节点的父亲指向subR{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;//更新parent的父亲节点}parent-_bf 0;subR-_bf 0;}
2.2.2 插入—— 左左型的右单旋
在parent结点的左子树的左子树上做了插入元素的操作parent-_bf -2 cur-_bf -1我们称这种情况为左左型 我们应该进行右旋转。a,b,c高度均为h。 把subLR节点放到parent的左子树上subL节点向右旋转到parent的位置成为新的根节点将subL的右子树指向parent节点。与左旋原理相同具体代码实现如下
void RotateR(Node* parent)//右单旋{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR) {subLR-_parent parent;}subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}subL-_bf 0;parent-_bf 0;}
2.2.3 插入—— 左右型的左右双旋
在parent结点的左子树的右子树上做了插入元素的操作parent-_bf -2 cur-_bf 1我们称这种情况为左右型 我们应该进行左右双旋转。a,d高度均为hb,c高度均为h-1。 左旋把b节点放到subL的右子树上subLR节点向左旋转到subL的位置将subLR的左子树指向subL节点。
右旋把c节点放到parent的左子树上subLR节点向右旋转到parent的位置将subLR的右子树指向parent节点。
更新平衡因子由图可知在parent结点的左子树的右子树上插入元素插入在bc子树上后subLR的bf都为零,而subL和parent的bf会发生变化。根据插入元素后subLR的bf的三种情况下面对subL和parent的bf进行分析a,d高度均为hb,c高度均为h-1
1. subRL-_bf0原来subLR位置为空。subL-_bf 0parent-_bf 0。
2. subRL-_bf-1在b节点插入元素。左右双旋后b所在子树x到subL的右子树c所在子树到parent的左子树。subL-_bf 0parent-_bf 1。
3. subRL-_bf1在c节点插入元素。左右双旋后b所在子树到subL的右子树c所在子树x到parent的左子树。subL-_bf -1parent-_bf 0。
代码实现如下
void RotateLR(Node* parent)//左右双旋{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;//记录旋转前bfRotateL(subL);//先以subL为parent,左旋RotateR(parent);//在以parent右旋//修改subL,subLR,parent节点的bfif (bf -1) //插入在subLR的左子树{subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 1)//插入在subLR的右子树{subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (bf 0)//插入在subLR{subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{assert(false);}}
2.2.4 插入—— 右左型的右左双旋
在parent结点的左子树的右子树上做了插入元素的操作parent-_bf -2 cur-_bf 1我们称这种情况为左右型 我们应该进行左右双旋转。a,d高度均为hb,c高度均为h-1。 右旋把c节点放到parent的左子树上subRL节点向右旋转到subR的位置将subRL的右子树指向subR节点。
左旋把b节点放到parent的右子树上subRL节点向左旋转到parent的位置将subRL的左子树指向parent节点。
平衡因子的更新参照左右双旋代码实现如下
void RotateRL(Node* parent)//右左双旋{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);if (bf -1)//插入在subRL的左子树{subRL-_bf 0;subR-_bf 1;parent-_bf 0;}else if (bf 1)//插入在subRL的右子树{subRL-_bf 0;subR-_bf 0;parent-_bf -1;}else if (bf 0)//插入在subRL{subRL-_bf 0;subR-_bf 0;parent-_bf 0;}else{assert(false);}}
2.2 AVL树的查找、删除
AVL树的查找与二叉搜索树相同请参照数据结构——二叉搜索树详解-CSDN博客。
AVL树的删除与插入类似先按照二叉搜索树的方法删除然后更行平衡因子。平衡因子的更新与插入相反删除左边节点bf删除右边节点bf--。如果不平衡进行旋转调整。
三、AVL树的验证
按照上述的插入方式构造一颗AVL树又如何判断它是不是真的AVL树呢
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步
1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树
2. 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)且节点的平衡因子是否计算正确。
bool _IsBalance(Node* root, int height){if (root nullptr){height 0;return true;}int lefth 0, righth 0;if (!_IsBalance(root-_left, lefth) || !_IsBalance(root-_right, righth)){return false;}if (abs(righth - lefth) 2) {cout root-_kv.first 不平衡 endl;return false;}if (righth - lefth ! root-_bf) {cout root-_kv.first 平衡因子异常 endl;}height lefth righth ? lefth 1 : righth 1;return true;}
注意这里hieght为传引用可以修改原变量lefth和righth。通过后序遍历的方式从第n层的叶子节点往上递归。通过获得的左右子树高度lefth和righth计算该节点的bf进行判断再计算出该节点height最后把该节点的height又作为上一层节点的lefth或righth返回。
四、AVL树的模拟实现及总结
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#includeassert.h
#includetime.h
#include utility
#includevector
#includestdbool.h
#includeiostream
#includestdlib.h
using namespace std;templateclass k, class v
struct AVLTreeNode
{AVLTreeNodek, v* _left;AVLTreeNodek, v* _right;AVLTreeNodek, v* _parent;int _bf;//平衡因子//template class T1, class T2 struct pair;两个不同类型成员变量构造的结构体pairk, v _kv;AVLTreeNode(const pairk, v kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}
};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;//通过parent变量链接节点并给_parent更新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;//每次插入节点后对该节点的parent更新while (parent) //从插入节点的父节点开始沿插入路径向上对祖先节点的bf平衡因子进行更新{//bf右子树高度-左子树高度且绝对值1if (cur parent-_left){parent-_bf--;//插入左边父节点bf-1}else{parent-_bf;//插入右边父节点bf1}//判断是否更新祖先节点if (parent-_bf 0)//更新前parent的bf为1或-1其左右子树高度不变左右均衡parent所在子树高度不变不影响祖先节点{break;}else if (parent-_bf 1 || parent-_bf -1){//更新前parent的bf为0parent高度改变向上更新祖先节点cur cur-_parent;parent parent-_parent;}// 旋转处理4种情况else if (parent-_bf 2 || parent-_bf -2){//此时bf为2或-2parent所在字树不平衡需要调整if (parent-_bf 2 cur-_bf 1)//左单旋{//parent节点的右子树的高度比左子树高2parent节点的右子树的右子树高度比左子树高度高1RotateL(parent);}else if (parent-_bf -2 cur-_bf -1)//右单旋{//parent节点的左子树的高度比右子树高2parent节点的左子树的左子树高度比右子树高度高1RotateR(parent);}else if (parent-_bf -2 cur-_bf 1)//左右双旋{//parent节点的左子树的高度比右子树高2parent节点的左子树的右子树高度比左子树高度高1RotateLR(parent);}//右左双旋else//parent-_bf 2 cur-_bf -1{//parent节点的右子树的高度比左子树高2parent节点的右子树的左子树高度比右子树高度高1RotateRL(parent);}break;}else{// 插入之前AVL树就有问题assert(false);}}return true;}void RotateL(Node* parent)//左单旋{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL) {subRL-_parent parent;}subR-_left parent;Node* ppnode parent-_parent;//记录parent的父节点parent-_parent subR;if (parent _root)//考虑parent是该树的根节点{_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}parent-_bf 0;subR-_bf 0;}void RotateR(Node* parent)//右单旋{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR) {subLR-_parent parent;}subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}subL-_bf 0;parent-_bf 0;}void RotateLR(Node* parent)//左右双旋{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;//记录旋转前bfRotateL(subL);//先以subL为parent,左旋RotateR(parent);//在以parent右旋//修改subL,subLR,parent节点的bfif (bf -1) //插入在subLR的左子树{subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 1)//插入在subLR的右子树{subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (bf 0)//插入在subLR{subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{assert(false);}}void RotateRL(Node* parent)//右左双旋{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);if (bf -1)//插入在subRL的左子树{subRL-_bf 0;subR-_bf 1;parent-_bf 0;}else if (bf 1)//插入在subRL的右子树{subRL-_bf 0;subR-_bf 0;parent-_bf -1;}else if (bf 0)//插入在subRL{subRL-_bf 0;subR-_bf 0;parent-_bf 0;}else{assert(false);}}//中序遍历void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first [ root-_bf ] endl;_InOrder(root-_right);}void InOrder(){_InOrder(_root);}//二叉树高度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;}int Height(){return _Height(_root);}//二叉树的大小size_t _Size(Node* root){if (root NULL)return 0;return _Size(root-_left) _Size(root-_right) 1;}size_t Size(){return _Size(_root);}//AVL树查找:与二叉搜索树相同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 NULL;}bool _IsBalance(Node* root, int height){if (root nullptr){height 0;return true;}int lefth 0, righth 0;if (!_IsBalance(root-_left, lefth) || !_IsBalance(root-_right, righth)){return false;}if (abs(righth - lefth) 2) {cout root-_kv.first 不平衡 endl;return false;}if (righth - lefth ! root-_bf) {cout root-_kv.first 平衡因子异常 endl;}height lefth righth ? lefth 1 : righth 1;return true;}//判断二叉树是否平衡bool IsBalance(){int height 0;return _IsBalance(_root, height);}private:Node* _root nullptr;};
void TestAVLTree1()
{//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTreeint, int t;for (auto e : a){if (e 14){int x 0;}t.Insert(make_pair(e, e));// 1、先看是插入谁导致出现的问题// 2、打条件断点画出插入前的树// 3、单步跟踪对比图一一分析细节原因cout e - t.IsBalance() endl;}t.InOrder();cout t.IsBalance() endl;
}void TestAVLTree2()
{const int N 1000000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand() i);//cout v.back() endl;}size_t begin2 clock();AVLTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));//cout Insert: e - t.IsBalance() endl;}size_t end2 clock();cout Insert: end2 - begin2 endl;cout t.IsBalance() 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;
}
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1在插入、删除的过程中会出现一下四种情况破坏AVL树的特性我们可以采取相应的旋转。这样可以保证查询时高效的时间复杂度即O(log2^n)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时 有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
