平衡二叉树深度公式 在平衡二叉树中,插入一个节点后引起不平衡,设离插入节点最近的不平衡点是A,并且已知A的左右孩子的平衡节点?
浏览量:2525
时间:2021-03-11 18:19:13
作者:admin
在平衡二叉树中,插入一个节点后引起不平衡,设离插入节点最近的不平衡点是A,并且已知A的左右孩子的平衡节点?
因为节点a的右子树的平衡因子为0,所以只能是插在左子树上的节点,也就是说节点a的左子树被加高了。如果平衡因子的定义是左子树的高度右子树的高度,则节点a的平衡因子必须为零如果平衡因子的定义是右子树的高度左子树的高度,则a的平衡因子必须为-2,并且需要向右旋转,也就是说,RR型旋转
二叉排序树也称为二叉搜索树。它要么是空树,要么具有以下属性:(1)如果其左子树不为空,则左子树上所有节点的值都小于根节点的值。(2) 如果右子树不为空,则右子树中所有节点的值都大于根节点的值。(3) 左右子树也是二叉排序树。
平衡二叉树是具有以下属性的空树或二叉排序树:(1)左右子树都是平衡二叉树;(2) 左右子树高差的绝对值
如果左右子树的高差称为节点x的平衡因子,则用BF(x)表示。
然后我们从平衡二叉树的定义知道:BF(x)=x左子树深度-x右子树深度
版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。