平衡二叉树的应用举例

AVL 是一种自平衡二叉搜索树，其中任何节点的左右子树的高度之差不能超过 1。

AVL树的特点：

1、它遵循二叉搜索树的一般属性。

2、树的每个子树都是平衡的，即左右子树的高度之差最多为1。

3、当插入新节点时，树会自我平衡。因此，插入操作非常耗时。

AVL Tree的应用：

1、大多数内存中集和字典都使用 AVL 树进行存储。

2、数据库应用程序（插入和删除不太常见，但需要频繁的数据查找）也经常使用 AVL 树。

3、除了数据库应用程序之外，它还用于其他需要更好搜索的应用程序。

4、有序关联容器（集合、多集、映射和多映射）的大多数 STL 实现都使用红黑树而不是 AVL树。

#include <stdio.h>
#include <stdlib.h>struct AVLnode
{int key;struct AVLnode *left;struct AVLnode *right;int height;
};
typedef struct AVLnode avlNode;int max(int a, int b) { return (a > b) ? a : b; }avlNode *newNode(int key)
{avlNode *node = (avlNode *)malloc(sizeof(avlNode));if (node == NULL)printf("!! Out of Space !!\n");else{node->key = key;node->left = NULL;node->right = NULL;node->height = 0;}return node;
}int nodeHeight(avlNode *node)
{if (node == NULL)return -1;elsereturn (node->height);
}int heightDiff(avlNode *node)
{if (node == NULL)return 0;elsereturn (nodeHeight(node->left) - nodeHeight(node->right));
}/* 返回左子树中最小值的节点*/
avlNode *minNode(avlNode *node)
{avlNode *temp = node;while (temp->left != NULL) temp = temp->left;return temp;
}void printAVL(avlNode *node, int level)
{int i;if (node != NULL){printAVL(node->right, level + 1);printf("\n\n");for (i = 0; i < level; i++) printf("\t");printf("%d", node->key);printAVL(node->left, level + 1);}
}avlNode *rightRotate(avlNode *z)
{avlNode *y = z->left;avlNode *T3 = y->right;y->right = z;z->left = T3;z->height = (max(nodeHeight(z->left), nodeHeight(z->right)) + 1);y->height = (max(nodeHeight(y->left), nodeHeight(y->right)) + 1);return y;
}avlNode *leftRotate(avlNode *z)
{avlNode *y = z->right;avlNode *T3 = y->left;y->left = z;z->right = T3;z->height = (max(nodeHeight(z->left), nodeHeight(z->right)) + 1);y->height = (max(nodeHeight(y->left), nodeHeight(y->right)) + 1);return y;
}avlNode *LeftRightRotate(avlNode *z)
{z->left = leftRotate(z->left);return (rightRotate(z));
}avlNode *RightLeftRotate(avlNode *z)
{z->right = rightRotate(z->right);return (leftRotate(z));
}avlNode *insert(avlNode *node, int key)
{if (node == NULL)return (newNode(key));/*二叉搜索树插入*/if (key < node->key)node->left =insert(node->left, key); /*递归插入左子树*/else if (key > node->key)node->right =insert(node->right, key); /*递归插入右子树*//*计算节点高度*/node->height = (max(nodeHeight(node->left), nodeHeight(node->right)) + 1);/*检查平衡性*/int balance = heightDiff(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 = LeftRightRotate(node);}/*右左*/if (balance < -1 && key < (node->right->key)){node = RightLeftRotate(node);}return node;
}avlNode *delete (avlNode *node, int queryNum)
{if (node == NULL)return node;if (queryNum < node->key)node->left =delete (node->left, queryNum); /*Recursive deletion in L subtree*/else if (queryNum > node->key)node->right =delete (node->right, queryNum); /*Recursive deletion in R subtree*/else{/*单节点或者没有子节点*/if ((node->left == NULL) || (node->right == NULL)){avlNode *temp = node->left ? node->left : node->right;/*没有子节点*/if (temp == NULL){temp = node;node = NULL;}else /*单节点*/*node = *temp;free(temp);}else{/*两个孩子节点*//*获取右子树最小值的节点*/avlNode *temp = minNode(node->right);node->key = temp->key; /*拷贝到根节点*/node->right =delete (node->right,temp->key); /*删除右子树最小值的节点*/}}/*单节点*/if (node == NULL)return node;/*更新高度*/node->height = (max(nodeHeight(node->left), nodeHeight(node->right)) + 1);int balance = heightDiff(node);/*左左*/if ((balance > 1) && (heightDiff(node->left) >= 0))return rightRotate(node);/*左右*/if ((balance > 1) && (heightDiff(node->left) < 0)){node = LeftRightRotate(node);}/*右右*/if ((balance < -1) && (heightDiff(node->right) >= 0))return leftRotate(node);/*右左*/if ((balance < -1) && (heightDiff(node->right) < 0)){node = RightLeftRotate(node);}return node;
}avlNode *findNode(avlNode *node, int queryNum)
{if (node != NULL){if (queryNum < node->key)node = findNode(node->left, queryNum);else if (queryNum > node->key)node = findNode(node->right, queryNum);}return node;
}void printPreOrder(avlNode *node)
{if (node == NULL)return;printf("  %d  ", (node->key));printPreOrder(node->left);printPreOrder(node->right);
}void printInOrder(avlNode *node)
{if (node == NULL)return;printInOrder(node->left);printf("  %d  ", (node->key));printInOrder(node->right);
}void printPostOrder(avlNode *node)
{if (node == NULL)return;printPostOrder(node->left);printPostOrder(node->right);printf("  %d  ", (node->key));
}int main()
{int choice;int flag = 1;int insertNum;int queryNum;avlNode *root = NULL;avlNode *tempNode;while (flag == 1){printf("\n\nEnter the Step to Run : \n");printf("\t1: Insert a node into AVL tree\n");printf("\t2: Delete a node in AVL tree\n");printf("\t3: Search a node into AVL tree\n");printf("\t4: printPreOrder (Ro L R) Tree\n");printf("\t5: printInOrder (L Ro R) Tree\n");printf("\t6: printPostOrder (L R Ro) Tree\n");printf("\t7: printAVL Tree\n");printf("\t0: EXIT\n");scanf("%d", &choice);switch (choice){case 0:{flag = 0;printf("\n\t\tExiting, Thank You !!\n");break;}case 1:{printf("\n\tEnter the Number to insert: ");scanf("%d", &insertNum);tempNode = findNode(root, insertNum);if (tempNode != NULL)printf("\n\t %d Already exists in the tree\n", insertNum);else{printf("\n\tPrinting AVL Tree\n");printAVL(root, 1);printf("\n");root = insert(root, insertNum);printf("\n\tPrinting AVL Tree\n");printAVL(root, 1);printf("\n");}break;}case 2:{printf("\n\tEnter the Number to Delete: ");scanf("%d", &queryNum);tempNode = findNode(root, queryNum);if (tempNode == NULL)printf("\n\t %d Does not exist in the tree\n", queryNum);else{printf("\n\tPrinting AVL Tree\n");printAVL(root, 1);printf("\n");root = delete (root, queryNum);printf("\n\tPrinting AVL Tree\n");printAVL(root, 1);printf("\n");}break;}case 3:{printf("\n\tEnter the Number to Search: ");scanf("%d", &queryNum);tempNode = findNode(root, queryNum);if (tempNode == NULL)printf("\n\t %d : Not Found\n", queryNum);else{printf("\n\t %d : Found at height %d \n", queryNum,tempNode->height);printf("\n\tPrinting AVL Tree\n");printAVL(root, 1);printf("\n");}break;}case 4:{printf("\nPrinting Tree preOrder\n");printPreOrder(root);break;}case 5:{printf("\nPrinting Tree inOrder\n");printInOrder(root);break;}case 6:{printf("\nPrinting Tree PostOrder\n");printPostOrder(root);break;}case 7:{printf("\nPrinting AVL Tree\n");printAVL(root, 1);break;}default:{flag = 0;printf("\n\t\tExiting, Thank You !!\n");break;}}}return 0;
}