希赛教育计算机专业考研专业课辅导招生
希赛教育计算机专业考研专业课辅导视频
希赛教育计算机考研专业课在线测试系统
称二叉树为平衡指的是它或是空树或具有下列特性其左子树和右子树都是平衡二叉树且左右子树深度之差的绝对值不大于例如右侧上的两棵二叉树为平衡树右侧下的两棵二叉树不是平衡树树中结点内的数值称作结点的平衡因子定义为左子树的深度减去右子树的深度换句话说平衡树上所有结点的平衡因子的绝对值均不大于可以证明含有n个结点的平衡二叉树的深度为因此在平衡二叉树上进行查找时和关键字进行比较的次数是和logn等数量级的
平衡处理的原则是保证二叉查找树始终处于平衡状态从空树起（空树是平衡树）每插入一个关键字都需要检查二叉查找树是否失去平衡如因插入新的结点引起不平衡则需对它进行平衡旋转处理如何进行平衡旋转处理在教材和其它参考书中都有详细阐述在此仅以一个例子作简单介绍
