二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是 O。不过，二叉查找树在频繁的动态更新过程中，可能会出现数的高度远大于 log2^n 的情况，从而导致各个操作的效率下降。在工程中

给定一个二叉树，判断它是否是高度平衡的二叉树。使用实例域变量记录是否与有不满足平衡的节点出现，使用一次递归即可。

LR:先对root->lchild进行左旋，再对root进行右旋。

　　所谓自平衡二叉树，就是当我们插入或删除元素之后，二叉树的高度会自动调整到最小，这样我们就可以在对数时间内查找二叉树内的元素。set.floor // 取set中小于等于x的最大值，没有就返回空set.size() // 返回树的

索引是一种数据结构，用于帮助我们在大量数据中快速定位到我们想要查找的数据。索引最形象的比喻就是图书的目录了。注意这里的大量，数据量大了索引才显得有意义，如果我想要在 [1,2,3,4] 中找到 4 这个数据，直接对全数据检索也很快，没有必要费力气建索引再去

平衡因子 BF为该节点左子树高度 - 右子树高度，绝对值如果 ≤ 1，则二叉树不需要调整。可以计算得到 8 的 BF 为 2，受到破坏且是第一个发现的节点，LL 表示破坏者处于被破坏者左子树的左子树中。对一棵平衡二叉树插入数据，平衡因子没有被破坏就不需要调

显然这种情况会使得二叉搜索树退化成链表。当出现这样的情况，二叉排序树的查找也就退化成了线性查找，所以我们需要合理调整二叉排序树的形态，使得树上的每个结点都尽量有两个子结点，这样整个二叉树的高度就会大约在\ 左右，其中 \(n\) 为结点个数。由于需要对每个

Given a binary tree, determine if it is height-balanced.For this problem, a height-balanced binary tree is defined as:a binary t

本文从属于笔者的数据结构与算法系列文章。因此，我们希望最理想的状态下是使二叉查找树始终处于良好的结构形态。1962年，Adelson-Velsikii和Landis提出了一种结点在高度上相对平衡的二叉查找树，又称为AVL树。

AVL树本质上还是二叉树，但是比二叉搜索树多了一个条件：每个节点的左右子树高度不超过1因为二叉搜索树在极端情况下无限趋近于链表，这种情况下不能体现二叉搜索树的高效率。}AVL树在添加或者删除后，可能导致AVL树失去平衡。失去平衡包括四种：LL(左左)，LR

在计算机科学中，树由称为结点的元素按照层次结构的方式组织而成。与根结点直接相连的结点称为根的子结点，通常子结点本身也有属于它们自己的子结点。通过这种3个成员的结构体，将每个结点的左右指针分别指向该结点的子结点，以此来构建一棵二叉树。如果某个结点没有对应的左