AVL 树
第一种发明的自平衡二叉搜索树是 AVL 树。AVL 树的名称取自其发明者 Adelson-Velsky 和 Landis 的名字。
在 AVL 树中，左右子树的高度差（称为平衡因子）必须最大为 1。一旦差值超过 1，树就会自动执行平衡算法，直到差值再次变为 1。
平衡因子 = 高度（左子树） - 高度（右子树）
AVL 树的平衡算法中通常有四种旋转情况：LL、RR、LR、RL。
LL 旋转
当节点插入右子树导致树不平衡时，会执行 LL 旋转。这是一个简单的左旋转，可以使树再次平衡 −
图：LL 旋转
发生不平衡的节点将成为左子树，新添加的节点将成为右子树，中间节点将成为父节点。
RR 旋转
当节点插入左子树导致树不平衡时，会执行 RR 旋转。这是一个单次右旋转，可以使树再次平衡 −
图：RR 旋转
发生不平衡的节点将成为右子节点，新添加的节点将成为左子节点，中间节点将成为父节点。
LR 旋转
LR 旋转是之前单次旋转的扩展版本，也称为双旋转。当将节点插入左子树的右子树时，会执行此操作。LR 旋转是左旋转和右旋转的组合。执行此操作需要遵循多个步骤。
考虑一个示例，其中"A"为根节点，"B"为"A"的左子节点，"C"为"B"的右子节点。
由于不平衡发生在 A 处，因此对 A 的子节点（即 B 和 C）进行左旋转。
旋转后，C 节点成为 A 的左子节点，B 成为 C 的左子节点。
不平衡仍然存在，因此对根节点 A 和左子节点 C 进行右旋转。
最终右旋转后，C 成为根节点，A 成为右子节点，B 成为左子节点。
图：LR 旋转
RL 旋转
RL 旋转也是之前单旋转的扩展版本，因此它被称为双旋转，当一个节点插入到右子树的左子树时，就会执行双旋转。RL 旋转是右旋转和左旋转的组合。要执行此操作，需要遵循多个步骤。
考虑一个示例，其中"A"为根节点，"B"为"A"的右子节点，"C"为"B"的左子节点。
由于不平衡发生在 A 处，因此对 A 的子节点（即 B 和 C）进行右旋转。
旋转后，C 节点成为 A 的右子节点，B 成为 C 的右子节点。
不平衡仍然存在，因此对根节点 A 和右子节点 C 进行左旋转。
最后一次左旋转后，C 成为根节点，A 成为左子节点，B 成为右子节点。
图：RL 旋转
AVL 树的基本操作
AVL 树结构上执行的基本操作包括二叉搜索树上执行的所有操作，因为 AVL 树的核心实际上就是一棵保留其所有属性的二叉搜索树。因此，AVL 树上执行的基本操作包括 − 插入 和 删除。
插入操作
数据插入 AVL 树遵循二叉搜索树的插入属性，即左子树必须包含小于根值的元素，右子树必须包含所有大于根值的元素。
然而，在 AVL 树中，每次插入元素后都会检查树的平衡因子；如果平衡因子不超过 1，则保持树的平衡。如果平衡因子超过 1，则会应用平衡算法重新调整树，使平衡因子再次小于或等于 1。
算法执行 AVL 树的插入操作涉及以下步骤 −
步骤 1 − 创建一个节点 步骤 2 − 检查树是否为空 步骤 3 − 如果树为空，则创建的新节点将成为 AVL 树的根节点。 步骤 4 − 如果树不为空，我们执行二叉搜索树的插入操作，并检查该节点在树中的平衡因子。 步骤 5 −假设平衡因子超过±1，我们对该节点进行适当的 旋转，并从步骤4继续插入操作。
通过构建一个包含1到7个整数的示例AVL树来理解插入操作。
从第一个元素1开始，创建一个节点并测量其平衡度，即0。
由于二分查找属性和平衡因子都满足，我们将另一个元素插入树中。
计算两个节点的平衡因子，发现其为-1（左子树的高度为0，右子树的高度为1）。由于它不超过 1，我们向树中添加另一个元素。
现在，添加第三个元素后，平衡因子超过 1，变为 2。因此，需要进行旋转。在本例中，由于不平衡发生在两个右侧节点，因此应用了 RR 旋转。
树被重新排列为 −
同样，插入下一个元素并使用这些旋转重新排列。重新排列后，我们得到的树为 −
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *leftChild;
struct Node *rightChild;
int height;
};
int max(int a, int b);
int height(struct Node *N){
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b){
return (a > b) ? a : b;
}
struct Node *newNode(int data){
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
node->data = data;
node->leftChild = NULL;
node->rightChild = NULL;
node->height = 1;
return (node);
}
struct Node *rightRotate(struct Node *y){
struct Node *x = y->leftChild;
struct Node *T2 = x->rightChild;
x->rightChild = y;
y->leftChild = T2;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
return x;
}
struct Node *leftRotate(struct Node *x){
struct Node *y = x->rightChild;
struct Node *T2 = y->leftChild;
y->leftChild = x;
x->rightChild = T2;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
return y;
}
int getBalance(struct Node *N){
if (N == NULL)
return 0;
return height(N->leftChild) - height(N->rightChild);
}
struct Node *insertNode(struct Node *node, int data){
if (node == NULL)
return (newNode(data));
if (data < node->data)
node->leftChild = insertNode(node->leftChild, data);
else if (data > node->data)
node->rightChild = insertNode(node->rightChild, data);
else
return node;
node->height = 1 + max(height(node->leftChild),
height(node->rightChild));
int balance = getBalance(node);
if (balance > 1 && data < node->leftChild->data)
return rightRotate(node);
if (balance < -1 && data > node->rightChild->data)
return leftRotate(node);
if (balance > 1 && data > node->leftChild->data) {
node->leftChild = leftRotate(node->leftChild);
return rightRotate(node);
}
if (balance < -1 && data < node->rightChild->data) {
node->rightChild = rightRotate(node->rightChild);
return leftRotate(node);
}
return node;
}
struct Node *minValueNode(struct Node *node){
struct Node *current = node;
while (current->leftChild != NULL)
current = current->leftChild;
return current;
}
void printTree(struct Node *root){
if (root == NULL)
return;
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->rightChild);
}
}
int main(){
struct Node *root = NULL;
root = insertNode(root, 22);
root = insertNode(root, 14);
root = insertNode(root, 72);
root = insertNode(root, 44);
root = insertNode(root, 25);
root = insertNode(root, 63);
root = insertNode(root, 98);
printf("AVL Tree: ");
printTree(root);
return 0;
}
输出
AVL Tree: 14 22 25 44 63 72 98
#include <iostream>
struct Node {
int data;
struct Node *leftChild;
struct Node *rightChild;
int height;
};
int max(int a, int b);
int height(struct Node *N){
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b){
return (a > b) ? a : b;
}
struct Node *newNode(int data){
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
node->data = data;
node->leftChild = NULL;
node->rightChild = NULL;
node->height = 1;
return (node);
}
struct Node *rightRotate(struct Node *y){
struct Node *x = y->leftChild;
struct Node *T2 = x->rightChild;
x->rightChild = y;
y->leftChild = T2;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
return x;
}
struct Node *leftRotate(struct Node *x){
struct Node *y = x->rightChild;
struct Node *T2 = y->leftChild;
y->leftChild = x;
x->rightChild = T2;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
return y;
}
int getBalance(struct Node *N){
if (N == NULL)
return 0;
return height(N->leftChild) - height(N->rightChild);
}
struct Node *insertNode(struct Node *node, int data){
if (node == NULL)
return (newNode(data));
if (data < node->data)
node->leftChild = insertNode(node->leftChild, data);
else if (data > node->data)
node->rightChild = insertNode(node->rightChild, data);
else
return node;
node->height = 1 + max(height(node->leftChild),
height(node->rightChild));
int balance = getBalance(node);
if (balance > 1 && data < node->leftChild->data)
return rightRotate(node);
if (balance < -1 && data > node->rightChild->data)
return leftRotate(node);
if (balance > 1 && data > node->leftChild->data) {
node->leftChild = leftRotate(node->leftChild);
return rightRotate(node);
}
if (balance < -1 && data < node->rightChild->data) {
node->rightChild = rightRotate(node->rightChild);
return leftRotate(node);
}
return node;
}
struct Node *minValueNode(struct Node *node){
struct Node *current = node;
while (current->leftChild != NULL)
current = current->leftChild;
return current;
}
void printTree(struct Node *root){
if (root == NULL)
return;
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->leftChild);
}
}
int main(){
struct Node *root = NULL;
root = insertNode(root, 22);
root = insertNode(root, 14);
root = insertNode(root, 72);
root = insertNode(root, 44);
root = insertNode(root, 25);
root = insertNode(root, 63);
root = insertNode(root, 98);
printf("AVL Tree: ");
printTree(root);
return 0;
}
输出
AVL Tree: 14 22 14 44 14 22 14
import java.util.*;
import java.io.*;
class Node {
int key, height;
Node left, right;
Node (int d) {
key = d;
height = 1;
}
}
public class AVLTree {
Node root;
int height (Node N) {
if (N == null)
return 0;
return N.height;
}
int max (int a, int b) {
return (a > b) ? a : b;
}
Node rightRotate (Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = max (height (y.left), height (y.right)) + 1;
x.height = 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 = max (height (x.left), height (x.right)) + 1;
y.height = max (height (y.left), height (y.right)) + 1;
return y;
}
int getBalance (Node N) {
if (N == null)
return 0;
return height (N.left) - height (N.right);
}
Node insert (Node node, int key) {
if (node == null)
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);
else
return node;
node.height = 1 + 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;
}
void printTree(Node root){
if (root == null)
return;
if (root != null) {
printTree(root.left);
System.out.print(root.key + " ");
printTree(root.left);
}
}
public static void main(String args[]) {
AVLTree tree = new AVLTree();
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 11);
tree.root = tree.insert(tree.root, 12);
tree.root = tree.insert(tree.root, 13);
tree.root = tree.insert(tree.root, 14);
tree.root = tree.insert(tree.root, 15);
System.out.println("AVL Tree: ");
tree.printTree(tree.root);
}
}
输出
AVL Tree: 10 11 10 13 10 11 10
class Node(object):
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1
class AVLTree(object):
def insert(self, root, key):
if not root:
return Node(key)
elif key < root.data:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
root.h = 1 + max(self.getHeight(root.left),
self.getHeight(root.right))
b = self.getBalance(root)
if b > 1 and key < root.left.data:
return self.rightRotate(root)
if b < -1 and key > root.right.data:
return self.leftRotate(root)
if b > 1 and key > root.left.data:
root.left = self.lefttRotate(root.left)
return self.rightRotate(root)
if b < -1 and key < root.right.data:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def leftRotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.getHeight(z.left),
self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left),
self.getHeight(y.right))
return y
def rightRotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.getHeight(z.left),
self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left),
self.getHeight(y.right))
return y
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
def Inorder(self, root):
if root.left:
self.Inorder(root.left)
print(root.data)
if root.right:
self.Inorder(root.right)
Tree = AVLTree()
root = None
root = Tree.insert(root, 10)
root = Tree.insert(root, 13)
root = Tree.insert(root, 11)
root = Tree.insert(root, 14)
root = Tree.insert(root, 12)
root = Tree.insert(root, 15)
# 中序遍历
print("Inorder traversal of the AVL tree is")
Tree.Inorder(root)
输出
Inorder traversal of the AVL tree is 10 11 12 13 14 15
删除操作
AVL 树中的删除操作有三种不同的场景 −
场景 1（删除叶子节点） − 如果要删除的节点是叶子节点，则直接删除，无需替换，因为这不会破坏二叉搜索树的性质。但是，平衡因子可能会受到干扰，因此需要进行旋转操作来恢复平衡因子。
场景 2（删除只有一个子节点的节点） − 如果要删除的节点只有一个子节点，则将该节点的值替换为其子节点的值。然后删除该子节点。如果平衡因子受到干扰，则需要进行旋转操作。
场景 3（删除有两个子节点的节点） −如果待删除节点有两个子节点，则找到该节点的中序后继节点，并将其值替换为中序后继节点的值。然后尝试删除该中序后继节点。如果删除后平衡因子超过 1，则应用平衡算法。
使用上面给出的同一棵树，让我们在三种情况下执行删除操作 −
从上面的树中删除元素 7 −
由于元素 7 是叶子节点，我们通常会在不干扰树中任何其他节点的情况下删除该元素。
从输出树中删除元素 6 达到 −
但是，元素 6 不是叶节点，并且有一个子节点附加到它的节点。在本例中，我们将节点 6 替换为其子节点：节点 5。
树的平衡度变为 1，由于它不超过 1，因此树保持原样。如果我们进一步删除元素 5，则必须应用左旋转；由于不平衡发生在路径 1-2-4 和 3-2-4 上，因此要么是 LL 旋转，要么是 LR 旋转。
删除元素 5 后，平衡因子被打乱，因此我们应用 LL 旋转（我们也可以在此处应用 LR 旋转）。
在路径 1-2-4 上应用 LL 旋转后，节点 3 仍然保持其应有的状态，即节点 2 的右子节点（现在由节点 4 占据）。因此，该节点被添加到节点 2 的右子树中，并作为节点 4 的左子节点。
从剩余的树中删除元素 2 −
如场景 3 中所述，该节点有两个子节点。因此，我们找到它的中序后继，即一个叶节点（例如 3），并将其值替换为中序后继。
树的平衡值仍然为 1，因此我们保持树的原样，不进行任何旋转。
示例以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *leftChild;
struct Node *rightChild;
int height;
};
int max(int a, int b);
int height(struct Node *N){
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b){
return (a > b) ? a : b;
}
struct Node *newNode(int data){
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
node->data = data;
node->leftChild = NULL;
node->rightChild = NULL;
node->height = 1;
return (node);
}
struct Node *rightRotate(struct Node *y){
struct Node *x = y->leftChild;
struct Node *T2 = x->rightChild;
x->rightChild = y;
y->leftChild = T2;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
return x;
}
struct Node *leftRotate(struct Node *x){
struct Node *y = x->rightChild;
struct Node *T2 = y->leftChild;
y->leftChild = x;
x->rightChild = T2;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
return y;
}
int getBalance(struct Node *N){
if (N == NULL)
return 0;
return height(N->leftChild) - height(N->rightChild);
}
struct Node *insertNode(struct Node *node, int data){
if (node == NULL)
return (newNode(data));
if (data < node->data)
node->leftChild = insertNode(node->leftChild, data);
else if (data > node->data)
node->rightChild = insertNode(node->rightChild, data);
else
return node;
node->height = 1 + max(height(node->leftChild),
height(node->rightChild));
int balance = getBalance(node);
if (balance > 1 && data < node->leftChild->data)
return rightRotate(node);
if (balance < -1 && data > node->rightChild->data)
return leftRotate(node);
if (balance > 1 && data > node->leftChild->data) {
node->leftChild = leftRotate(node->leftChild);
return rightRotate(node);
}
if (balance < -1 && data < node->rightChild->data) {
node->rightChild = rightRotate(node->rightChild);
return leftRotate(node);
}
return node;
}
struct Node *minValueNode(struct Node *node){
struct Node *current = node;
while (current->leftChild != NULL)
current = current->leftChild;
return current;
}
struct Node *deleteNode(struct Node *root, int data){
if (root == NULL)
return root;
if (data < root->data)
root->leftChild = deleteNode(root->leftChild, data);
else if (data > root->data)
root->rightChild = deleteNode(root->rightChild, data);
else {
if ((root->leftChild == NULL) || (root->rightChild == NULL)) {
struct Node *temp = root->leftChild ? root->leftChild : root->rightChild;
if (temp == NULL) {
temp = root;
root = NULL;
} else
*root = *temp;
free(temp);
} else {
struct Node *temp = minValueNode(root->rightChild);
root->data = temp->data;
root->rightChild = deleteNode(root->rightChild, temp->data);
}
}
if (root == NULL)
return root;
root->height = 1 + max(height(root->leftChild),
height(root->rightChild));
int balance = getBalance(root);
if (balance > 1 && getBalance(root->leftChild) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root->leftChild) < 0) {
root->leftChild = leftRotate(root->leftChild);
return rightRotate(root);
}
if (balance < -1 && getBalance(root->rightChild) <= 0)
return leftRotate(root);
if (balance < -1 && getBalance(root->rightChild) > 0) {
root->rightChild = rightRotate(root->rightChild);
return leftRotate(root);
}
return root;
}
// Print the tree
void printTree(struct Node *root){
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->rightChild);
}
}
int main(){
struct Node *root = NULL;
root = insertNode(root, 22);
root = insertNode(root, 14);
root = insertNode(root, 72);
root = insertNode(root, 44);
root = insertNode(root, 25);
root = insertNode(root, 63);
root = insertNode(root, 98);
printf("AVL Tree: ");
printTree(root);
root = deleteNode(root, 25);
printf("
After deletion: ");
printTree(root);
return 0;
}
输出
AVL Tree: 14 22 25 44 63 72 98 After deletion: 14 22 44 63 72 98
#include <iostream>
struct Node {
int data;
struct Node *leftChild;
struct Node *rightChild;
int height;
};
int max(int a, int b);
int height(struct Node *N){
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b){
return (a > b) ? a : b;
}
struct Node *newNode(int data){
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
node->data = data;
node->leftChild = NULL;
node->rightChild = NULL;
node->height = 1;
return (node);
}
struct Node *rightRotate(struct Node *y){
struct Node *x = y->leftChild;
struct Node *T2 = x->rightChild;
x->rightChild = y;
y->leftChild = T2;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
return x;
}
struct Node *leftRotate(struct Node *x){
struct Node *y = x->rightChild;
struct Node *T2 = y->leftChild;
y->leftChild = x;
x->rightChild = T2;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
return y;
}
int getBalance(struct Node *N){
if (N == NULL)
return 0;
return height(N->leftChild) - height(N->rightChild);
}
struct Node *insertNode(struct Node *node, int data){
if (node == NULL)
return (newNode(data));
if (data < node->data)
node->leftChild = insertNode(node->leftChild, data);
else if (data > node->data)
node->rightChild = insertNode(node->rightChild, data);
else
return node;
node->height = 1 + max(height(node->leftChild),
height(node->rightChild));
int balance = getBalance(node);
if (balance > 1 && data < node->leftChild->data)
return rightRotate(node);
if (balance < -1 && data > node->rightChild->data)
return leftRotate(node);
if (balance > 1 && data > node->leftChild->data) {
node->leftChild = leftRotate(node->leftChild);
return rightRotate(node);
}
if (balance < -1 && data < node->rightChild->data) {
node->rightChild = rightRotate(node->rightChild);
return leftRotate(node);
}
return node;
}
struct Node *minValueNode(struct Node *node){
struct Node *current = node;
while (current->leftChild != NULL)
current = current->leftChild;
return current;
}
struct Node *deleteNode(struct Node *root, int data){
if (root == NULL)
return root;
if (data < root->data)
root->leftChild = deleteNode(root->leftChild, data);
else if (data > root->data)
root->rightChild = deleteNode(root->rightChild, data);
else {
if ((root->leftChild == NULL) || (root->rightChild == NULL)) {
struct Node *temp = root->leftChild ? root->leftChild : root->rightChild;
if (temp == NULL) {
temp = root;
root = NULL;
} else
*root = *temp;
free(temp);
} else {
struct Node *temp = minValueNode(root->rightChild);
root->data = temp->data;
root->rightChild = deleteNode(root->rightChild, temp->data);
}
}
if (root == NULL)
return root;
root->height = 1 + max(height(root->leftChild),
height(root->rightChild));
int balance = getBalance(root);
if (balance > 1 && getBalance(root->leftChild) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root->leftChild) < 0) {
root->leftChild = leftRotate(root->leftChild);
return rightRotate(root);
}
if (balance < -1 && getBalance(root->rightChild) <= 0)
return leftRotate(root);
if (balance < -1 && getBalance(root->rightChild) > 0) {
root->rightChild = rightRotate(root->rightChild);
return leftRotate(root);
}
return root;
}
// 打印树
void printTree(struct Node *root){
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->rightChild);
}
}
int main(){
struct Node *root = NULL;
root = insertNode(root, 22);
root = insertNode(root, 14);
root = insertNode(root, 72);
root = insertNode(root, 44);
root = insertNode(root, 25);
root = insertNode(root, 63);
root = insertNode(root, 98);
printf("AVL Tree: ");
printTree(root);
root = deleteNode(root, 25);
printf("
After deletion: ");
printTree(root);
return 0;
}
输出
AVL Tree: 14 22 25 44 63 72 98 After deletion: 14 22 44 63 72 98
import java.util.*;
import java.io.*;
class Node {
int key, height;
Node left, right;
Node (int d) {
key = d;
height = 1;
}
}
public class AVLTree {
Node root;
int height (Node N) {
if (N == null)
return 0;
return N.height;
}
int max (int a, int b) {
return (a > b) ? a : b;
}
Node rightRotate (Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = max (height (y.left), height (y.right)) + 1;
x.height = 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 = max (height (x.left), height (x.right)) + 1;
y.height = max (height (y.left), height (y.right)) + 1;
return y;
}
int getBalance (Node N) {
if (N == null)
return 0;
return height (N.left) - height (N.right);
}
Node minValueNode (Node node) {
Node current = node;
while (current.left != null)
current = current.left;
return current;
}
Node deleteNode (Node 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)) {
Node temp = null;
if (temp == root.left)
temp = root.right;
else
temp = root.left;
if (temp == null) {
temp = root;
root = null;
} else
root = temp;
} else {
Node temp = minValueNode (root.right);
root.key = temp.key;
root.right = deleteNode (root.right, temp.key);
}
}
if (root == null)
return root;
root.height = 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;
}
public void printTree(Node root) {
if (root == null) return;
printTree(root.left);
System.out.print(root.key + " ");
printTree(root.right);
}
public static void main (String[]args) {
AVLTree tree = new AVLTree();
tree.root = new Node(13);
tree.root.left = new Node(12);
tree.root.left.left = new Node(11);
tree.root.left.left.left = new Node(10);
tree.root.right = new Node(14);
tree.root.right.right = new Node(15);
System.out.print("AVL Tree: ");
tree.printTree(tree.root);
tree.root = tree.deleteNode (tree.root, 10);
System.out.print("
After deletion: ");
tree.printTree(tree.root);
System.out.println ("");
}
}
输出
AVL Tree: 10 11 12 13 14 15 After deletion: 11 12 13 14 15
class Node(object):
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1
class AVLTree(object):
def insert(self, root, key):
if not root:
return Node(key)
elif key < root.data:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
root.h = 1 + max(self.getHeight(root.left),
self.getHeight(root.right))
b = self.getBalance(root)
if b > 1 and key < root.left.data:
return self.rightRotate(root)
if b < -1 and key > root.right.data:
return self.leftRotate(root)
if b > 1 and key > root.left.data:
root.left = self.lefttRotate(root.left)
return self.rightRotate(root)
if b < -1 and key < root.right.data:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def delete(self, root, key):
if not root:
return root
elif key < root.data:
root.left = self.delete(root.left, key)
elif key > root.data:
root.right = self.delete(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.getMindataueNode(root.right)
root.data = temp.data
root.right = self.delete(root.right, temp.data)
if root is None:
return root
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
balance = self.getBalance(root)
if balance > 1 and self.getBalance(root.left) >= 0:
return self.rightRotate(root)
if balance < -1 and self.getBalance(root.right) <= 0:
return self.leftRotate(root)
if balance > 1 and self.getBalance(root.left) < 0:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balance < -1 and self.getBalance(root.right) > 0:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def leftRotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.getHeight(z.left),
self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left),
self.getHeight(y.right))
return y
def rightRotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.getHeight(z.left),
self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left),
self.getHeight(y.right))
return y
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
def Inorder(self, root):
if root.left:
self.Inorder(root.left)
print(root.data, end = " ")
if root.right:
self.Inorder(root.right)
Tree = AVLTree()
root = None
root = Tree.insert(root, 10)
root = Tree.insert(root, 13)
root = Tree.insert(root, 11)
root = Tree.insert(root, 14)
root = Tree.insert(root, 12)
root = Tree.insert(root, 15)
# 中序遍历
print("AVL Tree: ")
Tree.Inorder(root)
root = Tree.delete(root, 14)
print("
After deletion: ")
Tree.Inorder(root)
输出
AVL Tree: 10 11 12 13 14 15 After deletion: 10 11 12 13 15
