数据结构与算法简记：AVL树

骑猪看日落 2022-07-19 05:21 237阅读 0赞

前面记录了二叉查找树，它在搜索方面的效率显而易见，可它也存在某种缺陷，假设我们连续插入较小或较大的数据，那么二叉查找树将会逐渐退变为一个线性结构，从而搜索就变为了线性查找，效率将会大打折扣。所以，我们需要一棵这样的树，它在插入新节点后，能够重新调整自己的结构，使左右恢复平衡。AVL树就符合这个条件。

AVL树是最先发明的自平衡二叉查找树，其得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 “An algorithm for the organization of information” 中发表了它。

在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树，其查找、插入和删除在平均和最坏情况下都是O(logN)。

首先是创建AVL树：

我们可以从一个排序后的数组来初始化AVL树，这个过程不难，只需找到数组区间的中间元素，这个将作为树的根节点，同时这个节点将数组划分两个子区间，然后分别再取左右子区间中间元素，创建左右子树的根节点，同时继续划分子区间，如此进行下去。过程如下图所示：

20160810133337047

然后是插入和移除节点，基本操作跟二叉查找树相似，不同的是这两个操作都需要重新平衡子树结构。

要使一棵树重新恢复平衡，我们需要对子树节点进行旋转操作，而旋转操作需要应对4种不同的情况，它们分别是：

LL: 即左左情况，此时需要对节点进行右旋转操作
RR: 即右右情况，此时需要对节点进行左旋转操作

以上这两种情况的旋转操作如下图所示：

20160810162725249

还有两种相对复杂的情况：

LR: 即左右情况，此时需要先进行一次RR型旋转，再进行一次LL型旋转
RL: 即右做情况，此时需要先进行一次LL行旋转，再进行一次RR型旋转

下面两张图分别拆解了这两种情况的步骤：

20160810163007891

20160810163222262

下面分别是JS和C语言的实现代码：

JS描述：

  1. //AVL树节点结构
  2. function AVLTreeNode(data) {
  4.   this.data = data;
  5.   this.leftChild = null;
  6.   this.rightChild = null;
  7.   this.height = 0;
  8. }
  10. var AVLTreeUtil = {
  11.   //由排序数组创建AVL树
  12.   createAVLTree: function(array, low, high) {
  14.     if (high < low) return null;
  16.     var mid = Math.floor((low + high) / 2);
  18.     var newNode = new AVLTreeNode(array[mid]);
  20.     newNode.leftChild = this.createAVLTree(array, low, mid - 1);
  21.     newNode.rightChild = this.createAVLTree(array, mid + 1, high);
  23.     this.updateHeight(newNode);
  25.     return newNode;
  26.   },
  27.   //前序遍历子树
  28.   preOrderTraverse: function(node, visitFn) {
  30.     if (node) {
  31.       visitFn(node);
  33.       this.preOrderTraverse(node.leftChild, visitFn);
  34.       this.preOrderTraverse(node.rightChild, visitFn);
  35.     }
  36.   },
  37.   //中序遍历子树
  38.   inOrderTraverse: function(node, visitFn) {
  40.     if (node) {
  41.       this.inOrderTraverse(node.leftChild, visitFn);
  43.       visitFn(node);
  45.       this.inOrderTraverse(node.rightChild, visitFn);
  46.     }
  47.   },
  48.   //插入节点并保持树平衡
  49.   insertNodeWithBalance: function(node, key) {
  51.     if (!node) {
  52.       return new AVLTreeNode(key);
  53.     }
  55.     if (key < node.data) {
  56.       node.leftChild = this.insertNodeWithBalance(node.leftChild, key);
  58.       //平衡当前节点和左子树
  59.       node = this.balanceLeft(node, key);
  60.     } else {
  61.       node.rightChild = this.insertNodeWithBalance(node.rightChild, key);
  63.       //平衡当前节点和右子树
  64.       node = this.balanceRight(node, key);
  65.     }
  67.     this.updateHeight(node);
  69.     return node;
  70.   },
  71.   //移除子树中指定值的节点
  72.   removeNodeWithBalance: function(node, key) {
  74.     if (!node) return null;
  76.     if (key < node.data) {
  77.       node.leftChild = this.removeNodeWithBalance(node.leftChild, key);
  79.       //平衡当前节点和左子树
  80.       node = this.balanceLeft(node, key);
  82.       this.updateHeight(node);
  84.       return node;
  85.     }
  87.     if (key > node.data) {
  88.       node.rightChild = this.removeNodeWithBalance(node.rightChild, key);
  90.       //平衡当前节点和右子树
  91.       node = this.balanceRight(node, key);
  93.       this.updateHeight(node);
  95.       return node;
  96.     }
  98.     //叶子节点
  99.     if (!node.leftChild && !node.rightChild) {
  100.       return null;
  101.     }
  103.     //仅左子树不存在，但存在右子树
  104.     if (!node.leftChild) {
  105.       return node.rightChild;
  106.     }
  108.     //仅右子树不存在，但存在左子树
  109.     if (!node.rightChild) {
  110.       return node.leftChild;
  111.     }
  113.     //下面处理左右子树均不为空的情况
  115.     //查找右子树中最小节点
  116.     var minNode = this.findMinNode(node.rightChild);
  118.     //替换
  119.     node.data = minNode.data;
  121.     //在右子树中移除最小节点
  122.     node.rightChild = this.removeNodeWithBalance(node.rightChild, minNode.data);
  124.     //平衡当前节点和右子树
  125.     node = this.balanceRight(node, key);
  127.     this.updateHeight(node);
  129.     return node;
  130.   },
  131.   //查找指定子树中最小节点
  132.   findMinNode: function(node) {
  134.     while (node && node.leftChild) {
  135.       node = node.leftChild;
  136.     }
  138.     return node;
  139.   },
  140.   //获取节点树高
  141.   getHeight: function(node) {
  143.     if (!node) return -1;
  145.     return node.height;
  146.   },
  147.   //更新节点树高
  148.   updateHeight: function(node) {
  150.     node.height = Math.max(this.getHeight(node.leftChild), this.getHeight(node.rightChild)) + 1;
  151.   },
  152.   //LL型右旋操作
  153.   rightRotateLL: function(node) {
  155.     var pivot = node.leftChild;
  157.     node.leftChild = pivot.rightChild;
  159.     pivot.rightChild = node;
  161.     this.updateHeight(node);
  162.     this.updateHeight(pivot);
  164.     return pivot;
  165.   },
  166.   //RR型左旋操作
  167.   leftRotateRR: function(node) {
  169.     var pivot = node.rightChild;
  171.     node.rightChild = pivot.leftChild;
  173.     pivot.leftChild = node;
  175.     this.updateHeight(node);
  176.     this.updateHeight(pivot);
  178.     return pivot;
  179.   },
  180.   //LR型双旋操作
  181.   doubleRotateLR: function(node) {
  183.     node.leftChild = this.leftRotateRR(node.leftChild);
  185.     return this.rightRotateLL(node);
  186.   },
  187.   //RL型双旋操作
  188.   doubleRotateRL: function(node) {
  190.     node.rightChild = this.rightRotateLL(node.rightChild);
  192.     return this.leftRotateRR(node);
  193.   },
  194.   //平衡左边
  195.   balanceLeft: function(node, key) {
  197.     if (this.lostBalance(node)) {
  198.       if (key < node.leftChild.data) {
  199.         node = this.rightRotateLL(node);  //LL
  200.       } else {
  201.         node = this.doubleRotateLR(node); //LR
  202.       }
  203.     }
  205.     return node;
  206.   },
  207.   //平衡右边
  208.   balanceRight: function(node, key) {
  210.     if (this.lostBalance(node)) {
  211.       if (key > node.rightChild.data) {
  212.         node = this.leftRotateRR(node);   //RR
  213.       } else {
  214.         node = this.doubleRotateRL(node); //RL
  215.       }
  216.     }
  218.     return node;
  219.   },
  220.   //是否失去平衡
  221.   lostBalance: function(node) {
  223.     //左右树高之差大于1就失去了平衡
  224.     return Math.abs(this.getHeight(node.leftChild) - this.getHeight(node.rightChild)) > 1;
  225.   }
  226. };
  228. //已排序数据
  229. var array = [1, 3, 4, 6, 7, 8, 10, 13, 15];
  231. var rootNode = AVLTreeUtil.createAVLTree(array, 0, array.length - 1);
  233. //用于存放节点遍历序列
  234. var orderArray = [];
  236. var visitFn = function(node) {
  238.   orderArray.push(node.data);
  239. };
  241. var printInAndPre = function() {
  243.   orderArray.length = 0;
  245.   AVLTreeUtil.inOrderTraverse(rootNode, visitFn);
  246.   console.log('in order:', orderArray.join(' '));
  248.   orderArray.length = 0;
  250.   AVLTreeUtil.preOrderTraverse(rootNode, visitFn);
  251.   console.log('pre order:', orderArray.join(' '));
  252. };
  254. console.log('--- after init ---');
  255. printInAndPre();
  257. //插入节点14并使树平衡
  258. rootNode = AVLTreeUtil.insertNodeWithBalance(rootNode, 14);
  260. console.log('--- after 14 inserted ---');
  261. printInAndPre();
  263. rootNode = AVLTreeUtil.removeNodeWithBalance(rootNode, 14);
  265. console.log('--- after 14 removed ---');
  266. printInAndPre();
  268. rootNode = AVLTreeUtil.insertNodeWithBalance(rootNode, 0);
  269. rootNode = AVLTreeUtil.insertNodeWithBalance(rootNode, -1);
  271. console.log('--- after 0 and -1 inserted ---');
  272. printInAndPre();

C语言描述：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. #define max(a,b) (a > b ? a : b)
  6. //AVL树节点结构体
  7. typedef struct node {
  8.     int data;
  9.     struct node *lchild, *rchild;
  10.     int height;
  11. } AVLTreeNode;
  13. AVLTreeNode * createAVLTree(int *array, int low, int high);
  15. void preOrderTraverse(AVLTreeNode *node);
  16. void inOrderTraverse(AVLTreeNode *node);
  18. AVLTreeNode * findMinNode(AVLTreeNode *node);
  20. int getHeight(AVLTreeNode *node);
  21. void updateHeight(AVLTreeNode *node);
  23. AVLTreeNode * insertNodeWithBalance(AVLTreeNode *node, int key);
  24. AVLTreeNode * removeNodeWithBalance(AVLTreeNode *node, int key);
  26. AVLTreeNode * rightRotateLL(AVLTreeNode *node);
  27. AVLTreeNode * doubleRotateLR(AVLTreeNode *node);
  28. AVLTreeNode * leftRotateRR(AVLTreeNode *node);
  29. AVLTreeNode * doubleRotateRL(AVLTreeNode *node);
  31. void balanceLeft(AVLTreeNode **node, int key);
  32. void balanceRight(AVLTreeNode **node, int key);
  34. int main(int argc, const char * argv[]) {
  36.     //已排序数据
  37.     int array[] = {
  38.    1, 3, 4, 6, 7, 8, 10, 13, 15};
  39.     int size = 9;
  41.     AVLTreeNode *rootNode = createAVLTree(array, 0, size - 1);
  43.     printf("---after init ---\nin: ");
  45.     inOrderTraverse(rootNode);
  47.     printf("\npre: ");
  48.     preOrderTraverse(rootNode);
  50.     rootNode = insertNodeWithBalance(rootNode, 14);
  52.     printf("\n--- after 14 inserted ---\nin: ");
  53.     inOrderTraverse(rootNode);
  55.     printf("\npre: ");
  56.     preOrderTraverse(rootNode);
  58.     rootNode = removeNodeWithBalance(rootNode, 14);
  60.     printf("\n--- after 14 removed ---\nin: ");
  61.     inOrderTraverse(rootNode);
  63.     printf("\npre: ");
  64.     preOrderTraverse(rootNode);
  66.     rootNode = insertNodeWithBalance(rootNode, 0);
  67.     rootNode = insertNodeWithBalance(rootNode, -1);
  69.     printf("\n--- after 14 removed ---\nin: ");
  70.     inOrderTraverse(rootNode);
  72.     printf("\npre: ");
  73.     preOrderTraverse(rootNode);
  75.     return 0;
  76. }
  78. //初始化AVL树
  79. AVLTreeNode * createAVLTree(int *array, int low, int high) {
  80.     if(high < low) return NULL;
  82.     //取出子树根节点值
  83.     int mid = (low + high) / 2;
  85.     //创建子树根节点
  86.     AVLTreeNode *newNode = (AVLTreeNode *) malloc(sizeof(AVLTreeNode));
  87.     newNode->data = array[mid];
  88.     newNode->height = 0;
  90.     //创建左右子树
  91.     newNode->lchild = createAVLTree(array, low, mid - 1);
  92.     newNode->rchild = createAVLTree(array, mid + 1, high);
  94.     //更新根节点树高
  95.     updateHeight(newNode);
  97.     return newNode;
  98. }
  100. //先序遍历，用来验证平衡后的二叉树
  101. void preOrderTraverse(AVLTreeNode *node) {
  102.     if (node != NULL) {
  103.         printf("%d ", node->data);
  105.         preOrderTraverse(node->lchild);
  107.         preOrderTraverse(node->rchild);
  108.     }
  109. }
  111. //中序遍历
  112. void inOrderTraverse(AVLTreeNode *node) {
  113.     if (node != NULL) {
  114.         inOrderTraverse(node->lchild);
  116.         printf("%d ", node->data);
  118.         inOrderTraverse(node->rchild);
  119.     }
  120. }
  122. //查找指定子树中最小节点
  123. AVLTreeNode * findMinNode(AVLTreeNode *node) {
  125.     while (node != NULL && node->lchild != NULL) {
  126.         node = node->lchild;
  127.     }
  129.     return node;
  130. }
  132. //插入节点并保持平衡
  133. AVLTreeNode * insertNodeWithBalance(AVLTreeNode *node, int key) {
  135.     //新增叶子节点，并返回该节点，父节点会与其建立关联
  136.     if (node == NULL) {
  137.         node = (AVLTreeNode *) malloc(sizeof(AVLTreeNode));
  138.         node->data = key;
  139.         node->height = 0;
  140.         node->lchild = node->rchild = NULL;
  142.         return node;
  143.     }
  145.     if (key < node->data) {
  146.         node->lchild = insertNodeWithBalance(node->lchild, key);
  148.         //平衡当前节点和左子树
  149.         balanceLeft(&node, key);
  151.     } else {
  152.         node->rchild = insertNodeWithBalance(node->rchild, key);
  154.         //平衡当前节点和右子树
  155.         balanceRight(&node, key);
  156.     }
  158.     updateHeight(node);
  160.     return node;
  161. }
  163. //在子树中移除值为key的节点并保持平衡
  164. AVLTreeNode * removeNodeWithBalance(AVLTreeNode *node, int key) {
  166.     if (node == NULL) return NULL;
  168.     //向左子树继续
  169.     if (key < node->data) {
  170.         node->lchild = removeNodeWithBalance(node->lchild, key);
  172.         //平衡当前节点和左子树
  173.         balanceLeft(&node, key);
  175.         updateHeight(node);
  177.         return node;
  178.     }
  180.     //向右子树继续
  181.     if (key > node->data) {
  182.         node->rchild = removeNodeWithBalance(node->rchild, key);
  184.         //平衡当前节点和右子树
  185.         balanceRight(&node, key);
  187.         updateHeight(node);
  189.         return node;
  190.     }
  192.     //以下是匹配到节点后的几个不同的情况
  194.     //移除叶子节点
  195.     if (node->lchild == NULL && node->rchild == NULL) {
  196.         //释放
  197.         free(node);
  199.         return NULL;
  200.     }
  202.     //仅左子树不存在
  203.     if (node->lchild == NULL) {
  204.         AVLTreeNode *rchild = node->rchild;
  206.         //释放
  207.         free(node);
  209.         return rchild;
  210.     }
  212.     //仅右子树不存在
  213.     if (node->rchild == NULL) {
  214.         AVLTreeNode *lchild = node->lchild;
  216.         //释放
  217.         free(node);
  219.         return lchild;
  220.     }
  222.     //-----最后如果左右子节点均存在，则先找到右子树最小子节点，替换其值，然后将最小节点删除-----
  224.     //查找右子树最小节点
  225.     AVLTreeNode *minNode = findMinNode(node->rchild);
  227.     //替换其值
  228.     node->data = minNode->data;
  230.     //在右子树中移除最小节点
  231.     node->rchild = removeNodeWithBalance(node->rchild, minNode->data);
  233.     //平衡当前节点和右子树
  234.     balanceRight(&node, key);
  236.     updateHeight(node);
  238.     return node;
  239. }
  241. //获取子树根节点高度
  242. int getHeight(AVLTreeNode *node) {
  243.     if (node == NULL) return -1;
  245.     return node->height;
  246. }
  248. //更新节点树高
  249. void updateHeight(AVLTreeNode *node) {
  250.     node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
  251. }
  253. //对LL类型做右旋转操作
  254. AVLTreeNode * rightRotateLL(AVLTreeNode *node) {
  256.     //获取左子节点作为轴点
  257.     AVLTreeNode *pivot = node->lchild;
  259.     node->lchild = pivot->rchild;
  261.     pivot->rchild = node;
  263.     updateHeight(node);
  264.     updateHeight(pivot);
  266.     return pivot;
  267. };
  269. //对RR类型做左旋转操作
  270. AVLTreeNode * leftRotateRR(AVLTreeNode *node) {
  272.     //获取右子节点作为轴点
  273.     AVLTreeNode *pivot = node->rchild;
  275.     node->rchild = pivot->lchild;
  277.     pivot->lchild = node;
  279.     updateHeight(node);
  280.     updateHeight(pivot);
  282.     return pivot;
  283. };
  285. //对于LR类型，先对左子节点进行一次RR类型的左旋转操作，然后再对根节点进行一次LL类型的右旋转操作
  286. AVLTreeNode * doubleRotateLR(AVLTreeNode *node) {
  288.     node->lchild = leftRotateRR(node->lchild);
  290.     return rightRotateLL(node);
  291. };
  293. //对于RL类型，先对右子树进行一次LL类型的右旋转操作，然后再对根节点进行一次RR类型的左旋转操作
  294. AVLTreeNode * doubleRotateRL(AVLTreeNode *node) {
  296.     node->rchild = rightRotateLL(node->rchild);
  298.     return leftRotateRR(node);
  299. };
  301. //平衡LL或LR类型
  302. void balanceLeft(AVLTreeNode **node, int key) {
  304.     AVLTreeNode *p = *node;
  306.     if (getHeight(p->lchild) - getHeight(p->rchild) > 1) {
  307.         if (key < p->lchild->data) {    //LL
  308.             *node = rightRotateLL(p);
  309.         } else {                        //LR
  310.             *node = doubleRotateLR(p);
  311.         }
  312.     }
  313. }
  315. //平衡RR或RL类型
  316. void balanceRight(AVLTreeNode **node, int key) {
  318.     AVLTreeNode *p = *node;
  320.     if (getHeight(p->rchild) - getHeight(p->lchild) > 1) {
  321.         if (key > p->rchild->data) {    //RR
  322.             *node = leftRotateRR(p);
  323.         } else {                        //RL
  324.             *node = doubleRotateRL(p);
  325.         }
  326.     }
  327. }

发表评论

表情：
评论列表 （有 0 条评论，237人围观）

还没有评论，来说两句吧...

相关阅读

    相关 数据结构与算法简记：AVL树

    前面记录了二叉查找树，它在搜索方面的效率显而易见，可它也存在某种缺陷，假设我们连续插入较小或较大的数据，那么二叉查找树将会逐渐退变为一个线性结构，从而搜索就变为了线性查找，效率

    骑猪看日落骑猪看日落/ 0 赞/ 238 阅读