做网站需要看的书,苏州seo,房屋设计师游戏下载,网站网页模板文章目录 AVL树AVL树的规则或原理 AVL树的实现1.节点的定义2.功能和接口等的实现默认构造函数#xff0c;析构函数拷贝构造函数插入搜索打印函数检查是否为平衡树#xff0c;检查平衡因子旋转 AVL树
AVL树#xff0c;全称Adelson-Velsky和Landis树#xff0c;是一种自平衡… 文章目录 AVL树AVL树的规则或原理 AVL树的实现1.节点的定义2.功能和接口等的实现默认构造函数析构函数拷贝构造函数插入搜索打印函数检查是否为平衡树检查平衡因子旋转 AVL树
AVL树全称Adelson-Velsky和Landis树是一种自平衡的二叉搜索树。它于1962年由苏联科学家Adelson-Velsky和Landis首次提出。AVL树具有以下特点树中任一节点的左右子树高度差不超过1因此AVL树是一种严格平衡的二叉搜索树。在AVL树上进行查找、插入和删除操作的时间复杂度均为O(log n)大大提高了搜索效率。
AVL树的规则或原理
当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n)搜索时间复杂度O( l o g 2 n log_2 n log2n)。
AVL树的实现
1.节点的定义
首先我们定义AVL树的节点结构
templateclass K, class V
struct AVLTreeNode
{pairK, V _kv;//值 AVLTreeNodeK, V* _left;//该节点的左孩子AVLTreeNodeK, V* _right;//该节点的右孩子AVLTreeNodeK, V* _parent;//该节点的父节点int _bf; // balance factor平衡因子AVLTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};2.功能和接口等的实现
默认构造函数析构函数
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public://默认构造函数用来初始化AVL树将根节点置空来表示树是空的AVLTree() default;//析构函数~AVLTree(){Destroy(_root);_root nullptr;}
private:void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;}
private:Node* _root nullptr;
};拷贝构造函数
templateclass K, class V
class AVLTree
{//拷贝构造AVLTree(const AVLTreeK, V t){_root Copy(t._root);}private://用递归来进行赋值AVL树的节点Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key, root-_value);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}private:Node* _root nullptr;
};插入
templateclass K, class V
class AVLTree
{
private: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 (cur parent-_left)parent-_bf--;elseparent-_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){RotateL(parent);}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}else{RotateLR(parent);}break;}else{assert(false);}}return true;}private:Node* _root nullptr;
};搜索
templateclass K, class V
class AVLTree
{
private:Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return cur;}}return nullptr;}private:Node* _root nullptr;
};打印函数
templateclass K, class V
class AVLTree
{void InOrder(){_InOrder(_root);cout endl;}
private: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;
};检查是否为平衡树检查平衡因子
templateclass K, class V
class AVLTree
{
bool IsBanlanceTree(){return _IsBanlanceTree(_root);}
private://计算平衡因子函数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 _IsBanlanceTree(Node* root){//空树返回真if (nullptr root){return true;}//计算root的平衡因子即root左右子树高度差int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);int diff rightHeight - leftHeight;//如果计算出的平衡因子与root的平衡因子不相等//或root平衡因子的绝对值超过一则不是AVL树/*if (abs(diff) 2 || root-_bf ! diff){return false;}*/if (abs(diff) 2){cout root-_kv.first 高度差异常 endl;return false;}if (root-_bf ! diff){cout root-_kv.first 平衡因子异常 endl;return false;}//root的左右都是AVL树那么概述一定是AVL树return _IsBanlanceTree(root-_left) _IsBanlanceTree(root-_right);}
private:Node* _root nullptr;
};旋转
templateclass K, class V
class AVLTree
{void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* parentParent parent-_parent;csubR-_left parent;parent-_parent subR;if (parentParent nullptr){_root subR;subR-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}parent-_bf subR-_bf 0;}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* parentParent parent-_parent;subL-_right parent;parent-_parent subL;if (parentParent nullptr){_root subL;subL-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}parent-_bf subL-_bf 0;}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 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else{assert(false);}}void 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;}}
private:Node* _root nullptr;
};
