小工具知识网

当前位置: 首页 > 行业知识 > 数据结构:AVL树

行业知识

数据结构:AVL树

2026-11-16 13:30:48 来源:互联网转载

���录

1、AVL树的概念

2、二叉搜索树的功能与实现

1、AVL树节点定义

2、AVL树的插入

3、AVL树的旋转操作

1、左旋

2、右旋

3、左右旋

 4、右左旋

 3、AVL树完整代码实现


1、AVL树的概念

        在前面的文章中,我们学过了二叉搜索树,二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。

一棵 AVL 树或者是空树,或者是具有以下性质的二叉搜索树: 它的左右子树都是 AVL 树 左右子树高度之差 ( 简称平衡因子 ) 的绝对值不超过 1(-1/0/1) 平衡因子:右子树高度减去左子树高度 如果一棵二叉搜索树是高度平衡的,它就是 AVL 树。如果它有 n 个结点,其高度可保持在 O(log2 n) ,搜索时间复杂度 O(log2 n) 。 以下是一个简单AVL树的示例:节点周围的是平衡因子。

2、二叉搜索树的功能与实现

1、AVL树节点定义

templatestruct AVLTreeNode{AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf; //平衡因子pair _kv;AVLTreeNode(const pair& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0),_kv(kv){}};
每个节点的平衡因子设置为0,每个节点包含左右指针,以及父节点指针,每个节点的数据用pair来实现,第一个元素为Key来比较。

2、AVL树的插入

AVL树是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看作二叉搜索树

插入过程与二叉搜索树一致,只不过要注意更新节点的平衡因子。

因为平衡因子是右子树高度减去左子树高度,所以如果在左子树添加节点,bf(平衡因子)--,在右子树添加,bf++。

parent节点的平衡因子更新有三种情况:

1、parent的平衡因子为0,说明满足AVL性质,插入成功。

2、parent的平衡因子为1或-1,说明该树的高度增加,需要向上更新。

3、parent的平衡因子为-2或2,说明该节点违反了平衡树性质,需要对其进行旋转处理。

旋转处理下面会介绍,我们先来看插入的代码实现:

bool Insert(const pair& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first _right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first _right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = 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){RotateLR(parent);}else{RotateRL(parent);}break;}else{assert(false);}}return true;}

寻找插入位置与搜索二叉树一致,然后更新平衡因子 ,对于不同的违反AVL树性质需要不同的旋转操作。

3、AVL树的旋转操作

我们先来看左旋对应的情况:

1、左旋

a,b,c具有相同的高度,旋转后注意更新parent和cur的平衡因子为0;
void RotateL(Node* parent){Node* sub = parent->_right;Node* subl = sub->_left;parent->_right = subl;if (subl){subl->_parent = parent;}sub->_left = parent;Node* ppnode = parent->_parent;parent->_parent = sub;if (parent == _root){_root = sub;sub->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = sub;}else{ppnode->_right = sub;}sub->_parent = ppnode;}parent->_bf = 0;sub->_bf = 0;}

2、右旋

原理与左旋相似,不过是向右旋转而已 (a,b,c具有相同的高度)

void RotateR(Node* parent){Node* sub = parent->_left;Node* subr = sub->_right;parent->_left = subr;if (subr){subr->_parent = parent;}sub->_right = parent;Node* ppnode = parent->_parent;parent->_parent = sub;if (parent == _root){_root = sub;sub->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = sub;}else{ppnode->_right = sub;}sub->_parent = parent;}parent->_bf = 0;sub->_bf = 0;}

3、左右旋

先以subl为根左旋,再以parent为根进行右旋。(a,b,c具有相同的高度)

void RotateLR(Node* parent){Node* subl = parent->_left;Node* sublr = subl->_right;int bf = sublr->_bf;RotateL(subl);RotateR(parent);if (bf == -1){sublr->_bf = 0;parent->_bf = 1;subl->_bf = 0;}else if (bf == 1){sublr->_bf = 0;parent->_bf = 0;subl->_bf = -1;}else if (bf == 0){subl->_bf = 0;parent->_bf = 0;sublr->_bf = 0;}else{assert(false);}}

根据sublr的平衡因子的不同(也就是插入到了B还是C)来判断如何更新平衡因子。

 4、右左旋

原理与左右旋相似,只是换了个方向。(a,b,c具有相同的高度)

void RotateRL(Node* parent){Node* subr = parent->_right;Node* subrl = subr->_left;int bf = subrl->_bf;RotateR(subr);RotateL(parent);if (bf == -1){subrl->_bf = 0;parent->_bf = 0;subr->_bf = 1;}else if (bf == 1){subrl->_bf = 0;parent->_bf = -1;subr->_bf = 0;}else if(bf==0){subrl->_bf = 0;parent->_bf = 0;subr->_bf = 0;}else{assert(false);}}

根据sublr的平衡因子的不同(也就是插入到了B还是C)来判断如何更新平衡因子。 

 3、AVL树完整代码实现

内部包含查找以及判断是否是AVL树的函数,以及中序遍历。

#pragma oncenamespace AVLTree_test{templatestruct AVLTreeNode{AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf; //平衡因子pair _kv;AVLTreeNode(const pair& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0),_kv(kv){}};templateclass AVLTree{typedef AVLTreeNode Node;public:bool Insert(const pair& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first _right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first _right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = 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){RotateLR(parent);}else{RotateRL(parent);}break;}else{assert(false);}}return true;}void RotateL(Node* parent){Node* sub = parent->_right;Node* subl = sub->_left;parent->_right = subl;if (subl){subl->_parent = parent;}sub->_left = parent;Node* ppnode = parent->_parent;parent->_parent = sub;if (parent == _root){_root = sub;sub->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = sub;}else{ppnode->_right = sub;}sub->_parent = ppnode;}parent->_bf = 0;sub->_bf = 0;}void RotateR(Node* parent){Node* sub = parent->_left;Node* subr = sub->_right;parent->_left = subr;if (subr){subr->_parent = parent;}sub->_right = parent;Node* ppnode = parent->_parent;parent->_parent = sub;if (parent == _root){_root = sub;sub->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = sub;}else{ppnode->_right = sub;}sub->_parent = parent;}parent->_bf = 0;sub->_bf = 0;}void RotateLR(Node* parent){Node* subl = parent->_left;Node* sublr = subl->_right;int bf = sublr->_bf;RotateL(subl);RotateR(parent);if (bf == -1){sublr->_bf = 0;parent->_bf = 1;subl->_bf = 0;}else if (bf == 1){sublr->_bf = 0;parent->_bf = 0;subl->_bf = -1;}else if (bf == 0){subl->_bf = 0;parent->_bf = 0;sublr->_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->_bf = 0;parent->_bf = 0;subr->_bf = 1;}else if (bf == 1){subrl->_bf = 0;parent->_bf = -1;subr->_bf = 0;}else if(bf==0){subrl->_bf = 0;parent->_bf = 0;subr->_bf = 0;}else{assert(false);}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout _kv.first _left);int rightHeight = Height(root->_right);return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;}bool _IsBalance(Node* root){if (root == nullptr)return true;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (abs(rightHeight - leftHeight) >= 2){cout _kv.first _kv.first _right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;}private:Node* _root = nullptr;};void TestAVLTree1(){int a[] = { 4, 2, 6, 1,0 ,67,56,33,212,90};AVLTree t;for (auto e : a){if (e == 14){int x = 0;}t.Insert(make_pair(e,e));}t.InOrder();cout 

上一篇:linux下怎么搭建svn服务器?

下一篇:轻松下载Oppokiller指南,步骤全解析揭秘!