【基本数据结构】平衡二叉树

文章目录

前言
平衡二叉树
- 1 简介
- 2 旋转
- - 2.1 左旋
  - 2.2 右旋
  - 2.3 何时旋转
- 3 插入节点
- 4 删除节点
- 5 代码
参考资料
写在最后

前言

本系列专注更新基本数据结构，现有以下文章：

【算法与数据结构】数组.

【算法与数据结构】链表.

【算法与数据结构】哈希表.

【算法与数据结构】二叉查找树

【算法与数据结构】平衡二叉树

平衡二叉树

1 简介

平衡二叉树是为了解决二叉查找树中树退化成链这一问题而提出的。平衡二叉树在插入、删除某一节点之后通过左旋或右旋操作保持动态平衡，从而避免节点失衡（最坏的情况是树退化成链）。

二叉树某节点是否失衡由该节点的 失衡因子 来衡量，失衡因子为左子树节点高度与右子节点高度之差。

当二叉树中某节点的左、右子树高度差不超过1，则表示该节点平衡，高度差不超过 1 对应平衡因子的值为 ±1 和 0。

左旋与右旋，由于插入、删除节点导致二叉树中出现不平衡节点，此时可以通过左旋或右旋操作调整节点位置以达到二叉查找树的动态平衡。平衡二叉树也是一棵二叉查找树，它的查找、插入、删除都与二叉查找树的操作相同，只是在插入、删除新的节点之后需要通过一些旋转操作来保持其平衡性。

2 旋转

2.1 左旋

左旋，顾名思义，指的是向左旋转节点，或者是逆时针旋转节点。在图 2-1 中，由于插入了一个新的节点到平衡二叉树中，根节点 3 平衡因子变为 0-2=-2，说明此时根节点已经失衡了。为了保持这棵二叉查找树的平衡性，需要左旋根节点。

图 2-1 左旋

实现代码

// 左旋操作
Node* leftRotate(Node* x) {Node* y = x->right;Node* T2 = y->left;y->left = x;x->right = T2;x->height = std::max(height(x->left), height(x->right)) + 1;y->height = std::max(height(y->left), height(y->right)) + 1;return y;
}

上述代码是左旋的具体操作，传入的一个节点指针 x，表示从该节点开始进行左旋，最终返回的是左旋操作后该子树新的根节点。

以图 2-1 为例，传入的节点为 3，首先记录 3 的右子节点 4，记作 y；接着记录 y 的左子节点空节点，记作 T2；接下来将 4 的左链接连到 3 上，3 的右链接连到空节点上。

最后，还需要更新节点 x 和 y 的高度，为后面计算平衡因子做准备。

2.2 右旋

右旋，指的是向右旋转节点，或者是顺时针旋转节点。在图 2-2 中，由于插入了一个新的节点到平衡二叉树中，根节点 9 平衡因子变为 2-0=2，说明此时根节点已经失衡了。为了保持这棵二叉查找树的平衡性，需要右旋根节点。

图 2-2 右旋

实现代码

// 右旋操作
Node* rightRotate(Node* y) {Node* x = y->left;Node* T2 = x->right;x->right = y;y->left = T2;y->height = std::max(height(y->left), height(y->right)) + 1;x->height = std::max(height(x->left), height(x->right)) + 1;return x;
}

右旋操作与左旋操作类似，具体实现见代码。

2.3 何时旋转

什么时候需要进行旋转操作，当然是失衡的时候。以下列出的是失衡的四种情况，以及为了保持平衡需要做出的旋转决策：

LL型，在当前节点的左子节点的左子节点插入新的节点后，当前节点失衡，此时为了保持平衡需要右旋当前节点。
RR型，在当前节点的右子节点的右子节点插入新的节点后，当前节点失衡，此时为了保持平衡需要左旋当前节点。
LR型，在当前节点的左子节点的右子节点插入新的节点后，当前节点失衡，此时为了保持平衡需要先左旋当前节点的左子节点，再右旋当前节点。
RL型，在当前节点的右子节点的左子节点插入新的节点后，当前节点失衡，此时为了保持平衡需要先右旋当前节点的右子节点，再左旋当前节点。

在 LL型情况中，我们注意到失衡节点的失衡因子为 2，失衡节点的左子节点的失衡因子为 1。类似的，在 RR型中，失衡节点的失衡因子为 -2，失衡节点的失衡因子为 -1；在 LR型中，失衡节点的失衡因子为 2，失衡节点的失衡因子为 -1；在 RL型中，失衡节点的失衡因子为 -2，失衡节点的失衡因子为 1。于是，我们可以根据失衡节点的失衡因子、失衡节点的左子节点的失衡因子、失衡节点的右子节点的失衡因子来判断当前是什么类型，进而做出相应的旋转决策。

图 2-3 LL型

图 2-4 RR型

图 2-5 LR型

图 2-6 RL型

3 插入节点

插入节点和在二叉查找树中插入节点一样，先进行未命中的查找，将节点插入到合适的位置。然后根据以上四种情况进行旋转以保持平衡二叉树的平衡性。比如在图 2-6 中插入一个新的节点 8，通过二分查找确定节点 8 的位置为节点 6 右子节点。但是插入节点 8 之后，造成根节点 5 的平衡因子失衡了。因为这是 RL型 情况，所以先右旋根节点的右子树，然后再左旋根节点。

需要注意的是，当插入节点导致多个祖先节点失衡，只需要调整距离插入节点最近的失衡节点即可，其他失衡节点会自动平衡。

图 3-1 调整最近的失衡节点

实现代码

// 插入节点
Node* insert(Node* node, int key) {if (node == nullptr)return new Node(key);if (key < node->key)node->left = insert(node->left, key);else if (key > node->key)node->right = insert(node->right, key);elsereturn node;node->height = 1 + std::max(height(node->left), height(node->right));int balance = getBalance(node);// LL 型if (balance > 1 && key < node->left->key)return rightRotate(node);// RR 型if (balance < -1 && key > node->right->key)return leftRotate(node);// LR 型if (balance > 1 && key > node->left->key) {node->left = leftRotate(node->left);return rightRotate(node);}// RL 型if (balance < -1 && key < node->right->key) {node->right = rightRotate(node->right);return leftRotate(node);}return node;
}

在上述插入代码中，我们先进行未命中的查找，在递归查找中插入新的节点。接着，更新当前根节点的高度。最后根据当前节点的平衡因子的不同值来确定是哪一个类型，再根据不同的类型进行相应的调整。具体地：

如果当前节点的失衡因子为 2，并且是在当前节点的左子节点的左子节点插入新的节点，则是 LL 型，右旋该节点即可；
如果当前节点的失衡因子为 -2，并且是在当前节点的右子节点的右子节点插入新的节点，则是 RR 型，左旋节点即可；
如果当前节点的失衡因子为 2，并且是在当前节点的左子节点的右子节点插入新的节点，则是 LR 型，先左旋该节点的左子节点，再右旋该节点；
如果当前节点的失衡因子为 -2，并且是在当前节点的右子节点的左子节点插入新的节点，则是 RL 型，先右旋该节点的右子节点，再左旋该节点；

4 删除节点

删除节点操作也需要先进行查找，递归的进行查找。查找到需要删除的节点 root 之后，按照以下情况进行处理：

如果该节点是叶子节点，直接删除该节点；
如果该节点仅有左子节点或者右子节点，则删除对应的子节点；
如果该节点的左右节点都齐全，则用右子节点中最小的节点更新 root，并删除这个右子节点。

接着更新 root 的高度。最后将失衡的节点旋转，保持平衡。依然是根据当前节点与左、右子节点的平衡因子来判断属于哪种旋转情况，然后进行相应的旋转。

实现代码

// 删除节点
Node* deleteNode(Node* root, int key) {if (root == nullptr)return root;if (key < root->key)root->left = deleteNode(root->left, key);else if (key > root->key)root->right = deleteNode(root->right, key);else {if ((root->left == nullptr) || (root->right == nullptr)) {Node* temp = root->left ? root->left : root->right;if (temp == nullptr) {temp = root;root = nullptr;} else*root = *temp;delete temp;} else {Node* temp = minValueNode(root->right);root->key = temp->key;root->right = deleteNode(root->right, temp->key);}}if (root == nullptr)return root;root->height = 1 + std::max(height(root->left), height(root->right));int balance = getBalance(root);if (balance > 1 && getBalance(root->left) >= 0)return rightRotate(root);if (balance > 1 && getBalance(root->left) < 0) {root->left = leftRotate(root->left);return rightRotate(root);}if (balance < -1 && getBalance(root->right) <= 0)return leftRotate(root);if (balance < -1 && getBalance(root->right) > 0) {root->right = rightRotate(root->right);return leftRotate(root);}return root;
}

5 代码

#include <iostream>
#include <algorithm>class AVLTree {
private:struct Node {int key;Node* left;Node* right;int height;Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}};Node* root;int height(Node* n) {return n == nullptr ? 0 : n->height;}// 求平衡因子int getBalance(Node* n) {return n == nullptr ? 0 : height(n->left) - height(n->right);}// 右旋操作Node* rightRotate(Node* y) {Node* x = y->left;Node* T2 = x->right;x->right = y;y->left = T2;y->height = std::max(height(y->left), height(y->right)) + 1;x->height = std::max(height(x->left), height(x->right)) + 1;return x;}// 左旋操作Node* leftRotate(Node* x) {Node* y = x->right;Node* T2 = y->left;y->left = x;x->right = T2;x->height = std::max(height(x->left), height(x->right)) + 1;y->height = std::max(height(y->left), height(y->right)) + 1;return y;}// 插入节点Node* insert(Node* node, int key) {if (node == nullptr)return new Node(key);if (key < node->key)node->left = insert(node->left, key);else if (key > node->key)node->right = insert(node->right, key);elsereturn node;node->height = 1 + std::max(height(node->left), height(node->right));int balance = getBalance(node);// LL 型if (balance > 1 && key < node->left->key)return rightRotate(node);// RR 型if (balance < -1 && key > node->right->key)return leftRotate(node);// LR 型if (balance > 1 && key > node->left->key) {node->left = leftRotate(node->left);return rightRotate(node);}// RL 型if (balance < -1 && key < node->right->key) {node->right = rightRotate(node->right);return leftRotate(node);}return node;}// 获得最小节点值Node* minValueNode(Node* node) {Node* current = node;while (current->left != nullptr)current = current->left;return current;}// 删除节点Node* deleteNode(Node* root, int key) {if (root == nullptr)return root;if (key < root->key)root->left = deleteNode(root->left, key);else if (key > root->key)root->right = deleteNode(root->right, key);else {if ((root->left == nullptr) || (root->right == nullptr)) {Node* temp = root->left ? root->left : root->right;if (temp == nullptr) {temp = root;root = nullptr;} else*root = *temp;delete temp;} else {Node* temp = minValueNode(root->right);root->key = temp->key;root->right = deleteNode(root->right, temp->key);}}if (root == nullptr)return root;root->height = 1 + std::max(height(root->left), height(root->right));int balance = getBalance(root);if (balance > 1 && getBalance(root->left) >= 0)return rightRotate(root);if (balance > 1 && getBalance(root->left) < 0) {root->left = leftRotate(root->left);return rightRotate(root);}if (balance < -1 && getBalance(root->right) <= 0)return leftRotate(root);if (balance < -1 && getBalance(root->right) > 0) {root->right = rightRotate(root->right);return leftRotate(root);}return root;}// 查找节点Node* search(Node* root, int key) {if (root == nullptr || root->key == key)return root;if (key < root->key)return search(root->left, key);return search(root->right, key);}// 中序遍历void inOrder(Node* root) {if (root != nullptr) {inOrder(root->left);std::cout << root->key << " ";inOrder(root->right);}}public:AVLTree() : root(nullptr) {}// 插入节点的对外接口void insert(int key) {root = insert(root, key);}// 删除节点的对外接口void deleteNode(int key) {root = deleteNode(root, key);}// 搜索节点的对外接口bool search(int key) {return search(root, key) != nullptr;}// 中序遍历的对外接口void inOrder() {inOrder(root);std::cout << std::endl;}
};int main() {AVLTree tree;tree.insert(10);tree.insert(20);tree.insert(30);tree.insert(40);tree.insert(50);tree.insert(25);std::cout << "中序遍历后的AVL树: ";tree.inOrder();tree.deleteNode(10);std::cout << "删除节点10后的AVL树: ";tree.inOrder();int key = 25;if (tree.search(key))std::cout << "找到节点: " << key << std::endl;elsestd::cout << "未找到节点: " << key << std::endl;return 0;
}