数据结构第10节：平衡树

平衡树是一种特殊的二叉搜索树，它的设计目的是为了保持树的平衡，从而保证所有操作的时间复杂度保持在O(log n)，即使在最坏的情况下也是如此。最常见的平衡树之一是AVL树，它是以发明者G.M. Adelson-Velsky和E.M. Landis的名字命名的。

在AVL树中，任何节点的两个子树的高度最大差别不超过1。这意味着AVL树总是尽可能地保持平衡，从而优化了搜索、插入和删除操作的效率。

AVL树的关键概念：

  1. 平衡因子：一个节点的平衡因子是其右子树的高度减去其左子树的高度。平衡因子可以是-1、0或1。

  2. 旋转：当插入或删除操作破坏了树的平衡时，AVL树会执行一系列的旋转操作来重新平衡树。旋转分为以下几种：

    • 单旋转：右旋（Right Rotation）和左旋（Left Rotation）。
    • 双旋转：右旋后再左旋（Right-Left Rotation）或左旋后再右旋（Left-Right Rotation）。

Java实现案例：

我们可以通过下面的Java代码来实现一个基本的AVL树：

public class AVLTree<T extends Comparable<T>> {private Node<T> root;private static class Node<T> {T data;Node<T> left, right;int height;Node(T data) {this.data = data;height = 1;}}private int height(Node<T> N) {if (N == null)return 0;return N.height;}private int getBalance(Node<T> N) {if (N == null)return 0;return height(N.right) - height(N.left);}private Node<T> rightRotate(Node<T> y) {Node<T> x = y.left;Node<T> T2 = x.right;x.right = y;y.left = T2;y.height = Math.max(height(y.left), height(y.right)) + 1;x.height = Math.max(height(x.left), height(x.right)) + 1;return x;}private Node<T> leftRotate(Node<T> x) {Node<T> y = x.right;Node<T> T2 = y.left;y.left = x;x.right = T2;x.height = Math.max(height(x.left), height(x.right)) + 1;y.height = Math.max(height(y.left), height(y.right)) + 1;return y;}private Node<T> insert(Node<T> node, T key) {if (node == null)return new Node<>(key);if (key.compareTo(node.data) < 0)node.left = insert(node.left, key);else if (key.compareTo(node.data) > 0)node.right = insert(node.right, key);elsereturn node;node.height = 1 + Math.max(height(node.left), height(node.right));int balance = getBalance(node);// Left Left Caseif (balance > 1 && key.compareTo(node.left.data) < 0)return rightRotate(node);// Right Right Caseif (balance < -1 && key.compareTo(node.right.data) > 0)return leftRotate(node);// Left Right Caseif (balance > 1 && key.compareTo(node.left.data) > 0) {node.left = leftRotate(node.left);return rightRotate(node);}// Right Left Caseif (balance < -1 && key.compareTo(node.right.data) < 0) {node.right = rightRotate(node.right);return leftRotate(node);}return node;}public void insert(T key) {root = insert(root, key);}// ... 其他方法如删除、查找、遍历等
}

应用案例：

假设我们要构建一个AVL树来存储一组整数，并保持树的平衡状态。我们可以这样使用：

public class Main {public static void main(String[] args) {AVLTree<Integer> avlTree = new AVLTree<>();avlTree.insert(10);avlTree.insert(20);avlTree.insert(30);avlTree.insert(40);avlTree.insert(50);avlTree.insert(25);// 在此之后，avlTree应该是一个平衡的AVL树}
}

以上代码展示了如何使用AVL树插入一些整数值，并自动调整树的平衡。在实际应用中，AVL树可以用于各种需要高效搜索、插入和删除操作的场景，比如数据库索引、符号表等。

下面，我将补充AVL树的删除、查找以及遍历方法。

删除操作

删除操作在AVL树中比较复杂，因为它涉及到保持树的平衡。在删除节点后，需要检查并修复可能的不平衡。

private Node<T> delete(Node<T> root, T key) {if (root == null)return root;if (key.compareTo(root.data) < 0)root.left = delete(root.left, key);else if (key.compareTo(root.data) > 0)root.right = delete(root.right, key);else {if (root.left == null)return root.right;else if (root.right == null)return root.left;root.data = minValue(root.right);root.right = delete(root.right, root.data);}root.height = Math.max(height(root.left), height(root.right)) + 1;int balance = getBalance(root);if (balance > 1 && getBalance(root.left) >= 0)return rightRotate(root);if (balance < -1 && getBalance(root.right) <= 0)return leftRotate(root);if (balance > 1 && getBalance(root.left) < 0) {root.left = leftRotate(root.left);return rightRotate(root);}if (balance < -1 && getBalance(root.right) > 0) {root.right = rightRotate(root.right);return leftRotate(root);}return root;
}private T minValue(Node<T> node) {T minv = node.data;while (node.left != null) {minv = node.left.data;node = node.left;}return minv;
}

查找操作

查找操作在AVL树中相对简单，遵循二叉搜索树的查找规则。

public boolean contains(T key) {return search(root, key) != null;
}private Node<T> search(Node<T> node, T key) {if (node == null || key.equals(node.data))return node;if (key.compareTo(node.data) < 0)return search(node.left, key);elsereturn search(node.right, key);
}

遍历操作

遍历操作包括前序遍历、中序遍历和后序遍历，这里展示中序遍历。

public void inorderTraversal() {inorder(root);
}private void inorder(Node<T> node) {if (node != null) {inorder(node.left);System.out.print(node.data + " ");inorder(node.right);}
}

主方法使用示例

将上述代码整合进AVLTree类中，然后在main方法中使用：

public class Main {public static void main(String[] args) {AVLTree<Integer> avlTree = new AVLTree<>();avlTree.insert(10);avlTree.insert(20);avlTree.insert(30);avlTree.insert(40);avlTree.insert(50);avlTree.insert(25);System.out.println("Inorder traversal of the constructed AVL tree is");avlTree.inorderTraversal();System.out.println();System.out.println("Deleting key 40");avlTree.delete(40);System.out.println("Inorder traversal after deletion is");avlTree.inorderTraversal();System.out.println();System.out.println("Searching for key 25: " + avlTree.contains(25));System.out.println("Searching for key 60: " + avlTree.contains(60));}
}

这段代码演示了如何插入元素、遍历AVL树、删除元素以及查找元素。

以下是前序遍历和后序遍历的代码实现，我们将它们添加到之前的AVLTree类中：

前序遍历

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

public void preorderTraversal() {preorder(root);
}private void preorder(Node<T> node) {if (node != null) {System.out.print(node.data + " ");preorder(node.left);preorder(node.right);}
}

后序遍历

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

public void postorderTraversal() {postorder(root);
}private void postorder(Node<T> node) {if (node != null) {postorder(node.left);postorder(node.right);System.out.print(node.data + " ");}
}

更新主方法示例

我们更新main方法来演示这些遍历方法：

public class Main {public static void main(String[] args) {AVLTree<Integer> avlTree = new AVLTree<>();avlTree.insert(10);avlTree.insert(20);avlTree.insert(30);avlTree.insert(40);avlTree.insert(50);avlTree.insert(25);System.out.println("Inorder traversal of the constructed AVL tree is");avlTree.inorderTraversal();System.out.println();System.out.println("Preorder traversal of the constructed AVL tree is");avlTree.preorderTraversal();System.out.println();System.out.println("Postorder traversal of the constructed AVL tree is");avlTree.postorderTraversal();System.out.println();System.out.println("Deleting key 40");avlTree.delete(40);System.out.println("Inorder traversal after deletion is");avlTree.inorderTraversal();System.out.println();System.out.println("Searching for key 25: " + avlTree.contains(25));System.out.println("Searching for key 60: " + avlTree.contains(60));}
}

这段代码展示了如何使用AVL树的各种遍历方法，包括中序遍历、前序遍历和后序遍历，以及插入、删除和查找操作。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/370645.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

跨越语言的界限：Vue I18n 国际化指南

跨越语言的界限：Vue I18n 国际化指南

前言 &#x1f4eb; 大家好&#xff0c;我是南木元元&#xff0c;热爱技术和分享&#xff0c;欢迎大家交流&#xff0c;一起学习进步&#xff01; &#x1f345; 个人主页&#xff1a;南木元元 目录 国际化简介 vue-i18n 安装和配置 创建语言包 基本使用 切换语言 动态翻…
阅读更多...
大数据Spark 面经

大数据Spark 面经

1: Spark 整体架构 Spark 是新一代的大数据处理引擎&#xff0c;支持批处理和流处理&#xff0c;也还支持各种机器学习和图计算&#xff0c;它就是一个Master-worker 架构&#xff0c;所以整个的架构就如下所示&#xff1a; 2: Spark 任务提交命令 一般我们使用shell 命令提…
阅读更多...
深入理解TCP协议格式（WireShark分析）

深入理解TCP协议格式（WireShark分析）

传输控制协议&#xff08;TCP&#xff09;是互联网中最为关键的通信协议之一。了解TCP协议的细节不仅对于网络工程师至关重要&#xff0c;对于任何涉及网络通信的软件开发人员而言都是必备的知识。本文旨在深入探讨TCP协议&#xff0c;从协议的基本概述到其工作机制&#xff0c…
阅读更多...
237 删除链表中的节点

237 删除链表中的节点

题目 有一个单链表的 head&#xff0c;我们想删除它其中的一个节点 node。 给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。 链表的所有值都是 唯一的&#xff0c;并且保证给定的节点 node 不是链表中的最后一个节点。 删除给定的节点。注意&#xff0c;删…
阅读更多...
用户身份和文件权限

用户身份和文件权限

前言&#xff1a;本博客仅作记录学习使用&#xff0c;部分图片出自网络&#xff0c;如有侵犯您的权益&#xff0c;请联系删除 目录 一、用户身份与能力 二、文件权限与归属 三、文件的特殊权限 四、文件的隐藏属性 五、文件访问控制列表 六、su命令和sudo服务 致谢 一、…
阅读更多...
动手学深度学习（Pytorch版）代码实践 -计算机视觉-48全连接卷积神经网络（FCN）

动手学深度学习（Pytorch版）代码实践 -计算机视觉-48全连接卷积神经网络（FCN）

48全连接卷积神经网络&#xff08;FCN&#xff09; 1.构造函数 import torch import torchvision from torch import nn from torch.nn import functional as F import matplotlib.pyplot as plt import liliPytorch as lp from d2l import torch as d2l# 构造模型 pretrained…
阅读更多...
调试支付分回调下载平台证书

调试支付分回调下载平台证书

之前的原生代码放到webman里面&#xff0c;死活跑不通 没办法&#xff0c;只能用esayWeChat6.7 &#xff08;自行下载&#xff09; 它里面配置要用到平台证书 平台证书又要用到 composer require wechatpay/wechatpay 但是请求接口之前&#xff0c;你先要用到一个临时的平台…
阅读更多...
linux下高级IO模型

linux下高级IO模型

高级IO 1.高级IO模型基本概念1.1 阻塞IO1.2 非阻塞IO1.3 信号驱动IO1.4 IO多路转接1.5 异步IO 2. 模型代码实现2.1 非阻塞IO2.2 多路转接-selectselect函数介绍什么才叫就绪呢&#xff1f;demoselect特点 2.3 多路转接-pollpoll函数介绍poll优缺点demo 2.4 多路转接-epoll&…
阅读更多...
【算法笔记自学】第 5 章 入门篇（3）——数学问题

【算法笔记自学】第 5 章 入门篇（3）——数学问题

5.1简单数学 #include <cstdio> #include <algorithm> using namespace std; bool cmp(int a,int b){return a>b; } void to_array(int n,int num[]){for(int i0;i<4;i){num[i]n%10;n /10;} } int to_number(int num[]){int sum0;for(int i0;i<4;i){sumsu…
阅读更多...
移动端UI风格营造舒适氛围

移动端UI风格营造舒适氛围

移动端UI风格营造舒适氛围
阅读更多...
Spring容器Bean之XML配置方式

Spring容器Bean之XML配置方式

一、首先看applicationContext.xml里的配置项bean 我们采用xml配置文件的方式对bean进行声明和管理&#xff0c;每一个bean标签都代表着需要被创建的对象并通过property标签可以为该类注入其他依赖对象&#xff0c;通过这种方式Spring容器就可以成功知道我们需要创建那些bean实…
阅读更多...
cs224n作业3 代码及运行结果

cs224n作业3 代码及运行结果

代码里要求用pytorch1.0.0版本&#xff0c;其实不用也可以的。 【删掉run.py里的assert(torch.version “1.0.0”)即可】 代码里面也有提示让你实现什么&#xff0c;弄懂代码什么意思基本就可以了&#xff0c;看多了感觉大框架都大差不差。多看多练慢慢来&#xff0c;加油&am…
阅读更多...
Camunda 整合Springboot 实战篇

Camunda 整合Springboot 实战篇

1.导入依赖 <dependency><groupId>org.camunda.bpm.springboot</groupId><artifactId>camunda-bpm-spring-boot-starter</artifactId><version>7.18.0</version></dependency><dependency><groupId>org.camunda.b…
阅读更多...
C语言图书馆管理系统（管理员版）

C语言图书馆管理系统（管理员版）

案例&#xff1a;图书馆管理系统&#xff08;管理员版&#xff09; 背景&#xff1a; 随着信息技术的发展和普及&#xff0c;传统的图书馆管理方式已经无法满足现代图书馆高效、便捷、智能化的管理需求。传统的手工登记、纸质档案管理不仅耗时耗力&#xff0c;而且容易出现错…
阅读更多...
剖析DeFi交易产品之UniswapV3：交易路由合约

剖析DeFi交易产品之UniswapV3：交易路由合约

本文首发于公众号&#xff1a;Keegan小钢 SwapRouter 合约封装了面向用户的交易接口&#xff0c;但不再像 UniswapV2Router 一样根据不同交易场景拆分为了那么多函数&#xff0c;UniswapV3 的 SwapRouter 核心就只有 4 个交易函数&#xff1a; exactInputSingle&#xff1a;指…
阅读更多...
华为机试HJ34图片整理

华为机试HJ34图片整理

华为机试HJ34图片整理 题目&#xff1a; 想法&#xff1a; 将输入的字符串中每个字符都转为ASCII码&#xff0c;再通过快速排序进行排序并输出 input_str input() input_list [int(ord(l)) for l in input_str]def partition(arr, low, high):i low - 1pivot arr[high]f…
阅读更多...
matlab 有倾斜的椭圆函数图像绘制

matlab 有倾斜的椭圆函数图像绘制

matlab 有倾斜的椭圆函数图像绘制 有倾斜的椭圆函数图像绘制xy交叉项引入斜线负向斜线成分正向斜线成分 x^2 y^2 xy 1 &#xff08;负向&#xff09;绘制结果 x^2 y^2 - xy 1 &#xff08;正向&#xff09;绘制结果 有倾斜的椭圆函数图像绘制 为了确定椭圆的长轴和短轴的…
阅读更多...
【Python】MacBook M系列芯片Anaconda下载Pytorch，并开发一个简单的数字识别代码（附带踩坑记录）

【Python】MacBook M系列芯片Anaconda下载Pytorch，并开发一个简单的数字识别代码（附带踩坑记录）

文章目录 配置镜像源下载Pytorch验证使用Pytorch进行数字识别 配置镜像源 Anaconda下载完毕之后&#xff0c;有两种方式下载pytorch&#xff0c;一种是用页面可视化的方式去下载&#xff0c;另一种方式就是直接用命令行工具去下载。 但是由于默认的Anaconda走的是外网&#x…
阅读更多...
9 redis,memcached,nginx网络组件

9 redis,memcached,nginx网络组件

课程目标： 1.网络模块要处理哪些事情 2.reactor是怎么处理这些事情的 3.reactor怎么封装 4.网络模块与业务逻辑的关系 5.怎么优化reactor? io函数 函数调用 都有两个作用：io检测 是否就绪 io操作 1. int clientfd = accept(listenfd, &addr, &len); 检测 全连接队列…
阅读更多...
技术派Spring事件监听机制及原理

技术派Spring事件监听机制及原理

Spring事件监听机制是Spring框架中的一种重要技术&#xff0c;允许组件之间进行松耦合通信。通过使用事件监听机制&#xff0c;应用程序的各个组件可以在其他组件不直接引用的情况下&#xff0c;相互发送和接受消息。 需求 在技术派中有这样一个需求&#xff0c;当发布文章或…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023