目录
- AVL树概念
- AVL树实现
- AVL树基础结构
- 插入
- 插入:左旋实现
- 插入:右旋实现
- AVL树完整实现代码:
之前学习到的二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。
因此为了解决这一问题,发明了一种新方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
AVL树概念
一棵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 ) O(log_2 n) O(log2n)。
AVL树实现
AVL树基础结构
- AVL树节点定义
//AVL树节点定义
template <class T>
struct AVLNode
{T _val;//平衡因子int _bf;typedef AVLNode<T> Node;Node* _parent;Node* _left;Node* _right;AVLNode(const T& val = T()):_val(val),_bf(0),_parent(nullptr),_left(nullptr),_right(nullptr){}
};
- AVL树定义
template <class T>
class AVLTree
{
public:typedef AVLNode<T> Node;private:Node* _root = nullptr;
};
插入
AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步:
- 按照二叉搜索树的方式插入新节点
- 调整节点的平衡因子
bool insert(const T& val){if (_root == nullptr){_root = new Node(val);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (cur->_val == val)return false;else if (cur->_val > val)cur = cur->_left;elsecur = cur->_right;}cur = new Node(val);if (parent->_val > val)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//调整,从parent开始while (parent){//更新parent的平衡因子,如果在左子树插入新节点-1,如果右子树插入+1if (parent->_left == cur)--parent->_bf;else++parent->_bf;//直到父节点的平衡因子为0时停止更新(平衡因子为0说明插入新节点对祖先父节点的平衡因子不会有影响)if (parent->_bf == 0)//停止更新break;//如果平衡因子不为0,则继续向上更新else if (parent->_bf == 1 || parent == -1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){if (parent->_bf == -2 && cur->_bf == -1){//左边的左边高//右旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//右边的右边高//左旋RotateL(parent);}break;}}return true;}
插入:左旋实现
//左旋操作结构如下://parent(2)// subR(1)// subRL(0)void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subL->_left;subR->_left = parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;//更新cur和父亲的父亲之间的连接//判断是否为根节点if (parent == _root){_root = subR;subR->_parent = nullptr;}else{Node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = subR;elsepparent->_right = subR;subR->_parent = pparent;}//更新父亲的父亲为curparent->_parent = subR;//更新平衡因子subR->_bf = parent->_bf = 0;}
插入:右旋实现
//右旋操作结构如下:// parent(-2)//subL(-1)// subLR(0)void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;//更新cur和父亲的父亲之间的连接//判断是否为根节点if (parent == _root){_root = subL;subL->_parent = nullptr;}else{Node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = subL;elsepparent->_right = subL;subL->_parent = pparent;}//更新父亲的父亲为curparent->_parent = subL;//更新平衡因子subL->_bf = parent->_bf = 0;}
AVL树完整实现代码:
//AVL树节点定义
template <class T>
struct AVLNode
{T _val;//平衡因子int _bf;typedef AVLNode<T> Node;Node* _parent;Node* _left;Node* _right;AVLNode(const T& val = T()):_val(val),_bf(0),_parent(nullptr),_left(nullptr),_right(nullptr){}
};template <class T>
class AVLTree
{
public:typedef AVLNode<T> Node;bool insert(const T& val){if (_root == nullptr){_root = new Node(val);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (cur->_val == val)return false;else if (cur->_val > val)cur = cur->_left;elsecur = cur->_right;}cur = new Node(val);if (parent->_val > val)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//调整,从parent开始while (parent){//更新parent的平衡因子,如果在左子树插入新节点-1,如果右子树插入+1if (parent->_left == cur)--parent->_bf;else++parent->_bf;//直到父节点的平衡因子为0时停止更新(平衡因子为0说明插入新节点对祖先父节点的平衡因子不会有影响)if (parent->_bf == 0)//停止更新break;//如果平衡因子不为0,则继续向上更新else if (parent->_bf == 1 || parent == -1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){if (parent->_bf == -2 && cur->_bf == -1){//左边的左边高//右旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//右边的右边高//左旋RotateL(parent);}break;}}return true;}//右旋操作结构如下:// parent(-2)//subL(-1)// subLR(0)void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;//更新cur和父亲的父亲之间的连接//判断是否为根节点if (parent == _root){_root = subL;subL->_parent = nullptr;}else{Node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = subL;elsepparent->_right = subL;subL->_parent = pparent;}//更新父亲的父亲为curparent->_parent = subL;//更新平衡因子subL->_bf = parent->_bf = 0;}//右旋操作结构如下:// parent(-2)//subL(-1)// subLR(0)void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;//更新cur和父亲的父亲之间的连接//判断是否为根节点if (parent == _root){_root = subL;subL->_parent = nullptr;}else{Node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = subL;elsepparent->_right = subL;subL->_parent = pparent;}//更新父亲的父亲为curparent->_parent = subL;//更新平衡因子subL->_bf = parent->_bf = 0;}//左旋操作结构如下://parent(2)// subR(1)// subRL(0)void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subL->_left;subR->_left = parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;//更新cur和父亲的父亲之间的连接//判断是否为根节点if (parent == _root){_root = subR;subR->_parent = nullptr;}else{Node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = subR;elsepparent->_right = subR;subR->_parent = pparent;}//更新父亲的父亲为curparent->_parent = subR;//更新平衡因子subR->_bf = parent->_bf = 0;}private:Node* _root = nullptr;
};