网站数据库多大合适,网站 河北 备案 慢,京津冀协同发展规划纲要,企业seo推广的绝密诀窍曝光文章目录 1.介绍1.1定义1.2来源1.3概念1.特性2.平衡因子[ Balance Factor-- _bf ] 2.BSTAVL1.示例分析2.情况分类3.代码剖析3.1左左型-右单旋3.2右右型-左单旋3.3左右型-左右旋3.4右左型:右左旋3.5总图 3.完整代码3.1AVLTree.h3.2Test.cpp 1.介绍
1.1定义
AVL树 – 平衡二… 文章目录 1.介绍1.1定义1.2来源1.3概念1.特性2.平衡因子[ Balance Factor-- _bf ] 2.BSTAVL1.示例分析2.情况分类3.代码剖析3.1左左型-右单旋3.2右右型-左单旋3.3左右型-左右旋3.4右左型:右左旋3.5总图 3.完整代码3.1AVLTree.h3.2Test.cpp 1.介绍
1.1定义
AVL树 – 平衡二叉树 – 平衡二叉搜索排序树 – 高度平衡搜索树 Balanced Binary Tree BBT
1.2来源
AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis他们在1962年的论文《An algorithm for the organization of information》中发表了它。 二叉搜索树可以缩短查找的效率但在数据有序或接近有序时它将退化为单支树查找元素相当于在顺序表中搜索效率低下。两位俄罗斯的数学家发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
1.3概念
1.特性
一棵空树或左右两个子树高度差绝对值不超过1左右两个子树也都是一棵高度平衡搜索树
2.平衡因子[ Balance Factor-- _bf ]
结点的平衡因子 右子树高度 - 左子树高度| _bf | 1AVL树不一定有平衡因子, 使用平衡因子只是一种较为简单的实现方式
2.BSTAVL
[设定 _bf 右子树高度 - 左子树高度]
1.示例分析 先看一下下面的图 了解一下什么叫做旋转 以及旋转的目的 2.情况分类 3.代码剖析
3.1左左型-右单旋 void RotateRight(Node* dad){Node* Grandpa dad-_parent;Node* sonL dad-_left;Node* sonLR sonL-_right;//dad连接sonLR sonLR不空-继承dad 为空不继承dad-_left sonLR;if (sonLR)sonLR-_parent dad;//sonL连接dad dad继承sonLsonL-_right dad;dad-_parent sonL;//G为空 表明dad为根结点 if (Grandpa nullptr){//更新根结点_root sonL;//更新根结点成员属性_root-_parent nullptr;}else{//父连子if (Grandpa-_left dad)Grandpa-_left sonL;elseGrandpa-_right sonL;//子继承父sonL-_parent Grandpa;}//更新_bfsonL-_bf dad-_bf 0;}3.2右右型-左单旋 void RotateLeft(Node* dad)
{Node* Grandpa dad-_parent;Node* sonR dad-_right;Node* sonRL sonR-_left;//dad连接sonRL sonRL不空继承dad 为空不继承dad-_right sonRL;if (sonRL)sonRL-_parent dad;//sonR连接dad dad继承sonRsonR-_left dad;dad-_parent sonR;//Grandpa为空--dad为根节点 更新后 sonR为根节点 根节点的_parent置空if (Grandpa nullptr){_root sonR;_root-_parent nullptr;}//不为空 依实际连接else{//父连子if (Grandpa-_left dad)Grandpa-_left sonR;elseGrandpa-_right sonR;//子继承父sonR-_parent Grandpa;}//左旋目的达到 更新_bfdad-_bf sonR-_bf 0;
}3.3左右型-左右旋 void RotateLR(Node* dad)
{Node* sonL dad-_left;Node* sonLR sonL-_right;int bf sonLR-_bf;RotateLeft(sonL);RotateRight(dad);if (bf 1){sonLR-_bf 0;sonL-_bf -1;dad-_bf 0;}else if (bf -1){sonLR-_bf 0;sonL-_bf 0;dad-_bf 1;}else if (bf 0){sonLR-_bf 0;sonL-_bf 0;dad-_bf 0;}else{assert(false);}
}3.4右左型:右左旋 void RotateRL(Node* dad)
{Node* sonR dad-_right;Node* sonRL sonR-_left;int bf sonRL-_bf;//最终根结点的_bfRotateLeft(dad-_right);RotateRight(dad);if (bf 1){sonRL-_bf 0;dad-_bf -1;sonR-_bf 0;}else if (bf -1){sonRL-_bf 0;dad-_bf 0;sonR-_bf 1;}else if (bf 0){sonRL-_bf 0;dad-_bf 0;sonR-_bf 0;1}else{assert(false);}
}3.5总图 3.完整代码
3.1AVLTree.h
#pragma once
#include iostream
#include list
#include vector
#include algorithm
#include array
#include time.h
#include queue
#include stack
#include string
#include set
#include map
#include functional
#include assert.h
#include math.h
using namespace std;
templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _pair;int _bf; // balance factorAVLTreeNode(const pairK, V pair):_left(nullptr), _right(nullptr), _parent(nullptr), _pair(pair), _bf(0){}
};//高度平衡搜索树
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public://插入--创建二叉树bool Insert(const pairK, V pair){//空树--new结点if (_root nullptr){_root new Node(pair);return true;}//非空--插入//1.定位到合适位置Node* parent nullptr;Node* cp _root;while (cp){if (pair.first cp-_pair.first){parent cp;cp cp-_right;}else if (pair.first cp-_pair.first){parent cp;cp cp-_left;}else{//搜索树不可有数据重复 -- 插入失败return false;}}//2.链接cp new Node(pair);if (pair.first parent-_pair.first){parent-_left cp;}else{parent-_right cp;}//cp继承parentcp-_parent parent;//构建AVL树while (parent){//一、更新平衡因子//插入结点在右子树if (cp parent-_right){parent-_bf;}//插入结点在左子树else{parent-_bf--;}//二、分类讨论// _bf 1/-1 原为0 现高度受到影响// 回溯直至遇到根源结点 即_bf2/-2的结点if (parent-_bf 1 || parent-_bf -1){parent parent-_parent;cp cp-_parent;}//_bf 0 不做处理 原为-1/1 现已满足 不继续更新else if (parent-_bf 0){break;}else if (parent-_bf 2 || parent-_bf -2){//旋转处理目的://1.使得当前子树平衡 2.降低当前子树的高度//左单旋if (parent-_bf 2 cp-_bf 1){RotateL(parent);}//右单旋else if (parent-_bf -2 cp-_bf -1){RotateR(parent);}//左右旋else if (parent-_bf -2 cp-_bf 1){RotateLR(parent);}//右左旋else if (parent-_bf 2 cp-_bf -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}//中序遍历void InOrder(){_InOrder(_root);cout endl;}//高度接口int Height(){return _Height(_root);}//判断是否满足AVL树平衡bool IsBalance(){return _IsBalance(_root);}private:// 中序遍历void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_pair.first ;_InOrder(root-_right);}//高度接口int _Height(Node* root){if (root NULL)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}//判断是否满足AVL树平衡bool _IsBalance(Node* root){if (root NULL){return true;}int leftH _Height(root-_left);int rightH _Height(root-_right);if (rightH - leftH ! root-_bf){cout root-_pair.first Abnormal node balance factor! endl;return false;}return abs(leftH - rightH) 2 _IsBalance(root-_left) _IsBalance(root-_right);}//左单旋void RotateL(Node* parent){//记录GrandpaNode* Grandpa parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;//parent链接subRL subRL不空继承parent 空没必要继承parent-_right subRL;if (subRL)subRL-_parent parent;//subR连接parent parent继承subRsubR-_left parent;parent-_parent subR;//Grandpa为空--parent为根节点 更新后 subR为根节点 根节点的_parent置空if (Grandpa nullptr){_root subR;_root-_parent nullptr;}//不为空 依实际连接else{//父连子if (Grandpa-_left parent){Grandpa-_left subR;}else{Grandpa-_right subR;}//子继承父subR-_parent Grandpa;}parent-_bf subR-_bf 0;}//右单旋void RotateR(Node* parent){Node* Grandpa parent-_parent;Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (Grandpa-_left parent){Grandpa-_left subL;}else{Grandpa-_right subL;}subL-_parent Grandpa;}subL-_bf parent-_bf 0;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 1){parent-_bf 0;subLR-_bf 0;subL-_bf -1;}else if (bf -1){parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 0){parent-_bf 0;subLR-_bf 0;subL-_bf 0;}else{assert(false);}}void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 1){subR-_bf 0;parent-_bf -1;subRL-_bf 0;}else if (bf -1){subR-_bf 1;parent-_bf 0;subRL-_bf 0;}else if (bf 0){subR-_bf 0;parent-_bf 0;subRL-_bf 0;}else{assert(false);}}private:Node* _root nullptr;
};void Test_AVLTree1()
{int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int b[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTreeint, int tree;for (auto e : b){tree.Insert(make_pair(e, e));if (tree.IsBalance()){cout e 插入成功! endl;}else{cout e 插入失败! endl;}}cout 此树中序遍历: endl;tree.InOrder();if (tree.IsBalance()){cout 此树为一棵AVL树 endl;}else{cout 此树不为一棵AVL树! endl;}
}void Test_AVLTree2()
{srand(time(0));const size_t N 10;AVLTreeint, int tree;for (size_t i 0; i N; i){size_t x rand() i;tree.Insert(make_pair(x, x));if (tree.IsBalance()){cout x 插入成功! endl;}else{cout x 插入失败! endl;}}cout 此树中序遍历: endl;tree.InOrder();if (tree.IsBalance()){cout 此树为一棵AVL树 endl;}else{cout 此树不为一棵AVL树! endl;}cout 此树高度为: tree.Height() endl;
}
3.2Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include iostream
#include list
#include vector
#include algorithm
#include array
#include time.h
#include queue
#include stack
#include string
#include set
#include map
#include functional
using namespace std;
#include AVLTree.hint main()
{Test_AVLTree1();return 0;
}
