每日学习一个数据结构-AVL树

embedded/2024/10/9 1:19:38/

文章目录

    • 概述
      • 一、定义与特性
      • 二、平衡因子
      • 三、基本操作
      • 四、旋转操作
      • 五、应用场景
    • Java代码实现

概述

AVL树是一种自平衡的二叉查找树，由两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明。想了解树的相关概念，请点击这里。以下是对AVL树的详细说明：

一、定义与特性

  1. 定义：AVL树是一种二叉查找树，其中每个节点的左右子树的高度差的绝对值（即平衡因子）不超过1。
  2. 特性：
    • 左右子树都是AVL树。
    • 左右子树高度之差（简称平衡因子）的绝对值不超过1（-1、0、1）。
    • 任意节点的左右子树的高度差不会超过1，这保证了树的高度相对较低，从而提高了搜索、插入和删除操作的效率。

二、平衡因子

平衡因子（Balance Factor，BF）是AVL树中的一个重要概念，用于衡量节点的左右子树的高度差。平衡因子的值只能是-1、0或1。具体计算方式为：节点的右子树高度减去左子树高度。

三、基本操作

AVL树的基本操作包括插入、删除和查找，这些操作都需要在保持树平衡的前提下进行。

  1. 插入：

    • 按照二叉查找树的方式插入新节点。
    • 插入后，从插入点向上回溯，更新每个节点的平衡因子。
    • 如果发现某个节点的平衡因子绝对值超过1，则进行旋转操作以恢复平衡。

  2. 删除：

    • 找到要删除的节点，并将其向下旋转成一个叶子节点。
    • 直接删除该叶子节点。
    • 从删除点向上回溯，更新每个节点的平衡因子。
    • 如果发现某个节点的平衡因子绝对值超过1，则进行旋转操作以恢复平衡。

  3. 查找：

    • 在AVL树中查找元素的过程与在二叉查找树中相同。
    • 由于AVL树总是保持平衡的，所以查找操作的时间复杂度为O(log n)。

四、旋转操作

旋转操作是AVL树保持平衡的关键。根据节点插入或删除后不平衡的具体情况，AVL树的旋转可以分为四种类型：

  1. 单向右旋（LL）：当在节点的左子树的左子树上插入新节点导致节点不平衡（平衡因子为2）时，进行右旋转操作。
  2. 单向左旋（RR）：当在节点的右子树的右子树上插入新节点导致节点不平衡（平衡因子为-2）时，进行左旋转操作。
  3. 双向旋转（先左后右，LR）：当在节点的左子树的右子树上插入新节点导致节点不平衡（平衡因子为2）时，先进行左旋转再进行右旋转。
  4. 双向旋转（先右后左，RL）：当在节点的右子树的左子树上插入新节点导致节点不平衡（平衡因子为-2）时，先进行右旋转再进行左旋转。

五、应用场景

AVL树适用于插入删除次数较少但查找频繁的场景。例如，Windows进程地址空间管理就采用了AVL树来实现高效的查找操作。然而，由于AVL树在插入和删除操作后需要进行复杂的旋转操作来保持平衡，所以其性能在插入和删除操作频繁的场景下可能不如其他数据结构（如红黑树）。

综上所述，AVL树是一种高效的自平衡二叉查找树，通过引入平衡因子和旋转操作来保持树的平衡性，从而提高了搜索、插入和删除操作的效率。

Java代码实现

下面是一个简单的AVL树在Java中的实现。这个实现包括了插入、删除和查找操作，以及必要的旋转操作来维持树的平衡。

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 successor's 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

http://www.ppmy.cn/embedded/124316.html

相关文章

Hive3.x版本调优总结

Hive3.x版本调优总结

文章目录 第 1 章 Explain 查看执行计划&#xff08;重点&#xff09;1.1 创建测试用表1&#xff09;建大表、小表和 JOIN 后表的语句2&#xff09;分别向大表和小表中导入数据 1.2 基本语法1.3 案例实操 第 2 章 Hive 建表优化2.1 分区表2.1.1 分区表基本操作2.1.2 二级分区2.…
阅读更多...
Redis篇（最佳实践）（持续更新迭代）

Redis篇（最佳实践）（持续更新迭代）

介绍一&#xff1a;键值设计 一、优雅的key结构 Redis 的 Key 虽然可以自定义&#xff0c;但最好遵循下面的几个最佳实践约定&#xff1a; 遵循基本格式&#xff1a;[业务名称]:[数据名]:[id]长度不超过 44 字节不包含特殊字符 例如&#xff1a; 我们的登录业务&#xff0…
阅读更多...
py-mmcif包pdbx_struct_oper_list对象介绍

py-mmcif包pdbx_struct_oper_list对象介绍

pdbx_struct_oper_list 对象 pdbx_struct_oper_list 对象是用于描述蛋白质结构的几何变换操作符的列表。在 mmCIF 文件中，它定义了在组装生物学装配体（biological assembly）时对每个亚基或链执行的几何变换。该列表包含了每个操作符的详细信息，包括操作的旋转矩阵和平移向…
阅读更多...
【Unity】unity安卓打包参数（个人复习向/有不足之处欢迎指出/侵删）

【Unity】unity安卓打包参数（个人复习向/有不足之处欢迎指出/侵删）

1.Texture Compression 纹理压缩 设置发布后的纹理压缩格式 Use Player Settings:使用在播放器设置中设置的纹理压缩格式 ETC&#xff1a;使用ETC格式&#xff08;兼容&#xff09; ETC2&#xff1a;使用ETC2格式&#xff08;很多设备不支持&#xff09; ASTC&#xff1a;使用…
阅读更多...
滚雪球学MySQL[4.4讲]：数据库的性能调优详解

滚雪球学MySQL[4.4讲]：数据库的性能调优详解

全文目录&#xff1a; 前言1. 数据库性能调优的重要性2. 数据库性能调优策略2.1 索引优化2.1.1 创建合适的索引示例&#xff1a;创建单列索引和联合索引 2.1.2 避免过度索引2.1.3 使用覆盖索引示例&#xff1a;覆盖索引 2.2 查询优化2.2.1 使用EXPLAIN分析查询示例&#xff1a;…
阅读更多...
常见数据同步工具之实时同步

常见数据同步工具之实时同步

常见数据同步工具之实时同步
阅读更多...
【SQL】重复的邮箱信息

【SQL】重复的邮箱信息

目录 语法 需求 示例 分析 代码 语法 SELECT column_name(s), AGGREGATE_FUNCTION(column_name) FROM table_name WHERE condition GROUP BY column_name(s) ORDER BY column_name(s); GROUP BY 语句主要用于结合聚合函数&#xff08;如 COUNT(), MAX(), MIN(), SUM(), AV…
阅读更多...
2024年9月个人工作生活总结

2024年9月个人工作生活总结

本文为 2024年9月工作生活总结。 研发编码 vuepress构建的几个问题 某vuepress项目&#xff0c;是我在3年多以前自行构想自行着手搞的&#xff0c;主要用于将一些常用的数据文件&#xff08;markdown样式&#xff09;渲染成html网页文件&#xff0c;在自建服务程序里开启访问…
阅读更多...
最新文章

Copyright @ 2022~2023