数据结构 非平衡二叉树的平衡处理 若一棵二叉排序树是平衡二叉树,插入某个结点后, 可能会变成非平衡二叉树,这时,就可以对该二叉树 进行平衡处理,使其变成一棵平衡二叉树。处理的原 则应该是处理与插入点最近的、而平衡因子又比1大 或比-1小的结点。下面将分四种情况讨论平衡处理。 (1)L型的处理(左左型) 在A的左孩子B上插入一个左孩子结点C,使A的平衡因 子由1变成了2,成为不平衡的二叉排序树。这时的平衡 处理为:将A顺时针旋转,成为B的右子树,而原来B的 右子树则变成A的左子树,待插入结点C作为B的左子树。 B)平衡处理 B数据结构 tjm 非平衡二叉树的平衡处理 若一棵二叉排序树是平衡二叉树，插入某个结点后， 可能会变成非平衡二叉树，这时，就可以对该二叉树 进行平衡处理，使其变成一棵平衡二叉树。处理的原 则应该是处理与插入点最近的、而平衡因子又比1大 或比-1小的结点。下面将分四种情况讨论平衡处理。 （1）LL型的处理(左左型) 在A的左孩子B上插入一个左孩子结点C，使A的平衡因 子由1变成了2，成为不平衡的二叉排序树。这时的平衡 处理为：将A顺时针旋转，成为B的右子树，而原来B的 右子树则变成A的左子树，待插入结点C作为B的左子树。 A B C A B C 平衡处理