首页  流程图  详情

AVL树的旋转操作

2015-01-28 01:15:54   10  举报





AVL树简单的旋转示意图

数据结构;平衡树;AVL树

作者其他创作

大纲/内容

单旋转

双旋转

我们把必须重新平衡的点称为a点（图中红点）。由于任意节点最多有两个儿子，因此高度不平衡时，a点的两棵子树高度相差2。出现不平衡时可能有4种情况：1.对a的左儿子的左子树进行一次插入2.对a的左儿子的右子树进行一次插入3.对a的右儿子的左子树进行一次插入4.对a的右儿子的右子树进行一次插入其中，1、4是镜像对称，2、3是镜像对称1、4只需要一次旋转，而2、3需要两次旋转