接上一篇《AVL 树旋转及 JS 实现，平衡树支棱起来~》，来了个难的，再来个相对简单的，别一直搁那“旋转树”而打击了“种二叉树”的自信心~~
遍历每个结点，借助一个获取树深度的递归函数，根据该结点的左右子树高度差判断是否平衡，然后递归地对左右子树进行判断。
平衡二叉树最早是由两位前苏联数学家G.M.Adelsen-Velskii和E.M.Landis提出的。这是一个高度平衡的二进制位。那么满足哪两点才是平衡二叉树？怎样才能不破坏二叉树的平衡性？
今天的博客是在上一篇博客的基础上进行的延伸。上一篇博客我们主要聊了二叉排序树，详情请戳《二叉排序树的查找、插入与删除》。本篇博客我们就在二叉排序树的基础上来聊聊平衡二叉树，也叫AVL树，AVL是发明平衡二叉树的两个科学家的名字的缩写，在此就不做深究了。其实平衡二叉树就是二叉排序树的一种，比二叉排序树多了一个平衡的条件。在一个平衡二叉树中，一个结点的左右子树的深度差不超过1。 本篇博客我们就依照平衡二叉树的特点，在创建二叉排序树的同时要保证结点的左右子树的深度差不超过1的规则。当我们往二叉排序树中插入结点时，
在上一篇《无死角“盘”它！二分查找树》中提到了：平衡二叉树的目的就是使得平均查找长度最短。那么这里就引出两个问题：
面试过程中，多多少少会问一点数据结构（二叉树）的问题，今天我们来复习一下二叉树的相关问题，文末总结。
不知道前端小伙伴们都了解“红黑树”吗？本瓜，之前听是听过，但是它到底是干嘛的，并不十分清楚。在认识了平衡二叉树、AVL 树之后，现在已经来到了这个节点，必须来看下“红黑树”了！
上篇教程学院君给大家介绍了二叉排序树，并且提到理想情况下，二叉排序树的插入、删除、查找时间复杂度都是 O(logn)，非常高效，而且它是一种动态的数据结构，插入删除性能和查找一样好，不像之前提到的二分查找，虽然查找性能也是 O(logn)，但是需要先对线性表进行排序，而排序的最好时间复杂度也是 O(nlogn)，所以二分查找不适合动态结构的排序。
为了避免树的高度增长过快，降低二叉排序树的性能，我们规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树，简称平衡树（AVL树）。定义结点左子树和右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是-1、0或1。
出现背景 前文已经研究过普通的二叉树， 为什么要用二叉树呢？因为二叉树的结构可以实现二分法查找的效果。
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。如下图
题目：输入一颗二叉树的根结点，判断该树是不是平衡二叉树。 如果某二叉树中任意结点的左右子树的高度相差不超过1，那么它就是一棵平衡二叉树。 分析：所谓平衡二叉树就是要确保每个结点的左子树与右子树的高度差在－1到1之间。 由于之前一题已经给出了二叉树高度的计算方法，因此本题最直观的思路就是分别计算每个结点的左子树高和右子树高，从而判断一棵树的所有结点是否均为平衡二叉树。 /** * 题目：输入一颗二叉树的根结点，判断该树是不是平衡二叉树。 * 如果某二叉树中任意结点的左右子树的高度相差不超过1，那么
树的平衡检测是指判断一棵树是否为平衡二叉树，即每个节点的左右子树高度差不超过1。在本文中，我们将深入讨论如何实现树的平衡检测算法，提供Python代码实现，并详细说明算法的原理和步骤。
这道题是判断给定的二叉树是不是平衡二叉树，如果一棵二叉树是平衡二叉树，那么其所有子树也是平衡二叉树。
平衡二叉树 对于二叉查找树，尽管查找、插入及删除操作的平均运行时间为O(logn)，但是它们的最差运行时间都是O(n),原因在于对树的形状没有限制。 平衡二叉树又称为AVL树，它或者是一棵空树，或者是有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。二叉树的的平衡因子BF为：该结点的左子树的深度减去它的右子树的深度，则平衡二叉树的所有结点的平衡因子为只可能是：-1、0和1 一棵好的平衡二叉树的特征： （1）保证有n个结点的树的高度为O(logn) （2）容易维护，
在之前的系列中，我们已经学习了二叉树最大深度以及DFS，如果不会可以先查看之前的文章。今天我们将对其进行应用，直接看题目。
。影响时间复杂度的因素即为二叉树的高，为了尽量避免树中每层上只有一个节点的情况，这里引入平衡二叉树。
平衡二叉树也叫自平衡二叉搜索树（Self-Balancing Binary Search Tree），所以其本质也是一颗二叉搜索树，不过为了限制左右子树的高度差，避免出现倾斜树等偏向于线性结构演化的情况，所以对二叉搜索树中每个节点的左右子树作了限制，左右子树的高度差称之为平衡因子，树中每个节点的平衡因子绝对值不大于1，此时二叉搜索树称之为平衡二叉树。自平衡是指，在对平衡二叉树执行插入或删除节点操作后，可能会导致树中某个节点的平衡因子绝对值超过1，即平衡二叉树变得“不平衡”，为了恢复该节点左右子树的平衡，此时需要对节点执行旋转操作。
首先要理解一个概念：什么是平衡二叉树，如果某二叉树中任意的左右子树深度相差不超过1，那么他就是一颗平衡二叉树。如下图：
完整高频题库仓库地址：https://github.com/hzfe/awesome-interview
学如逆水行舟，不进则退。心如平原野马，易放难收。春节假期，基本结束，是该回归正常的节奏了。
树中的节点数在范围 [0, 5000] 内 -104 <= Node.val <= 104
题目：输入一颗二叉树的根结点，判断该树是不是平衡二叉树。 如果某二叉树中任意结点的左右子树的高度相差不超过1，那么它就是一棵平衡二叉树。 分析：所谓平衡二叉树就是要确保每个结点的左子树与右子树的高度差在－1到1之间。 由于之前一题已经给出了二叉树高度的计算方法，因此本题最直观的思路就是分别计算每个结点的左子树高和右子树高，从而判断一棵树的所有结点是否均为平衡二叉树。 上一篇博客中采用了一种较为常规的思路，但由于涉及到重复计算子树的高度，因此性能并不好，接下来提出一种从下而上，依次判断每个子树是否为
相信不少同学和我一样，在刚学完数据结构后开始刷算法题时，遇到递归的问题总是很头疼，而一看解答，却发现大佬们几行递归代码就优雅的解决了问题。从我自己的学习经历来看，刚开始理解递归思路都很困难，更别说自己写了。
关键思想: 递归遍历每个结点的左右树 若左树或者右树不是平衡二叉树则该结点树也不少平衡二叉树 若左树或者右树都是平衡二叉树则判断左右树高度之差,如果高度差大于1也是不平衡二叉树,否则该结点是平衡二叉树,高度是左右子树中较大值+1
示例 1： 输入：root = [3,9,20,null,null,15,7] 输出：true
大家都知道MySQL数据库选择的是B+Tree作为索引的数据结构，那为什么会选择B+Tree呢？
平衡二叉树的递归定义: (1)空树。 (2)他的左子树和右子树都是平衡二叉树，并且左子树和右子树的高度差的绝对值不会超过1(<=1)。
二叉树为高度平衡二叉树，则二叉树中以任意节点为根节点的子树皆为高度平衡二叉树。仿照后序遍历二叉树每个节点，若左子树和右子树皆为高度平衡二叉树，则进一步判断左子树与右子树高度差是否大于一即可。
在线索二叉树中，除了左右孩子指针，还添加了两个额外的指针：前驱指针和后继指针。这两个指针分别指向当前节点的前驱节点和后继节点。
平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
解题思路： 根据二叉树的定义，我们可以递归遍历二叉树的每一个节点来，求出每个节点的左右子树的高度，如果每个节点的左右子树的高度相差不超过1，按照定义，它就是一颗平衡二叉树。
今日偷懒，在家忙着码代码，所以就分享一道简单点的题目~在之前的系列中，我们已经学习了二叉树的深度以及DFS，如果不会可以先查看之前的文章。今天我们将对其进行应用，直接看题目：
平衡二叉树:它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
日常中我们见到的二叉树应用有，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，以及B-Tree，B+-Tree在文件系统，都是通过红黑树去实现的。虽然之前写过《再谈堆排序：堆排序算法流程步骤透解—最大堆构建原理》但是二叉树的基本性质，对我来说，从入门到放弃是搞了好几回。
前两篇文章谈了B-Tree和B+Tree，它们属于多路平衡树，所有叶子结点都在同一层，除了这两种平衡树， 我们熟知的还有平衡二叉树和红黑树。这一篇文章就来看看如何构建红黑树
平衡二叉树(Balanced binary tree)又称为AVL树，是一种特殊的二叉排序树，且左右子树的高度之差的绝对值不超过1.
输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
队列是数据结构中比较重要的一种类型，它支持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们生活中的排队类似。
世界分为三条线，两实一虚： 1. 当前时间线： 黑帽威廉时间线，凡是有黑帽威廉的都在当前时间 2. 历史时间线：白帽威廉时间线 （35年前），凡是有白帽威廉的都在历史时间，属于回忆 3. 虚拟时间线： 女主脑海中的闪回，脑补画面，与时间没直接关系，可在多个时间线跳跃，也可以是完全脑补的画面。 当女主是穿蓝色的连衣裙、自言自语时属于这条虚拟时间线。
代码来自算法第四版 红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。 红黑树实际上是由2-3-4树转换而来，红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构，能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。
听名字还是比较好理解的，就是每个节点有两个分叉的树。但是又不要求一定有两个节点，只要小于等于2个节点就可以。
根据本题对平衡二叉树的定义：如果二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则是平衡二叉树。根据题目定义，解题思路如涌泉般喷发，老规矩，递归破题(若一棵二叉树是平衡二叉树，必须满足其所有子树也都是平衡二叉树才行)，且递归的顺序可以是自顶向下或者自底向上，如上两种递归顺序我都给大家讲解一下。
索引定义：索引是依靠某些数据结构和算法来组织数据，最终引导用户快速检索出所需要的数据
本文所述的各种数据结构(二叉树等)，均不考虑重复值的情况，本文简述各种数据结构的区别仅仅只是为了理解MySQL索引的需要而做的铺垫。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
