平衡二叉树之AVL树（Adelson-Velsky and Landis Tree）简介及Java实现

[toc]

一、AVL树简介

在前面的内容中，我们已经介绍了平衡二叉树。其中提到了AVL树，这是一种非常著名的平衡二叉树。

在计算机科学中，AVL树（以发明者Adelson-Velsky和Landis命名）是一种自平衡二叉查找树。这是第一个发明类似自平衡机制的二叉树数据结构。在AVL树中，任何节点的两个子树的高度最多相差一个。如果在任何时候它们相差多于一个，则重新平衡以恢复此属性。查找，插入和删除在平均和最差情况下都需要$O(\log n)$时间，其中n是操作之前树中的节点数。插入和删除可能需要通过一个或多个树旋转来重新平衡树。

AVL树以其两位苏联发明家Georgy Adelson-Velsky和Evgenii Landis命名，他们在1962年的论文“An algorithm for the organization of information”中发表了这篇论文。

AVL树通常与红黑树进行比较，因为它们都支持相同的操作，并且对基本操作都是$O(\log n)$时间。对于查找密集型应用程序，AVL树比红黑树快，因为它们更严格地平衡。与红黑树相似，AVL树是高度平衡树。

二、平衡因子（Balance Factor）

在二叉树中，平衡因子（Balance Factor）是一种高度之差，它等于左子树的高度减去右子树的高度：

\text{BF(T)} = H_L - H_R

如果一个树是AVL树，那么它的平衡因子只能有三种取值，即0,1和-1。当平衡因子小于0，称为“left heavy”，大于0是“right-heavy”，等于0则是平衡的。

三、自平衡适应

前面已经说过了，保证树的平衡会大大提高搜索的效率。那么如何保证平衡就是不同自平衡树之间的差异了。AVL树保持自平衡的方式是通过旋转的方式。上述定义的平衡因子就是帮助我们判断是否需要进行平衡操作的信息，而AVL树的平衡操作主要包括单旋转和双旋转两种，前者分为左单旋和右单旋，而后者则分成左右旋转和右左旋转。

旋转操作发生在插入和删除操作中，因为插入和删除可能会破坏树的平衡状态。以插入为例，所有新加的元素都是叶子节点，叶子节点的左右子树高度都是0，因此平衡因子也是0，不存在平衡的需要。因此，需要平衡的节点是其父节点。平衡的操作取决于新加的元素是左叶子节点还是右叶子节点。如果是右叶子节点，那么父节点的平衡因子就要减1，否则加1。这个操作也会传导到爷爷节点一直到根节点。因此，这里也引申出了自平衡操作的两个基础：

package com.huawei.machinelearning.data.structure; /** * AVL Tree implementation * Created by d00454735 on 2018/10/26. */ public class AVLTree { AVLNode root; // 根节点 // 右旋转 private AVLNode rightRotate(AVLNode rootNode){ AVLNode newRootNode = rootNode.leftNode; // 新的根节点是原来根节点的左节点 // 将新的根节点的右节点拿出来，然后拼到原来的根节点上 AVLNode pruningNode = newRootNode.rightNode; // 再把拼接后的节点放到新根节点的左边 newRootNode.rightNode = rootNode; rootNode.leftNode = pruningNode; // 更新节点高度 updateNodeHeight(rootNode); updateNodeHeight(newRootNode); return newRootNode; // 返回新的根节点 } // 左旋转 private AVLNode leftRotate(AVLNode rootNode){ AVLNode newRootNode = rootNode.rightNode; // 新的根节点是原来根节点的右节点 // 将新的根节点的左节点拿出来，然后拼到原来的根节点上 AVLNode pruningNode = newRootNode.leftNode; // 再把拼接后的节点放到新根节点的左边 newRootNode.leftNode = rootNode; rootNode.rightNode = pruningNode; // 更新节点高度 updateNodeHeight(rootNode); updateNodeHeight(newRootNode); return newRootNode; // 返回新的根节点 } // 插入一个新节点 AVLNode insert(AVLNode avlNode, int key) { // 如果节点为空，当前插入的是根节点 if (avlNode == null) { return new AVLNode((key)); } // 插入操作 if (key < avlNode.key) { // 如果插入的节点key小于根节点的key，则左边 avlNode.leftNode = insert(avlNode.leftNode, key); } else if (key > avlNode.key) { avlNode.rightNode = insert(avlNode.rightNode, key); } else { // 如果key已存在，则无法插入 return avlNode; } // 更新节点的高度 updateNodeHeight(avlNode); // 获取父节点的平衡因子 int balance = getBalance(avlNode); // 判断是否需要旋转操作，四种情况 // 右旋转 if( balance > 1 && key < avlNode.leftNode.key ){ return rightRotate(avlNode); } // 左旋转 if( balance < -1 && key > avlNode.rightNode.key ){ return leftRotate(avlNode); } // 左右旋转 if( balance > 1 && key > avlNode.leftNode.key){ avlNode.leftNode = leftRotate(avlNode.leftNode); return rightRotate(avlNode); } // 右左旋转 if( balance < -1 && key < avlNode.rightNode.key){ avlNode.rightNode = rightRotate(avlNode.rightNode); return leftRotate(avlNode); } return avlNode; } // 获取当前节点的平衡因子 private int getBalance(AVLNode avlNode){ if( avlNode == null ){ return 0; } return height(avlNode.leftNode) - height(avlNode.rightNode); } // 更新节点高度 private void updateNodeHeight(AVLNode avlNode){ avlNode.height = max(height(avlNode.leftNode), height(avlNode.rightNode))+1; } // 返回较大的值 private int max(int h1, int h2) { return h1 > h2? h1: h2; } // 取出节点的高度 private int height( AVLNode avlNode ){ if( avlNode == null ){ return 0; } return avlNode.height; } // A utility function to print preorder traversal // of the tree. // The function also prints height of every node void preOrder(AVLNode node) { if (node!= null) { System.out.print(node.key + " "); preOrder(node.leftNode); preOrder(node.rightNode); } } public static void main(String[] args) { AVLTree tree = new AVLTree(); /* Constructing tree given in the above figure */ tree.root = tree.insert(tree.root, 10); tree.root = tree.insert(tree.root, 20); tree.root = tree.insert(tree.root, 30); tree.root = tree.insert(tree.root, 40); tree.root = tree.insert(tree.root, 50); tree.root = tree.insert(tree.root, 25); /* The constructed AVL Tree would be 30 / \ 20 40 / \ \ 10 25 50 */ System.out.println("Preorder traversal" + " of constructed tree is: "); tree.preOrder(tree.root); } } // 定义AVL树的节点，这个和其他的一样 class AVLNode { int key; // 节点的key int height; // 节点的高度 AVLNode leftNode, rightNode; // 左右子节点 AVLNode(int d) { key = d; height = 1; } }

平衡二叉树之AVL树（Adelson-Velsky and Landis Tree）简介及Java实现

一、AVL树简介

二、平衡因子（Balance Factor）

三、自平衡适应

DataLearner 官方微信

四、AVL树的Java实现

热门博客