基于重构的AVL树的新算法及实现

摘要

传统的AVL的算法是如果在某一结点发现不平衡,沿刚才回溯的路径取下三层A、B、C分别采取左旋转、右旋转、先左后右双旋转和先右后左双旋转.本文提出了一种基于重构实现AVL树的新方法,把结点A、B、C的中间点做顶点,小者做左子树,大者做右子树.然后将新顶点原来的左子树做左子树的右子树,右子树做右子树的左子树,其它点的子树不变.该方法简单且易于理解.并给出了实现的VC++代码.