二叉搜索树进阶

进阶"/>

二叉搜索树进阶

目录

• 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(log2​n)，搜索时间复杂度 O ( l o g 2 n ) O(log_2 n) O(log2​n)。

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树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

	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;
};