- 数据结构与算法
- DSA - 主页
- DSA - 概述
- DSA - 环境设置
- 数据结构
- DSA - 数据结构基础知识
- DSA - 数据结构和类型
- DSA - 数组数据结构
- 链表
- DSA - 链表基础知识
- DSA - 双向链表
- DSA - 循环链表
- 堆栈和队列
- DSA - 堆栈
- DSA - 表达式解析
- DSA-队列
- 图数据结构
- DSA - 图数据结构
- DSA-深度优先遍历
- DSA-广度优先遍历
- DSA——生成树
- 树数据结构
- DSA - 树数据结构
- DSA - 树遍历
- DSA - 二叉搜索树
- DSA - AVL 树
- DSA - 红黑树
- DSA - B 树
- DSA - B+ 树
- DSA - 八字树
- DSA - 尝试
- DSA-堆
- 递归
- DSA - 递归基础知识
- DSA - 河内塔
- DSA - 斐波那契数列
- DSA 有用资源
- DSA - 问题与解答
- DSA - 快速指南
- DSA - 有用的资源
- DSA - 讨论
数据结构和算法 - AVL 树
第一种被发明的自平衡二叉搜索树是AVL树。AVL 树这个名字是根据其发明者的名字——Adelson-Velsky 和 Landis 创造的。
在 AVL 树中，左右子树的高度之差（称为平衡因子）最多只能为 1。一旦差值超过1，树就会自动执行平衡算法，直到差值再次变为1。
BALANCE FACTOR = HEIGHT(LEFT SUBTREE) – HEIGHT(RIGHT SUBTREE)
AVL树的平衡算法中旋转通常有四种情况：LL、RR、LR、RL。
LL 旋转
当节点插入到导致不平衡树的右子树时，会执行 LL 旋转。这是一次左旋转，使树再次平衡 -
图：LL 旋转
发生不平衡的节点成为左子节点，新添加的节点成为右子节点，中间节点为父节点。
RR 轮换
当节点插入到导致不平衡树的左子树时，会执行 RR 旋转。这是一次右旋转，使树再次平衡 -
图：RR 旋转
发生不平衡的节点成为右子节点，新添加的节点成为左子节点，中间节点为父节点。
左右旋转
LR旋转是之前单旋转的扩展版本，也称为双旋转。当一个节点插入左子树的右子树时执行。LR 旋转是左旋转和右旋转的组合。执行此操作需要遵循多个步骤。
考虑一个示例，其中“A”作为根节点，“B”作为“A”的左子节点，“C”作为“B”的右子节点。
由于不平衡发生在 A 处，因此对 A 的子节点（即 B 和 C）应用左旋转。
旋转后，C 节点成为 A 的左子节点，B 成为 C 的左子节点。
不平衡仍然存在，因此在根节点 A 和左子节点 C 处应用右旋转。
最终右旋后，C成为根节点，A成为右子节点，B成为左子节点。
图：左右旋转
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 恢复插入。
START
if node == null then:
return new node
if key < node.key then:
node.left = insert (node.left, key)
else if (key > node.key) then:
node.right = insert (node.right, key)
else
return node
node.height = 1 + max (height (node.left), height (node.right))
balance = getBalance (node)
if balance > 1 and key < node.left.key then:
rightRotate
if balance < -1 and key > node.right.key then:
leftRotate
if balance > 1 and key > node.left.key then:
node.left = leftRotate (node.left)
rightRotate
if balance < -1 and key < node.right.key then:
node.right = rightRotate (node.right)
leftRotate (node)
return node
END
插入示例
让我们通过构造一个包含 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)
# Inorder Traversal
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，则应用平衡算法。
START
if root == null: return root
if key < root.key:
root.left = delete Node
else if key > root.key:
root.right = delete Node
else:
if root.left == null or root.right == null then:
Node temp = null
if (temp == root.left)
temp = root.right
else
temp = root.left
if temp == null then:
temp = root
root = null
else
root = temp
else:
temp = minimum valued node
root.key = temp.key
root.right = delete Node
if (root == null) then:
return root
root.height = max (height (root.left), height (root.right)) + 1
balance = getBalance
if balance > 1 and getBalance (root.left) >= 0:
rightRotate
if balance > 1 and getBalance (root.left) < 0:
root.left = leftRotate (root.left);
rightRotate
if balance < -1 and getBalance (root.right) <= 0:
leftRotate
if balance < -1 and getBalance (root.right) > 0:
root.right = rightRotate (root.right);
leftRotate
return root
END
删除示例
使用上面给出的同一棵树，让我们在三种情况下执行删除 -
从上面的树中删除元素 7 -
由于元素 7 是叶子，因此我们通常删除该元素而不干扰树中的任何其他节点
从输出树中删除元素 6 实现 -
然而，元素 6 不是叶节点，并且有一个子节点附加到它。在本例中，我们将节点 6 替换为其子节点：节点 5。
树的平衡性变为 1，并且由于它不超过 1，所以树保持原样。如果我们进一步删除元素 5，我们将不得不应用左旋转；LL 或 LR，因为不平衡发生在 1-2-4 和 3-2-4 处。
删除元素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("\nAfter 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;
}
// 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("\nAfter 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.println("The AVL Tree is: ");
tree.printTree(tree.root);
tree.root = tree.deleteNode (tree.root, 10);
System.out.println("\n----------------------------------------------\n");
System.out.println("The AVL Tree after deleting 10 is: ");
tree.printTree(tree.root);
System.out.println ("");
}
}
输出
The AVL Tree is: 10 11 12 13 14 15 ---------------------------------------------- The AVL Tree after deleting 10 is: 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)
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)
# Inorder Traversal
print("Inorder traversal of the AVL tree is")
Tree.Inorder(root)
root = Tree.delete(root, 14)
print("Inorder traversal of the modified AVL tree is")
Tree.Inorder(root)
输出
Inorder traversal of the AVL tree is 10 11 12 13 14 15 Inorder traversal of the modified AVL tree is 10 11 12 13 15
AVL树的实现
在下面的实现中，我们按升序考虑输入，并通过计算平衡因子和应用旋转将它们存储在 AVL 树中。
例子
以下是此操作在各种编程语言中的实现 -
#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("\nAfter 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;
}
// 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("\nAfter 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 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;
}
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.println(root.key);
printTree(root.right);
}
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("The AVL Tree is: ");
tree.printTree(tree.root);
tree.root = tree.deleteNode (tree.root, 10);
System.out.println("\n----------------------------------------------\n");
System.out.println("The AVL Tree after deleting 10 is: ");
tree.printTree(tree.root);
System.out.println ("");
}
}
输出
The AVL Tree is: 10 11 12 13 14 15 ---------------------------------------------- The AVL Tree after deleting 10 is: 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)
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)
# Inorder Traversal
print("Inorder traversal of the AVL tree is")
Tree.Inorder(root)
root = Tree.delete(root, 14)
print("Inorder traversal of the modified AVL tree is")
Tree.Inorder(root)
输出
Inorder traversal of the AVL tree is 10 11 12 13 14 15 Inorder traversal of the modified AVL tree is 10 11 12 13 15