平衡旋转有两类代码AVL.cpp

平衡旋转有两类: --单旋转(左旋和右旋) (都已有序) --双旋转(左右旋和右左旋) 每插入一个新节点时,AVL树中相关节点的平衡状态会发生改变。因此,在插入一个新节点后,需要从插入位置沿着通向根的路径回溯,检查各节点的平衡因子。 如果在某一节点发现此树不平衡,停止回溯。 从发生不平衡的节点起,沿着刚才回溯的路径取直接下两层的节点。 (1)如果这三个节点处在一条直线上,则采用单旋转进行平衡化。单旋转可按方向分为左单旋转和右单旋转。 (2)如果这三个节点处在一条折线上,则采用双旋转进行平衡化。单旋转可按方向分为先左后右旋转和先右后左旋转。