平衡二叉树 有四种使其变为平衡的方法。
分别如何
LL型
单向右旋平衡处理:由于A的左子树根结点的左子树插入了一个节点,A的平衡因子由1增为2,是A为根的子树失去平衡,需进行一次向右的顺时针旋转操作。
RR 型
单向左旋平衡处理:由于A的右子树根结点的右子树上插入节点,A的平衡因此由-1变为-2,使A失去平衡。进行一次向左的逆时针旋转
LR型
由于A的左子树的根的右子树插入节点 使其失去平衡。进行两次旋转,先左旋后右旋
RL型
由于A的右子树的根的左子树插入节点,使其失去平衡。进行两次旋转,先右旋,后左旋。
采用平衡树的优点是:使树的结构较好,从而提高查找运算的速度。缺点是:是插入和删除运算变得复杂化,从而降低了他们的运算速度。对二叉搜索树删除节点而引起的不平衡性进行的操作比插入节点的情况要复杂