数据结构 AVL树 - 北京网站建设

概述

AVL树的主要特点是在插入或者删除节点后，树会自动保持其平衡性，从而保证了最坏情况下，查找、插入和删除的时间复杂度都是O（log n）。注意AVL树是符合二叉搜索树的规则，即左子树小于根节点数值，右子树大于节点数值

平衡因子

平衡因子：一个节点左子树的高度减去右子树高度的值
BF = 左子树高度 - 右子树高度
AVL树节点，其平衡因子取值范围只可以在-1\0\1
BF = 0：左子树高度等于右子树高度，节点平衡
BF = 1：左子树高度比右子树高度多1，平衡
BF = -1：右子树高度比左子树高度多1 ，平衡
超出上述范围，就会导致不平衡需要进行旋转

旋转

单右旋

左子树的节点高度比右子树高的时候，则单右旋（左子树左侧节点变高的时候---左左右旋）

【注：圆形数字为平衡因子】

将失衡节点 y 的左子节点 x 作为新的根节点
将 x 的右子树 T2 作为 y 的左子树（因为旋转后，y 将成为 x 的右子节点）
更新 y 和 x 的高度
返回新的根节点 x

Node* rightRotate(Node* y) {Node* x = y->left;y->left = x->right;x->right = y;updateHeight(y);updateHeight(x);return x;
}

单左旋

右子树的高度比左子树高2时，新节点插入到了较高右子树的右侧（右右插入--左旋）

将失衡节点 x 的右子节点 y 作为新的根节点。
将 y 的左子树 T2 作为 x 的右子树（因为旋转后，x 将成为 y 的左子节点）。
更新 x 和 y 的高度。
返回新的根节点 y

Node* leftRotate(Node* x) {Node* y = x->right;x->right = y->left;y->left = x;updateHeight(x);updateHeight(y);return y;
}

左右旋

当新节点插入到较高左子树的右侧，则对该树先进左单选然后再右单旋（左右高，左右旋）

当某个节点的左子树高度比右子树高2，且左子树的右子树高度比左子树的左子树高的时候，先对左子树进行一次左旋转，然后再对根节点进行一次右旋

先左旋（用一个具体情况分析）：平衡因子不再标注

再右旋：90头结点进行右旋

右左旋

插入的新节点在较高右子树的左侧：先右单旋再左单旋（右左高--右左旋）

具体事例分析：先右旋 90

【注：数据设计有问题，将右子树下左子树的60改为61，左旋已更正】

再左旋，60左旋

代码实现

height函数：如果节点存在，返回节点的高度；如果节点为空，则返回0

int height(Node* node) {return node ? node->height : 0;
}

更新结节点高度，节点的高度等于左右子树中较高的高度+1

void updateHeight(Node* node) {node->height = 1 + std::max(height(node->left), height(node->right));
}

插入逻辑总结

递归插入节点：通过递归方式将新节点插入到适当的位置。如果节点为空，创建并返回一个新节点。
更新高度：插入节点后，递归回溯过程中更新每个节点的高度。
计算平衡因子：检查插入节点后树的平衡状态。
旋转调整：根据平衡因子进行适当的旋转：
左左情况：右旋。
右右情况：左旋。
左右情况：先左旋再右旋。
右左情况：先右旋再左旋。
返回节点：递归返回调整后的树的根节

Node* insert(Node* node, int key) {if (!node) 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; // 相同的key不插入updateHeight(node);int balance = getBalance(node);// 根据平衡因子调整树if (balance > 1 && key < node->left->key)  // 左左情况return rightRotate(node);if (balance < -1 && key > node->right->key) // 右右情况return leftRotate(node);if (balance > 1 && key > node->left->key) { // 左右情况node->left = leftRotate(node->left);return rightRotate(node);}if (balance < -1 && key < node->right->key) { // 右左情况node->right = rightRotate(node->right);return leftRotate(node);}return node; // 返回未变的节点
}

inOrder：升序打印AVL树中所有的节点

递归遍历左子树。
打印当前节点的值。
递归遍历右子树

void inOrder(Node* root) {if (root) {inOrder(root->left);std::cout << root->key << " ";inOrder(root->right);}
}

全代码

#include <iostream>// AVL树节点定义
struct Node {int key;          // 节点值Node* left;       // 左子树Node* right;      // 右子树int height;       // 节点高度Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {} // 构造函数
};// 获取节点高度
int height(Node* node) {return node ? node->height : 0;
}// 更新节点高度
void updateHeight(Node* node) {node->height = 1 + std::max(height(node->left), height(node->right));
}// 计算平衡因子
int getBalance(Node* node) {return node ? height(node->left) - height(node->right) : 0;
}// 右旋操作
Node* rightRotate(Node* y) {Node* x = y->left;y->left = x->right;x->right = y;updateHeight(y);updateHeight(x);return x;
}// 左旋操作
Node* leftRotate(Node* x) {Node* y = x->right;x->right = y->left;y->left = x;updateHeight(x);updateHeight(y);return y;
}// 插入节点并保持AVL树平衡
Node* insert(Node* node, int key) {if (!node) 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; // 相同的key不插入updateHeight(node);int balance = getBalance(node);// 根据平衡因子调整树if (balance > 1 && key < node->left->key)  // 左左情况return rightRotate(node);if (balance < -1 && key > node->right->key) // 右右情况return leftRotate(node);if (balance > 1 && key > node->left->key) { // 左右情况node->left = leftRotate(node->left);return rightRotate(node);}if (balance < -1 && key < node->right->key) { // 右左情况node->right = rightRotate(node->right);return leftRotate(node);}return node; // 返回未变的节点
}// 中序遍历
void inOrder(Node* root) {if (root) {inOrder(root->left);std::cout << root->key << " ";inOrder(root->right);}
}int main() {Node* root = nullptr;// 插入节点root = insert(root, 10);root = insert(root, 20);root = insert(root, 30);root = insert(root, 40);root = insert(root, 50);root = insert(root, 25);// 打印中序遍历结果std::cout << "中序遍历结果：" << std::endl;inOrder(root);return 0;
}