您好,登录后才能下订单哦!
AVL树是一种自平衡的二叉搜索树(BST),由Adelson-Velsky和Landis在1962年提出。AVL树通过维护每个节点的平衡因子(即左子树高度与右子树高度的差值)来确保树的高度始终保持在O(log n)范围内,从而保证查找、插入和删除操作的时间复杂度为O(log n)。
首先,我们定义一个表示AVL树节点的类AVLNode
:
class AVLNode {
int key;
int height;
AVLNode left;
AVLNode right;
AVLNode(int key) {
this.key = key;
this.height = 1;
this.left = null;
this.right = null;
}
}
为了计算节点的平衡因子,我们需要一个辅助方法来获取节点的高度:
int height(AVLNode node) {
if (node == null) {
return 0;
}
return node.height;
}
int getBalance(AVLNode node) {
if (node == null) {
return 0;
}
return height(node.left) - height(node.right);
}
AVL树的旋转操作包括左旋和右旋:
AVLNode rightRotate(AVLNode y) {
AVLNode x = y.left;
AVLNode T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
AVLNode leftRotate(AVLNode x) {
AVLNode y = x.right;
AVLNode T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
插入操作首先按照二叉搜索树的规则插入节点,然后更新节点的高度并检查平衡因子。如果树失去平衡,则进行相应的旋转操作:
AVLNode insert(AVLNode node, int key) {
if (node == null) {
return new AVLNode(key);
}
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
} else {
return node; // 不允许插入重复的键
}
node.height = 1 + Math.max(height(node.left), height(node.right));
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;
}
删除操作与插入操作类似,首先按照二叉搜索树的规则删除节点,然后更新节点的高度并检查平衡因子。如果树失去平衡,则进行相应的旋转操作:
AVLNode deleteNode(AVLNode root, int key) {
if (root == null) {
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 == null) || (root.right == null)) {
AVLNode temp = null;
if (temp == root.left) {
temp = root.right;
} else {
temp = root.left;
}
if (temp == null) {
temp = root;
root = null;
} else {
root = temp;
}
} else {
AVLNode temp = minValueNode(root.right);
root.key = temp.key;
root.right = deleteNode(root.right, temp.key);
}
}
if (root == null) {
return root;
}
root.height = Math.max(height(root.left), height(root.right)) + 1;
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;
}
AVLNode minValueNode(AVLNode node) {
AVLNode current = node;
while (current.left != null) {
current = current.left;
}
return current;
}
假设我们有一个空的AVL树,依次插入以下键值:10, 20, 30, 40, 50, 25。插入过程如下:
最终,AVL树的结构如下:
30
/ \
20 40
/ \ \
10 25 50
AVL树通过维护每个节点的平衡因子来确保树的高度始终保持在O(log n)范围内,从而保证了查找、插入和删除操作的高效性。通过旋转操作,AVL树能够在插入或删除节点后迅速恢复平衡。本文通过Java代码实现了AVL树的基本操作,并通过实例分析了插入过程。AVL树在需要频繁插入和删除操作的场景中具有重要的应用价值。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。