七章查找.pptVIP

AVL树的类定义 template class Type class AVLTree { public: struct AVLNode { //AVL树结点 Type data; int balance; AVLNodeType * left, * right; AVLNode ( ) : left (NULL), right (NULL), balance (0) { } AVLNode ( Type d, AVLNodeType * l = NULL, AVLNodeType *r = NULL) : data (d), left (l), right (r), balance (0) { } }; …… } 每插入一个新结点时, AVL 树中相关结点的平衡状态会发生改变。因此, 在插入一 个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子 如果在某一结点发现高度不平衡，停止回溯。该不平衡的结点为最深的不平衡点 根据最深的不平衡点与新插入点的位置关系，进行相应的平衡化旋转 单旋转:左单旋转或右单旋转 双旋转:先左后右旋转和先右后左旋转 平衡化旋转 右单旋转 左单旋转 左右双旋转 右左双旋转 四种不同的平衡化旋转 表示最深的不平衡 如果最深的不平衡点与新插入点处于一条直线上，则采用单旋转进行平衡化（左单旋转或右单旋转）。 如果最深的不平衡点与新插入点处于一条折线上，则采用双旋转进行平衡化（双旋转分为先左后右和先右后左两类）。 插入新结点后导致结点A的平衡因子变成2，出现不平衡。为使树恢复平衡，以结点B为旋转轴，让结点A反时针旋转。 插入 A C B h h h-1 h-1 1 0 0 左单 旋转 B A C h h h-1 h 2 1 1 B h h C A 0 0 h-1 h 1 1.左单旋转 (RotateLeft ) //左单旋转的算法 template class Type void AVLTreeType :: RotateLeft ( AVLNodeType * Tree, AVLNodeType * NewTree ) { NewTree = Tree-right; Tree-right = NewTree-left; NewTree-left = Tree; } 插入新结点后结点A的平衡因子增到-2，造成不平衡。为使树恢复平衡，以结点B为旋转轴，将结点A顺时针旋转。 插入 h h h-1 h-1 A B C -1 0 0 h h h h-1 B C A -1 0 0 h B A C h h h-1 h -2 -1 -1 右单 旋转 2.右单旋转 (RotateRight ) //右单旋转的算法 template class Type void AVLTree Type:: RotateRight ( AVLNodeType * Tree, AVLNodeType * NewTree) { NewTree = Tree-left; Tree-left = NewTree-right; NewTree-right = Tree; } 插入 h h A C h-1 h-1 B -1 0 0 左单 旋转 A C B 3.先左后右双旋转(RotationLeftRight) h A h-1 C B 0 0 -1 h h A 右单 旋转 h h C h-1 h B 0 -2 -2 h h h-1 h 1 -2 -1 插入新结点后，结点A的平衡因子变为-2，造成不平衡。 首先，以结点C为旋转轴，将结点B反时针旋转，以C代替原来B的位置。 其次，再以结点C为旋转轴，将结点A顺时针旋转，以C代替原来A的位置。 。 template class Type void AVLTreeType :: LeftBalance ( AVLNodeType * Tree, int taller ) { 左平衡算法实现(包含右单旋转和左右旋转) AVLNodeType *leftsub = Tree-left, *rightsub; switch ( leftsub-balance ) { case -1 : Tree-balance = leftsub-balance =