数据结构--AVL树

一、二叉搜索树（Binary Search Tree, BST）

基本性质

1. 对于树中的每个节点，其左子树中的所有节点值均小于该节点值。
2. 其右子树中的所有节点值均大于该节点值。
3. 左右子树也分别是二叉搜索树。

极端场景

在极端情况下，如插入节点顺序为升序或降序时，二叉搜索树会退化为链表结构。例如，依次插入 1, 2, 3, 4, 5，此时树的形状为一条从根节点开始不断向右延伸的链。这种退化导致树的高度变为 O (n)（n 为节点数），原本二叉搜索树查找、插入、删除操作平均时间复杂度为 O (log n)，此时会退化为 O (n)，效率大幅降低。

二、AVL 树（Adelson-Velsky and Landis Tree）

定义与特点

AVL 树是一种自平衡的二叉搜索树。它在向二叉搜索树中插入新节点时，通过特定的旋转操作，保证每个节点的左右子树高度之差的绝对值不超过 1。这使得 AVL 树在动态插入和删除节点过程中，始终保持较为平衡的状态，从而保证基本操作的时间复杂度稳定在 O (log n)。

平衡因子（Balance Factor）

1. 定义：平衡因子 = 右子树高度 - 左子树高度。
2. AVL 树的平衡条件：对于 AVL 树中的每一个节点，其平衡因子的绝对值不超过 1。即，| 右子树高度 - 左子树高度 | ≤ 1。当插入或删除节点导致某个节点的平衡因子绝对值大于 1 时，AVL 树会进行相应的旋转操作（左单旋、右单旋、双旋（先左旋后右旋和先右旋后左旋））来重新平衡树结构，确保树始终满足 AVL 树的性质。

 三、AVL 树 的实现

设计结构

1.节点结构

template<class K, class V>
class AVLTreeNode {
public:
    pair<K, V> _kv;              // 键值对
    AVLTreeNode<K, V>* _left;     // 左子节点
    AVLTreeNode<K, V>* _right;    // 右子节点
    AVLTreeNode<K, V>* _parent;   // 父节点（关键，用于回溯调整平衡）
    int _bf;                      // 平衡因子（右子树高度 - 左子树高度）

    AVLTreeNode(const pair<K,V>& kv):
	_kv(kv),
	_left(nullptr),
	_right(nullptr),
	_parent(nullptr),
	_bf(0)
    {}
};

2.树结构

template<class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
public:
    //增删改查操作
    //......
private:
    Node* _root = nullptr;  // 根节点
};

操作函数

插入

1.查找插入位置：

• 若树为空，直接创建根节点。

• 否则，从根节点开始遍历查找：

  bool insert(const pair<K, V>& kv) {
      if (_root == nullptr) {      // 空树直接插入
          _root = new Node(kv);
          return true;
      }
      
      Node* cur = _root, *parent = nullptr;
      while (cur) {                // 向下搜索插入位置
          parent = cur;
          if (kv.first < cur->_kv.first) cur = cur->_left;
          else if (kv.first > cur->_kv.first) cur = cur->_right;
          else return false;       // 重复键不允许插入
      }

2.插入新节点：

• 创建新节点 cur，根据键值大小链接到父节点的左或右。

      cur = new Node(kv);
      cur->_parent = parent;       // 绑定父节点
      if (kv.first < parent->_kv.first) 
          parent->_left = cur;     // 插入到左子树
      else 
          parent->_right = cur;    // 插入到右子树

• 设置 cur->_parent = parent（关键，后续调整依赖父指针）。

3.更新平衡因子：

• 从插入点的父节点向上回溯，调整每个祖先节点的平衡因子：

  • 插入在左子树：parent->_bf--

  • 插入在右子树：parent->_bf++

• 根据平衡因子决定是否继续调整或旋转：

  • _bf == 0：停止调整（子树高度未变）。

  • |_bf| == 1：继续向上调整。

  • |_bf| == 2：触发旋转（需判断旋转类型）。

    while (parent) {             // 从父节点向上回溯调整
        if (cur == parent->_left) parent->_bf--;
        else parent->_bf++;

        if (parent->_bf == 0) break;     // 高度不变，无需调整
        else if (abs(parent->_bf) == 1) { // 高度变化，继续向上
            cur = parent;
            parent = parent->_parent;
        }
        else if (abs(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 if (parent->_bf == -2 && cur->_bf == 1) 
				rotateLR(parent);       //左-右旋

            break;
        }
    }
    return true;
}

左单旋（rotateL）

• 确定关键节点

  

  • parent：失衡节点（_bf == 2）。

  • cur：parent的右子节点（_bf == 1）。

  • curleft：cur的左子节点。

  • grandParent：parent的父节点。

• 调整指针关系

1.处理curleft：

• parent->_right = curleft：将parent的右子指向curleft。
• 若curleft存在：设置curleft->_parent = parent。

2.建立cur与parent关系：

• cur->_left = parent：cur的左子指向原父节点。
• parent->_parent = cur：原父节点的父指针指向cur。

3.链接到原树：

• cur->_parent = grandParent：cur的父指针指向原祖父。
• 若grandParent为空：更新根节点为cur。
• 否则：根据parent在原树的位置，将grandParent的左/右子指向cur。

• 更新平衡因子

  

  • parent->_bf = 0

  • cur->_bf = 0

完整代码

void rotateL(Node* parent) {
	Node* grandParent = parent->_parent;
	Node* cur = parent->_right, * curleft = cur->_left;

	parent->_right = curleft;
	if (curleft) {
		curleft->_parent = parent;
	}

	cur->_left = parent;
	parent->_parent = cur;

	cur->_parent = grandParent;
	if (grandParent == nullptr) {
		_root = cur;
	}
	else {
		if (parent == grandParent->_left) {
			grandParent->_left = cur;
		}
		else {
			grandParent->_right = cur;
		}
	}

	parent->_bf = cur->_bf = 0;
}

右单旋 （rotateR） 

• 参考图：
  • 确定关键节点，调节指针关系：
  • 链接到原树 ：
• 复现代码：

  void rotateR(Node* parent) {
  	Node* grandParent = parent->_parent;
  	Node* cur = parent->_left, * curright = cur->_right;
  
  	parent->_left = curright;
  	if (curright) {
  		curright->_parent = parent;
  	}
  
  	cur->_right = parent;
  	parent->_parent = cur;
  
  	if (grandParent == nullptr) {
  		_root = cur;
          cur->_parent = nullptr;
  	}
  	else {
  		if (grandParent->_left == parent) {
  			grandParent->_left = cur;
  		}
  		else {
  			grandParent->_right = cur;
  		}
          cur->_parent = grandParent;
  	}
  
  	parent->_bf = cur->_bf = 0;
  }

左-右双旋 （rotateLR）

适用场景
父节点平衡因子为 -2，左子节点平衡因子为 1（左子树的右子树过高）。

步骤：

1.定位关键节点：

• parent：失衡节点（平衡因子 -2）。

• cur：parent 的左子节点（平衡因子 1）。

• curright：cur 的右子节点（需记录其原始平衡因子 tmpbf）。

2.执行双旋：

• 先左旋：对 cur 调用左单旋（rotateL），使 curright 成为新的左子树根。

• 再右旋：对 parent 调用右单旋（rotateR），使 curright 成为新的根节点。

3.调整平衡因子：

• tmpbf == 1：

  • parent->_bf = 0，cur->_bf = -1（左子树高度减少）。

  • curright->_bf = 0。

• tmpbf == -1：

  • parent->_bf = 1（右子树高度增加）。

  • cur->_bf = 0，curright->_bf = 0。

• tmpbf == 0：所有相关节点平衡因子置 0。

完整代码

void rotateLR(Node* parent) {
	Node* cur = parent->_left, * curright = cur->_right;
	int tmpbf = curright->_bf;
	rotateL(parent->_left);
	rotateR(parent);

	if (tmpbf == -1) {
		cur->_bf = 0;
		curright->_bf = 0;
		parent->_bf = 1;
	}
	else if (tmpbf == 1) {
		parent->_bf = 0;
		cur->_bf = -1;
		curright->_bf = 0;
	}
	else if (tmpbf == 0) {
		parent->_bf = cur->_bf = curright->_bf = 0;
	}
	else {
		assert(false);
	}
}

右-左双旋（rotateRL） 

适用场景：
父节点平衡因子为 2，右子节点平衡因子为 -1（右子树的左子树过高）。

步骤：

1.定位关键节点：

• parent：失衡节点（平衡因子 2）。

• cur：parent 的右子节点（平衡因子 -1）。

• curleft：cur 的左子节点（需记录其原始平衡因子 tmpbf）。

2.执行双旋：

• 先右旋：对 cur 调用右单旋（rotateR），使 curleft 成为新的右子树根。

• 再左旋：对 parent 调用左单旋（rotateL），使 curleft 成为新的根节点。

3.调整平衡因子：

• tmpbf == -1：

  • parent->_bf = 0，cur->_bf = 1（右子树高度增加）。

  • curleft->_bf = 0。

• tmpbf == 1：

  • parent->_bf = -1（左子树高度减少）。

  • cur->_bf = 0，curleft->_bf = 0。

• tmpbf == 0：所有相关节点平衡因子置 0。

补充：在 AVL 树的双旋转操作（如rotateRL和rotateLR）完成后需要调整平衡因子的原因？

在左单旋（rotateL）和右单旋（rotateR）操作中，旋转完成后直接将相关节点的平衡因子置为 0。这是因为单旋转操作在特定的失衡情况下进行，能够一步将树调整为平衡状态，旋转后相关节点的左右子树高度差重新达到平衡，所以可以简单地将平衡因子置为 0。

双旋转（rotateRL 和 rotateLR）是由两次单旋转组合而成，情况更为复杂。双旋转操作会改变多个节点的左右子树结构，旋转后不同节点的左右子树高度变化不能简单地通过将平衡因子置为 0 来处理，需要根据旋转前子节点的平衡因子情况来具体调整。（具体如何调整合一参考 rotateRL 和 rotateLR  的图解和实现）