- 分享至
-
加入QQ群享真题
546357334
21计算机考研群 -
关注公众号得干货
启航计算机考研
数据结构之 平衡二叉树
平衡二叉树,是一种二叉排序树,其中每个结点的左子树和右子树的高度差至多等于1。它是一种高度平衡的二叉排序树。高度平衡?意思是说,要么它是一棵空树,要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。
将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF,那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。
平衡二叉树的前提是它是一棵二叉排序树。
距离插入结点最近的,且平衡因子的绝对值大于1的结点为根的子树,称为最小不平衡子树。如下图所示,当插入结点37时,距离它最近的平衡因子的绝对值超过1的结点是58。
【考研党必备学习资料包】:考研真题+免费择校择专业+免费考研复习规划,更有考研课程优惠券等你来加购~名额有限立即领取【领取链接】
【启航教育考研辅导课程推荐】:面授课集训营(冲刺密训,十一特训),专业课一对一辅导,考研网课全程班包含公共课以及专业课,这些课程中都会配有内部讲义以及辅导书和资料,同时会有教研教辅双师模式对大家进行教学以及督学,并配有24小时答疑和模拟测试等,具体详情可直接咨询在线客服老师。
来源:启航考研
责任编辑:yulaoshi