c/c++补完计划(五): 平衡二叉树和二叉搜索树

前言

来看维基的说明: AVL树：是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是

{\displaystyle O(\log {n})}

。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。 从查找树的角度来看, 还是非常实用的结构, 面试也很喜欢考, 我回想了一下, 在3家以上公司遇到了, 当然有一次是因为我不会红黑树, 被降级要求写AVL树, 是我不配(手动无奈).

平衡二叉树判断

自顶向下

思路是, 左右子树都要是平衡二叉树, 且左右子树的高度差小于2. 核心代码也很简单, 基本就是把思路用代码写出来.

然后就是高度的获取, 当前节点的高度, 就是, 左右子树的高度大的那个+1. 这里你可以用系统的max函数, 也可以自己写一个lambda, 建议自己写一个.

放到力库跑一下, 看到效果还行.

image

自底向上

但是很明显有很多重复计算, 而且思路是自顶向下的. 那么考虑一个自底向上的. 也不用维护数据结构那么复杂, 考虑传入一个height引用.

思路是其实是后序遍历, 先判断左, 后判断右, 最后是当前节点, 也就是中. 当某次不满足时, 会直接返回false, 然后一路返回到顶, 所以复杂度肯定要优于之前的.

image

你可能会觉得有点别扭, 因为这里的true和false似乎可以用height搞定, 那为啥不简化一下.

可以看到, 等于是把之前的与判断拆分了, 当返回-1, 就意味着当前子树不是平衡树, 然后一路返回.

image

二叉搜索树的最近公共祖先

这个题思路很重要, 不是难题, 一个暴力做法, 我直接保存两个查找的路径, 然后比对, 但是问题是什么?

• 要维护一个数组记录路径
• 没有利用起二叉搜索树的特性, 人家帮你弄好了左小右大的树, 你当一般树, 不是很搞笑吗?

那思路其实很简单, 当两个节点都小于当前节点, 说明还未分叉, 继续找; 如果一个大于当前节点, 一个小于当前节点, 就是终止条件了. 当然, 可以先排序两个节点, 这样判断就少了, 不用每次判断2个.

最后

这里没有说到AVL左旋和右旋的问题, 但是实际上不是很难, 还是要自己动动手, 才能记得住.