|
|
|
平衡二叉树又称为AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左、右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1；若将二叉树节点的平衡因子定义为该节点的左子树的深度减去其右子树的深度，则平衡树上所有节点的平衡因子只可能是-1、0和1；只要树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
|
|
|
|
平衡二叉树上的插入操作。失去平衡后进行调整的规律可归纳为4种情况：①单向右旋平衡处理；②单向左旋平衡处理；③双向旋转（从左到右）平衡处理；④双向旋转（从右到左）平衡处理。
|
|
|
|
平衡二叉树上的删除操作：若删除节点的两个子树都不为空，就用该节点左子树上的中序遍历的最后一个节点（或其右子树上的第一个节点）替换该节点，将情况转化为待删除的节点只有一个子树后再进行处理。当一个节点被删除后，从被删节点到树根的路径上所有节点的平衡因子都需要更新，对于每一个位于该路径上的平衡因子为±2的节点来说，都要进行平衡处理。
|
|
|
