点击上面关注，每天进步一点点

正文的思维导图

简单叙述

平衡二叉树暂且不谈，我们一个人说，这个更容易理解。

先说二叉树，就平衡条件而言，没有那么华丽的理论。 我只是想阅读理解和写作。

二叉树

什么是二叉树？ 二叉树的数据结构，顾名思义，只有两个叉。 在数据结构中，操作性能远远高于线性结构，具有o (高度)索引性能。 具有与线性结构相同的空间复杂性，特性如下。

每个节点最多只有两个儿子。 左儿子小，右儿子大。 (大小遵循默认的比较规则。 在本例中，用int进行比较。 )线行找7和叉数找7

线性检索7

二叉树找7

okay先生，我想聪明的人已经明白了，二叉树搜索用了两次，线性结构用了五次。

说白了，是二叉树结构。 每次听到一个节点，都会越来越接近我的目标，但线性的情况不是这样。 必须一个一个地问。

说到这里，我想有个博友提出疑问，线性找的话，7正好在最前面吗？ 那不是很快就找到了吗？

哈哈，你为什么不上天呢---。 还是第一个。 开玩笑。

这就是二叉树索引的好地方。 看图比码字清晰多了。

平衡条件

那么，什么是平衡呢？ 实际上，其中一个节点的子节点的高度差必须小于2

最初的双重愿望平衡树

从下往下数，第一个高度是一。 数一下符合日常生活的数量吧。 5:———1高|4、7、23、71———2高|6、50———3高| 15 ———4高如节点6，4和7的高均为2，50！ 难点是递归的

递归搜索

为了了解递归的深度，我们添加了一些节点

每次前向橙色线滚动时，每次递归滚动前向橙色线时，都会进入方法堆栈！ 递归的深度取决于线走了多少次，这次调查堆栈有多深，除去路线，共追溯了4次堆栈的难点

追溯插入

请不要在意这个旋转操作。 如图所示，基于递归，沿着线追溯理解吧

每当橙色线向相反方向滚动时，进行递归操作的各节点每当进行递归操作时，在递归的轨迹上每次递归都有回溯，因此，首先在完成相关操作(追加或删除)之后，能够判定平衡的4种旋转

p>

左左类型旋转

博主尽量放慢了速度，让大家看清楚究竟旋转是如何进行的,这是一个插入操作，我们看到在不平衡的时候，进行了左旋转，这里我们看到

正向插入，递归3-2-1逆向回溯，1-2 判断平衡条件 ，是平衡的再次回溯，2-3，3的左边高度为2，右边没有节点为0，那么2-0 > 1，不平衡！

到这里我们基本上理解了平衡的判断，下面正式说一下旋转:

判断不平衡边 在3节点判定，不平衡，那么左边高，我们需要调整左边，获取左边节点2判断旋转类型 这时候我们拿到节点2，判断节点2哪边高。左边高，为左左类型。右边高为左右旋转类型，我们先不管旋转操作 3.left = 2.right; 2.right = 3; 重新计算，2和3节点的高度

右右类型旋转[同上，不再叙述]

左右类型旋转

右左类型旋转

到此旋转就说完了，希望大家好好的理解第一个左左类型!（理解了一个也就都理解了 ）

后续部分没有讲是因为说太多反而更乱。

后续的理解不了没关系，我们代码在看。

代码基础部分

node类

高度计算

插入操作

旋转

insert

删除操作

以上就是难点插入和删除的实现了， 没有过多阐述，是因为大家如果真的理解了上面说明的理论， 那么应该没有问题来理解这些code。

当然有任何问题大家可以在留言区回复我 ，欢迎大家指正!

4种遍历

前序遍历 根左右中序遍历 左跟右后序遍历 左右根层级遍历 从root开始，一层层

https://blog.csdn.net/zhang6622056/article/details/82698859