首页
学习
活动
专区
工具
TVP
发布

什么平衡二叉树

前言 上篇文章里面,我们已经学习了二叉搜索树的相关内容,二叉搜索树有一个缺点,在插入数据有序的序列(包括升序和降序),会导致二叉树退化成链表,从而导致在查找,删除,添加时的性能均从O(logN)降低为...平衡二叉树的性质 平衡二叉树本质上特殊的二叉搜索树(二叉排序树),它具有二叉搜索树所有的特点,此外它有自己的特别的性质,如下: (1)它是一棵空树或它的左右两个子树的高度差的绝对值不超过1; (2)平衡二叉树的左右两个子树都是一棵平衡二叉树...什么平衡因子 平衡因子指的是,平衡二叉树在保持平衡的时候,通过平衡因子来判断的,节点的平衡因子 = 该节点的左子树的高度 - 该节点右子树的高度。...(3)左右旋转 如下图与(2)的情况类似,但不同的插入的方式3,1,2,从而导致最后一个2插入的时候,在右子树上导致失衡的,这种情况下比前面的稍微复杂,需要旋转两次来调整平衡。 ?...,AVL平衡二叉树很好的解决了二叉搜索树在遇到有序序列性能退化为O(N)的情况,使得在最坏情况下的搜索效率仍然能够达到O(logN),但这种优化牺牲了插入和删除的性能换来的,故而AVL树并不适合需要频繁插入和删除的场景

7.1K51
您找到你想要的搜索结果了吗?
是的
没有找到

什么平衡二叉树(AVL)

1 为什么要有平衡二叉树 二叉搜索树一定程度上可以提高搜索效率,但是当原序列有序时,例如序列 A = {1,2,3,4,5,6},构造二叉搜索树如图 1.1。...这种左右子树的高度相差不超过 1 的树为平衡二叉树。 2. 定义 平衡二叉查找树:简称平衡二叉树。...例如图 2.1 不是平衡二叉树,因为结点 60 的左子树不是平衡二叉树。 ? 图 2.1 图 2.2 也不是平衡二叉树,因为虽然任何一个结点的左子树与右子树都是平衡二叉树,但高度之差已经超过 1 。...AVL树插入时的失衡与调整 图 5.1 一颗平衡二叉树 ? 图 5.1 在此平衡二叉树插入节点 99 ,树结构变为: ?...也就是说,一棵失衡的树,有可能有多棵子树同时失衡的。而这个时候,我们只要调整最小的不平衡子树,就能够将不平衡的树调整为平衡的树。 平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。

60320

漫画:什么平衡二叉树

————— 第二天 ————— ———————————— 在红黑树当中,我们通过红色结点和黑色结点作为辅助,来判断一颗二叉树是否相对平衡。...而在AVL树当中,我们通过“平衡因子”来判断一颗二叉树是否符合高度平衡。 到底什么AVL树的平衡因子呢? 对于AVL树的每一个结点,平衡因子它的左子树高度和右子树高度的差值。...只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候,这颗二叉树才是一颗合格的AVL树。...举个例子,下图就是一颗典型的AVL树,每个节点旁边都标注了平衡因子: 其中结点4的左子树高度1,右子树不存在,所以该结点的平衡因子1-0=1。...结点7的左子树不存在,右子树高度1,所以平衡因子0-1=-1。 所有的叶子结点,不存在左右子树,所以平衡因子都是0。

60020

学习笔记 | 什么Node.js

开始去了解node.js Node.js简介 Node.js运行在服务端的JavaScript,一个事件驱动I/O服务端Javascript环境。...查看版本: node版本管理工具nvm Node.js应用 Node.js应用的构成: 引入required模块 创建服务器 接收请求与响应请求 创建Node.js应用 步骤一:引入required模块...的回调函数 Node.js异步编程的直接体现就是回调 阻塞代码实例 创建一个文件 input.txt ,内容如下: Hello world!...; 以上代码执行结果如下: $ node main.js 程序执行结束! Hello World! 第一个实例在文件读取完后才执行完程序。...因此,阻塞按顺序执行的,而非阻塞不需要按顺序的,所以如果需要处理回调函数的参数,我们就需要写在回调函数内。

1K20

js什么匿名函数_js函数返回值

js匿名函数的代码如下: (function(){ // 这里忽略jQuery 所有实现 })(); 半年前初次接触jQuery 的时候,我也像其他人一样很兴奋地想看看源码是什么样的。...为什么只有一个匿名函数又没看到运行(当然运行了…… ),就能有jQuery 这么个函数库了?于是,我抱着疑问来到CSDN 。结果相信现在很多人都很清楚了(因为在我之 后也不乏来者,呵呵~ )。...function abc(x,y){ return x+y; } function abc(x,y){ return x+y; }   但是,无论你怎么去定义你的函数,JS 解释器都会把它翻译成一个...闭包   闭包是什么?闭包指某种程序语言中的代码块允许一级函数存在并且在一级函数中所定义的自由变量能不被释放,直到一级函数被释放前,一级函数外也能应用这些未释放的自由变量。   怎样?...所以如果问你那个开篇中的jQuery 代码片段应用了JS 里的什么特性?那么它只是匿名函数与匿名函数的调用而已。但是,它 隐含了闭包的特性,并且随时可以实现闭包应用。

6.9K20

什么Node.js Stream(流)?

什么流?在Node.js中,流(Stream)一种用于处理数据的抽象接口。它提供了一种有效的方式来读取或写入大量数据,而无需一次性将整个数据加载到内存中。...创建可读流在Node.js中,我们可以通过创建一个可读流对象来读取数据。...创建可写流在Node.js中,我们可以通过创建一个可写流对象来写入数据到目标位置。...创建转换流在Node.js中,我们可以通过创建一个转换流对象来实现数据的转换。...本文详细介绍了Node.js中的流的概念、创建方式以及使用方法,并提供了相应的示例代码。希望通过本文,你对Node.js中的流有了更深入的理解,并能够在实际开发中灵活运用流处理数据的能力。

17930

什么Deno,它与Node.js什么不同?

Node.js 的创建者 Ryan Dahl 花了一年半的时间研究 Deno(https://deno.land/),这是一个新的 JavaScript 运行时环境,可以解决Node 的所有问题。...不过早在 2009 年,JavaScript 仍然这种奇怪的小众语言,每个人都在取笑它,而且还确实许多功能。 什么Deno,它的主要特点是什么?...只要你能忍受: import { assertEquals } from "https://deno.land/std/testing/asserts.ts"; 您可能会问,通过 URL 导入包有什么大不了的...包提供程序必须支持版本控制,但从客户端来看,只需在 URL 中设置版本号即可,如下所示:https://unpkg.com/liltest@0.0.5/dist/liltest.js。...由自己决定我们的主要目标是什么,并相应地做出选择。 TypeScript支持开箱即用 Deno 可以无需任何配置文件就能够轻松使用 TypeScript。

2.1K10

什么Node.js,它有什么作用,可以干啥呢?

Node.js:一个基于Chrome V8引擎的JavaScript运行环境 Node.js一个开源的、跨平台的JavaScript运行环境,用于在服务器端运行JavaScript代码。...在使用Node.js的过程中,开发人员需要注意一些问题。首先,由于Node.js单线程的,如果存在长时间运行的计算任务或者I/O阻塞,可能会影响整个应用程序的性能。...其次,由于Node.js的事件循环机制基于回调函数的,因此需要注意避免回调地狱和内存泄漏等问题。...总的来说,Node.js一个功能强大、易于使用的JavaScript运行环境,适用于构建各种类型的服务器端应用程序。...无论Web应用、自动化测试、实时通信还是其他的应用场景,Node.js都可以提供高效、可扩展的解决方案。

20110

《重学数据结构》之什么二叉树

基本概念 树,一种非线性表数据结构: 节点 “树”里面的每个元素 父子关系 连线相邻节点之间的关系 兄弟节点 节点的父节点同一个节点 根节点 没有父节点的节点 叶(子)节点 没有子节点的节点...满二叉树 叶节点全在最底层,除叶节点外,每个节点都有左右两个子节点 完全二叉树 叶节点都在最底下两层,最后一层的叶节点都靠左排列,且除最后一层,其他层节点个数都达到最大 为啥就把最后一层的叶子节点靠左排列的叫完全二叉树...要搞清楚完全二叉树为啥这么定义,先学习 如何存储二叉树? 基于指针或者引用的二叉链式存储法 每个节点有三个字段: 一个存储数据 另两个指向左右子节点的指针 大部分二叉树代码都是通过这种结构实现的。...若是非完全二叉树,就会浪费较多存储空间: 所以完全二叉树用数组存储最省内存,就不像链式存储法,还要存储左、右子节点的指针。所以完全二叉树要求最后一层的子节点都靠左。...postOrder(root->right); print root // 此处为伪代码,表示打印root节点 } 时间复杂度 每个节点最多会被访问两次,所以遍历操作的时间复杂度,跟节点的个数n成正比,也就是说二叉树遍历的时间复杂度

57920

《重学数据结构》之什么二叉树

基本概念 树,一种非线性表数据结构: 节点 “树”里面的每个元素 父子关系 连线相邻节点之间的关系 兄弟节点 节点的父节点同一个节点 根节点 没有父节点的节点 叶(子)节点 没有子节点的节点...满二叉树 叶节点全在最底层,除叶节点外,每个节点都有左右两个子节点 完全二叉树 叶节点都在最底下两层,最后一层的叶节点都靠左排列,且除最后一层,其他层节点个数都达到最大 为啥就把最后一层的叶子节点靠左排列的叫完全二叉树...要搞清楚完全二叉树为啥这么定义,先学习 如何存储二叉树? 基于指针或者引用的二叉链式存储法 每个节点有三个字段: 一个存储数据 另两个指向左右子节点的指针 大部分二叉树代码都是通过这种结构实现的。...若是非完全二叉树,就会浪费较多存储空间: 所以完全二叉树用数组存储最省内存,就不像链式存储法,还要存储左、右子节点的指针。所以完全二叉树要求最后一层的子节点都靠左。...postOrder(root->right); print root // 此处为伪代码,表示打印root节点 } 时间复杂度 每个节点最多会被访问两次,所以遍历操作的时间复杂度,跟节点的个数n成正比,也就是说二叉树遍历的时间复杂度

31510

让你更好的理解什么二叉树

二叉树 6.2.1 二叉树的概念 二叉树(Binary Tree)结点的有限集合,这个集合或者为空,或者由一个根结点和两颗互不相交的分别称为左子树和右子树的二叉树组成。...二叉树与树的区别:二叉树中每个结点的孩子至多不超过两个,而树对结点的孩子数无限制;另外,二叉树中结点的子树有左右之分,而树的子树没有次序。思考一棵度为2的树与一棵二叉树什么区别?...【例6.2】树与二叉树什么区别? 区别有两点: (1)二叉树的一个结点至多有两个子树,树则不然; (2)二叉树的一个结点的子树有左右之分,而树的子树没有次序。...6.2.4 二叉树的遍历 1.二叉树遍历的概念 二叉树的遍历指沿某条搜索路径访问二叉树,对二叉树中的每个结点访问一次且仅一次。这里的“访问”实际上指对结点进行某种操作。...图6.17 所示的二叉树中的结点C,其前序前趋结点D,前序后继结点E; 中序前趋结点E,中序后继结点F; 后序前趋结点F,后序后继结点A。

2.4K110

什么js动态类型语言呢?

以下一些示例来说明 JavaScript 的动态类型特性: 变量类型的弱化: let x = 10; // x被推断为number类型 x = "Hello"; // 现在x的类型变为string...# ts VS js (动态 vs 静态) 动态类型语言直接运行时对变量检测,无需声明变量类型 静态类型语言需声明变量类型,在编译时对变量类型检测 JavaScript 被称为动态类型语言,因为它在运行时对变量的类型进行推断和处理...以下一些 TypeScript 的静态类型示例: let variable: number = 10; // 变量被声明为数字类型 console.log(variable); // 输出: 10...# typeScript 强型语言还是弱类型语言? 类型系统按照「是否允许隐式类型转换」来分类,可以分为强类型和弱类型。...TypeScript 完全兼容 JavaScript 的,它不会修改 JavaScript 运行时的特性,所以它们都是弱类型。

20810

什么Node.js Buffer(缓冲区)?

在计算机内存中,缓冲区(Buffer)一块连续的内存空间,用于临时存储数据。缓冲区可以保存各种类型的数据,例如字符串、图像、音频等。...在 Node.js 中,Buffer 一个全局对象,用于处理二进制数据。创建缓冲区在 Node.js 中,可以使用以下方式创建缓冲区:1....缓冲区与字符串的转换Node.js 提供了方便的方法来在缓冲区和字符串之间进行转换。...总结Node.js 的缓冲区一种用于处理二进制数据的机制,提供了创建、操作和转换缓冲区的方法。通过使用缓冲区,可以高效地处理各种类型的数据,并应用到文件操作、网络通信、图像处理等多个领域。...掌握缓冲区的原理和使用方法,对于开发 Node.js 应用来说是非常重要的。

24140
领券