您的位置: 首页 > 文章 > 平衡二叉树 平衡二叉树 分类: 文章 • 2024-06-05 18:55:46 平衡二叉树 定义： 任意的左右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树，二叉平衡树前提是一个二叉排序树。 平衡二叉树的插入示例： 平衡二叉树在插入或删除一个结点时，先检查该操作是否导致了树的不平衡，若是，则在该路径上查找最小的不平衡树，调节其平衡。 4种平衡调整如下(结点的数字仅作标记作用)： 1、LL：右单旋转2、RR：左单旋转3、LR：先左后右旋转4、RL：先右后左旋转平衡二叉树查找：平衡二叉树查找过程等同于二叉排序树相同，因此平衡二叉树查找长度不超过数的长度，及其平均查找长度为O(log2n)。
