架设个人网站,环球设计网站,写作挣钱的网站,免费短视频制作文章目录 概述一、定义与特性二、平衡因子三、基本操作四、旋转操作五、应用场景 Java代码实现 概述
AVL树是一种自平衡的二叉查找树#xff0c;由两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明。想了解树的相关概念#xff0c;请点击这里。以下是对AVL树的… 文章目录 概述一、定义与特性二、平衡因子三、基本操作四、旋转操作五、应用场景 Java代码实现 概述
AVL树是一种自平衡的二叉查找树由两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明。想了解树的相关概念请点击这里。以下是对AVL树的详细说明
一、定义与特性
定义AVL树是一种二叉查找树其中每个节点的左右子树的高度差的绝对值即平衡因子不超过1。特性 左右子树都是AVL树。左右子树高度之差简称平衡因子的绝对值不超过1-1、0、1。任意节点的左右子树的高度差不会超过1这保证了树的高度相对较低从而提高了搜索、插入和删除操作的效率。
二、平衡因子
平衡因子Balance FactorBF是AVL树中的一个重要概念用于衡量节点的左右子树的高度差。平衡因子的值只能是-1、0或1。具体计算方式为节点的右子树高度减去左子树高度。
三、基本操作
AVL树的基本操作包括插入、删除和查找这些操作都需要在保持树平衡的前提下进行。 插入 按照二叉查找树的方式插入新节点。插入后从插入点向上回溯更新每个节点的平衡因子。如果发现某个节点的平衡因子绝对值超过1则进行旋转操作以恢复平衡。 删除 找到要删除的节点并将其向下旋转成一个叶子节点。直接删除该叶子节点。从删除点向上回溯更新每个节点的平衡因子。如果发现某个节点的平衡因子绝对值超过1则进行旋转操作以恢复平衡。 查找 在AVL树中查找元素的过程与在二叉查找树中相同。由于AVL树总是保持平衡的所以查找操作的时间复杂度为O(log n)。
四、旋转操作
旋转操作是AVL树保持平衡的关键。根据节点插入或删除后不平衡的具体情况AVL树的旋转可以分为四种类型
单向右旋LL当在节点的左子树的左子树上插入新节点导致节点不平衡平衡因子为2时进行右旋转操作。单向左旋RR当在节点的右子树的右子树上插入新节点导致节点不平衡平衡因子为-2时进行左旋转操作。双向旋转先左后右LR当在节点的左子树的右子树上插入新节点导致节点不平衡平衡因子为2时先进行左旋转再进行右旋转。双向旋转先右后左RL当在节点的右子树的左子树上插入新节点导致节点不平衡平衡因子为-2时先进行右旋转再进行左旋转。
五、应用场景
AVL树适用于插入删除次数较少但查找频繁的场景。例如Windows进程地址空间管理就采用了AVL树来实现高效的查找操作。然而由于AVL树在插入和删除操作后需要进行复杂的旋转操作来保持平衡所以其性能在插入和删除操作频繁的场景下可能不如其他数据结构如红黑树。
综上所述AVL树是一种高效的自平衡二叉查找树通过引入平衡因子和旋转操作来保持树的平衡性从而提高了搜索、插入和删除操作的效率。
Java代码实现
下面是一个简单的AVL树在Java中的实现。这个实现包括了插入、删除和查找操作以及必要的旋转操作来维持树的平衡。
class AVLTree {private class Node {int key, height;Node left, right;Node(int d) {key d;height 1;}}private Node root;// Utility function to get the height of the treeint height(Node N) {if (N null)return 0;return N.height;}// Utility function to get the maximum of two integersint max(int a, int b) {return (a b) ? a : b;}// Right rotate subtree rooted with yNode rightRotate(Node y) {Node x y.left;Node T2 x.right;// Perform rotationx.right y;y.left T2;// Update heightsy.height max(height(y.left), height(y.right)) 1;x.height max(height(x.left), height(x.right)) 1;// Return new rootreturn x;}// Left rotate subtree rooted with xNode leftRotate(Node x) {Node y x.right;Node T2 y.left;// Perform rotationy.left x;x.right T2;// Update heightsx.height max(height(x.left), height(x.right)) 1;y.height max(height(y.left), height(y.right)) 1;// Return new rootreturn y;}// Get Balance factor of node Nint getBalance(Node N) {if (N null)return 0;return height(N.left) - height(N.right);}// Insert a node with given key in the subtree rooted with node and returns the new root of the subtreeNode insert(Node node, int key) {// Perform the normal BST insertionif (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 // Duplicate keys are not allowed in BSTreturn node;// Update height of this ancestor nodenode.height 1 max(height(node.left), height(node.right));// Get the balance factor of this ancestor node to check whether this node became unbalancedint balance getBalance(node);// If this node becomes unbalanced, then there are 4 cases// Left Left Caseif (balance 1 key node.left.key)return rightRotate(node);// Right Right Caseif (balance -1 key node.right.key)return leftRotate(node);// Left Right Caseif (balance 1 key node.left.key) {node.left leftRotate(node.left);return rightRotate(node);}// Right Left Caseif (balance -1 key node.right.key) {node.right rightRotate(node.right);return leftRotate(node);}// Return the (unchanged) node pointerreturn node;}// Delete a node with given key in the subtree rooted with node and returns the new root of the subtreeNode deleteNode(Node root, int key) {// Perform standard BST deleteif (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 {// node with only one child or no childif ((root.left null) || (root.right null)) {Node temp null;if (temp root.left)temp root.right;elsetemp root.left;// No child caseif (temp null) {temp root;root null;} else // One child caseroot temp; // Copy the contents of the non-empty child} else {// node with two children: Get the inorder successor (smallest in the right subtree)Node temp minValueNode(root.right);// Copy the inorder successors data to this noderoot.key temp.key;// Delete the inorder successorroot.right deleteNode(root.right, temp.key);}}// If the tree had only one node then returnif (root null)return root;// Update height of the current noderoot.height max(height(root.left), height(root.right)) 1;// Get the balance factor of this node (to check whether this node became unbalanced)int balance getBalance(root);// If this node becomes unbalanced, then there are 4 cases// Left Left Caseif (balance 1 getBalance(root.left) 0)return rightRotate(root);// Left Right Caseif (balance 1 getBalance(root.left) 0) {root.left leftRotate(root.left);return rightRotate(root);}// Right Right Caseif (balance -1 getBalance(root.right) 0)return leftRotate(root);// Right Left Caseif (balance -1 getBalance(root.right) 0) {root.right rightRotate(root.right);return leftRotate(root);}return root;}Node minValueNode(Node node) {Node current node;// Loop down to find the leftmost leafwhile (current.left ! null)current current.left;return current;}// A utility function to do inorder traversal of BSTvoid inorder(Node root) {if (root ! null) {inorder(root.left);System.out.print(root.key );inorder(root.right);}}// Main functionpublic 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 be30/ \20 40/ \ \10 25 50*/System.out.println(Inorder traversal of the constructed AVL tree is:);tree.inorder(tree.root);System.out.println(\n\nDelete 20);tree.root tree.deleteNode(tree.root, 20);System.out.println(Inorder traversal of the modified tree is:);tree.inorder(tree.root);System.out.println(\n\nDelete 30);tree.root tree.deleteNode(tree.root, 30);System.out.println(Inorder traversal of the modified tree is:);tree.inorder(tree.root);System.out.println(\n\nDelete 50);tree.root tree.deleteNode(tree.root, 50);System.out.println(Inorder traversal of the modified tree is:);tree.inorder(tree
