AVL 树是带有平衡条件的二叉搜索树。当它不平衡时重排其节点让其再度保持平衡。
平衡节点（balanced node）或者说平衡因子（ balance factor）如果节点是平衡树的节点，即它的两颗子树的高度差不大于1，则该节点是平衡的。
BalanceFactor = height(left-sutree) − height(right-sutree)

AVL树的旋转

在AVL树中，每次插入或删除后，则需要检查每个节点的平衡因子，如果每个节点都满足平衡的条件，则可以完成操作，否则需要使用旋转操作重新平衡树。
1.png
旋转分为两种类型，

  • 单旋转
    • 左旋转（LL旋转）
    • 右旋转（RR旋转）
  • 双旋转
    • 左右旋转（LR旋转）
    • 右左旋转（RL旋转）

分别在下列情况下使用

  • 如果左侧子树的右子树存在不平衡则执行左右旋转
  • 如果左侧子树的左子树存在不平衡则执行右旋转
  • 如果右侧子树的右子树存在不平衡则执行坐旋转
  • 如果右侧子树的左子树存在不平衡则执行右左旋转

左旋转（LL旋转）

当一个节点插入到节点A的右子树的右子树位置时，如果树变的不平衡，则执行左旋转。
left.png

  1. Alogrithm rotateLeft(nodeN) //nodeN 就如上图的A节点
  2. //修正给定的节点nodeN的不平衡，因为在nodeN的右子树节点的右子树位置添加了节点C
  4. //将A的右子树赋值给新的变量nodeC 也就是B节点
  5. nodeC = nodeN->rightChild
  6. //将nodeC的左子树赋值给nodeN的右子树 也就是将 将B的左子树赋值给A的右节点
  7. nodeN.rightChild = nodeC.leftChild
  8. //将nodeN赋值给nodeC的左子树 将B 的左子树设置为A
  9. nodeC->leftChild = nodeN
  10. 将nodeC返回 也就是 B
  11. return nodeC

右旋转（RR旋转）

将一个节点插入到节点C的左子树的左子树位置时，AVL树可能变的不平衡，此时需要右旋转
right.png

  1. Alogrithm rotateRight(nodeN) //nodeN 就如上图的C节点
  2. //修正给定的节点nodeN的不平衡，因为在nodeN的左子树节点的右子树位置添加了节点A
  4. //将C的左子树赋值给新的变量nodeC 也就是B节点
  5. nodeC = nodeN->leftChild
  6. //将nodeC的右子树赋值给nodeN的左子树 也就是将 将B的右子树赋值给C的左子树
  7. nodeN.leftChild = nodeC.rightChild
  8. //将nodeN赋值给nodeC的右子树 将B 的右子树设置为C节点
  9. nodeC->rightChild = nodeN
  10. 将nodeC返回 也就是 B
  11. return nodeC

左右旋转（LR旋转）

如果在节点C左子树节点的右子树位置插入节点时，树变的不平衡，则执行左右旋转。左右旋转顾明思义，先左旋转再右旋转
left-right.png

  1. Alogrithm rotateLeftRight(nodeN) nodeN代表上图中的C
  2. //修正给定的节点nodeN的不平衡，因为在nodeNd的左子树节点的右子树位置插入了新节点 B
  4. //将nodeN(C)节点左子树 赋值给一个新的辅助变量nodeC (等于节点A)
  5. nodeC = nodeN->leftChild
  6. //对节点A 进行左旋转，并将返回值赋值给nodeN(C)节点的左子树
  7. nodeN->leftChild = rotateLeft(nodeC);
  8. //再对节点nodeN(C)进行右旋转
  9. return rotateRight(nodeN)

右左旋转（RL旋转）

如果在节点A的右子树的左子树位置插入节点时，树变的不平衡，则执行右左旋转。就是先右旋转再左旋转
right-left.png

  1. Alogrithm rotateRightLeft(nodeN) nodeN代表上图中的A
  2. //修正给定的节点nodeN的不平衡，因为在nodeNd的右子树节点的左子树位置插入了新节点 B
  4. //将nodeN(A)节点的右子树 赋值给一个新的辅助变量nodeC (等于节点C)
  5. nodeC = nodeN->rightChild
  6. //对节点C 进行右旋转，并将返回值赋值给nodeN(A)节点的右子树
  7. nodeN->rightChild = rotateRight(nodeC);
  8. //再对节点nodeN(A)进行左旋转
  9. return rotateRLeft(nodeN)

再平衡算法

  1. Alogrithm rebalance(nodeN)
  2. if(nodeN的左子树的高度与其右子树的高度查大于1)
  3. {
  4.   // 在nodeN的左子树中添加
  5.       if(nodeN的左孩子的左子树高于其右子树){
  6.             rotateRight(nodeN)    //在左孩子的左子树中添加
  7.     }else {
  8.             rotateLeftRight(nodeN) // 在左孩子的右子树中添加
  9.     }
  10. }else if(nodeN的右子树的高度与其左子树的高度差大于1){
  11.       if(nodeN的右孩子的右子树比其左子树高)
  12.         {
  13.         rotateLeft(nodeN)  // 在右孩子的右子树中添加
  14.         }else {
  15.         rotateRightLeft(nodeN) // 在右孩子的左子树中添加
  17.         }
  20. }
  1. #ifndef AVL_TREE_H
  2. #define AVL_TREE_H
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <math.h>
  6. #include <assert.h>
  7. struct AVLNode;
  8. typedef struct AVLNode *AvlNode;
  9. typedef struct AVLNode *AVLTree;
  11. // 创建节点
  12. AVLTree createAvlNode(const int data);
  14. // 查找指定数据的节点
  15. AvlNode find(const int data, const AVLTree tree);
  16. // 查找最小节点
  17. AvlNode findMin(const AVLTree tree);
  18. // 查找最大节点
  19. AvlNode findMax(const AVLTree tree);
  20. // 插入数据
  21. AVLTree insert(const int data, AVLTree tree);
  22. // 删除
  23. AVLTree deleteNode(const int data, AVLTree tree);
  25. // 旋转
  26. // 左旋转（LL旋转）
  27. AVLTree rotateLeft(AVLTree node);
  28. // 右旋转（RR旋转）
  29. AVLTree rotateRight(AVLTree node);
  30. // 右左旋转（RL旋转）
  31. AVLTree rotateRightLeft(AVLTree node);
  32. // 左右旋转（LR旋转）
  33. AVLTree rotateLeftRight(AVLTree node);
  35. // 再平衡 通过旋转让AVL 树再度平衡
  36. AVLTree rebalance(const int data, AVLTree node);
  38. // 节点 struct
  39. struct AVLNode
  40. {
  41.     /* data */
  42.     int data;
  43.     int height;
  44.     AVLTree left;
  45.     AVLTree right;
  46. };
  48. AVLTree createAvlNode(const int data)
  49. {
  50.     AVLTree node = (AVLTree)malloc(sizeof(AVLTree));
  51.     if (node == NULL)
  52.     {
  53.         printf("createAvlNode 内存分配出错！\n");
  54.         exit(EXIT_FAILURE);
  55.     }
  56.     node->data = data;
  57.     node->left = node->right = NULL;
  58.     node->height = 0;
  59.     return node;
  60. };
  61. // 获取avl树的高度
  62. static int height(AvlNode node)
  63. {
  65.     if (node == NULL)
  66.         return -1;
  68.     return node->height;
  69. }
  71. static int maxNumber(const int a, const int b)
  72. {
  73.     return a > b ? a : b;
  74. };
  76. static int getMaxHeight(AVLTree node)
  77. {
  78.     return maxNumber(height(node->left), height(node->right)) + 1;
  79. }
  81. // 递归查找左节点 为最小
  82. AVLTree findMin(AVLTree tree)
  83. {
  84.     if (tree == NULL)
  85.         return NULL;
  86.     if (tree->left == NULL)
  87.         return tree;
  88.     return findMin(tree->left);
  89. }
  90. // 循环查找右节点 为最大
  91. AVLTree findMax(AVLTree tree)
  92. {
  93.     if (tree != NULL)
  94.     {
  95.         while (tree->right != NULL)
  96.         {
  97.             tree = tree->right;
  98.         }
  99.     }
  100.     return tree;
  101. }
  102. // 左旋转（LL旋转）
  103. AVLTree rotateLeft(AVLTree node)
  104. {
  105.     // 拿出右子树节点
  106.     AVLTree rightNode = node->right;
  107.     assert(rightNode != NULL);
  108.     // 将右子树的左子树赋值给当前旋转节点的有右节点
  109.     node->right = rightNode->left;
  110.     //将 当前旋转节点赋值给右子树的左节点
  111.     rightNode->left = node;
  113.     // 重新设置高度
  114.     node->height = getMaxHeight(node);
  115.     rightNode->height = getMaxHeight(rightNode);
  117.     //完成旋转 将右子树返回
  118.     return rightNode;
  119. }
  120. // 右旋转（RR旋转）
  121. AVLTree rotateRight(AVLTree node)
  122. { // 拿出左子树节点
  123.     AVLTree leftNode = node->left;
  124.     assert(leftNode != NULL);
  125.     // 将左子树的右子树节点赋值给当前旋转节点的左侧节点
  126.     node->left = leftNode->right;
  127.     // 将当前旋转节点赋值给左子树的右侧节点
  128.     leftNode->right = node;
  129.     // 重新设置高度
  130.     node->height = getMaxHeight(node);
  131.     leftNode->height = getMaxHeight(leftNode);
  132.     // 完成旋转 将左子树节点返回
  133.     return leftNode;
  134. };
  136. // 左右旋转（LR旋转）
  137. AVLTree rotateLeftRight(AVLTree node)
  138. {
  139.     assert(node != NULL && node->left != NULL);
  140.     // 先对当前旋转节点的左子树节点进行左旋转 并将返回值赋值给左子树
  141.     node->left = rotateLeft(node->left);
  142.     // 再对当前旋转节点进行右旋转
  143.     return rotateRight(node);
  144. }
  145. // 右左旋转（RL旋转）
  146. AVLTree rotateRightLeft(AVLTree node)
  147. {
  148.     assert(node != NULL && node->right != NULL);
  149.     // 先对当前旋转节点的右子树节点进行右旋转 并将返回值赋值给右子树
  150.     node->right = rotateRight(node->right);
  151.     // 再对当前旋转节点进行左旋转
  152.     return rotateLeft(node);
  153. }
  154. // 再平衡 通过旋转让AVL 树再度平衡
  155. AVLTree rebalance(const int data, AVLTree node)
  156. {
  157.     if (node == NULL)
  158.         return NULL;
  159.     // 两颗子树的高度差不大于1，则该节点是平衡的
  161.     // 左子树的高度大于右子树的高度 并且差值大于1 节点不平衡
  162.     if (height(node->left) - height(node->right) > 1)
  163.     {
  164.         // 当前插入的值小于 左子树的值 说明 这个新节点插入到了左子树的左子树节点的位置 进行右旋转
  165.         if (data < node->left->data)
  166.         {
  168.             node = rotateRight(node);
  169.         }
  170.         else // 否则就是插入了 左子树的右子树节点位置 进行左右旋转
  171.         {
  172.             node = rotateLeftRight(node);
  173.         }
  174.     }
  175.     // 右子树的高度大于左子树的高度 并且差值大于1 节点不平衡
  176.     else if (height(node->right) - height(node->left) > 1)
  177.     {
  178.         // 当前插入的值大于 右子树的值 说明 这个新节点插入到了 右子树的右子树的位置 进行左旋转
  179.         if (data > node->right->data)
  180.         {
  181.             node = rotateLeft(node);
  182.         }
  183.         else // 否则就是在右子树的左子树位置 进行右左旋转
  184.         {
  185.             node = rotateRightLeft(node);
  186.         }
  187.     }
  188.     return node;
  189. };
  190. AVLTree insert(const int data, AVLTree tree)
  191. {
  192.     if (tree == NULL)
  193.     {
  194.         tree = createAvlNode(data);
  195.     }
  196.     else if (data < tree->data)
  197.     { //比当前节点小 插入左子树中
  198.         tree->left = insert(data, tree->left);
  199.     }
  200.     else if (data > tree->data)
  201.     {
  202.         // 比当前节点的值大，插入右子树中
  203.         tree->right = insert(data, tree->right);
  204.     }
  205.     // 再平衡
  206.     tree = rebalance(data, tree);
  207.     tree->height = getMaxHeight(tree);
  208.     return tree;
  209. }
  211. // 删除节点
  212. AVLTree deleteNode(const int data, AVLTree tree)
  213. {
  214.     if (tree == NULL)
  215.         return NULL;
  217.     if (tree->data > data)
  218.     {
  219.         // 小于当前节点值 去左子树节点查找
  220.         tree->left = deleteNode(data, tree->left);
  221.     }
  222.     else if (tree->data < data)
  223.     {
  224.         // 大于当前节点值 右去子树节点查找
  225.         tree->right = deleteNode(data, tree->right);
  226.     }
  227.     else if (tree->left && tree->right)
  228.     {
  229.         // 找到右子树最小的节点，替换当前节点
  230.         AVLTree temp = findMin(tree->right);
  231.         tree->data = temp->data;
  232.         // 再将最小节点删除
  233.         tree->right = deleteNode(temp->data, tree->right);
  234.     }
  235.     else
  236.     {
  237.         AVLTree temp = tree;
  238.         if (tree->left == NULL)
  239.         {
  240.             tree = tree->right;
  241.         }
  242.         else if (tree->right == NULL)
  243.         {
  244.             tree = tree->left;
  245.         }
  246.         free(temp);
  247.     }
  248.     // 再平衡
  249.     tree = rebalance(data, tree);
  250.     return tree;
  251. };
  253. void printTree(AVLTree tree, int level)
  254. {
  255.     if (tree != NULL)
  256.     {
  257.         printTree(tree->left, level + 1);
  258.         printf("node data = %d, height = %d , level = %d\n", tree->data, tree->height, level);
  259.         printTree(tree->right, level + 1);
  260.     }
  261. }
  263. #endif //AVL_TREE_H

AVL树的插入和删除

avl树的插入和删除是与二叉搜索树一致的，不同的是在插入或者删除节点之后，调用 rebalance 函数判断是否需要进行旋转再平衡。