二叉有哪些信誉好的足球投注网站树_AVL树.pptVIP

平衡树（AVL树）举例 平衡树（AVL树）的插入操作 LL不平衡 RR不平衡 LR不平衡 RL不平衡 平衡化旋转 如果在一棵平衡的二叉有哪些信誉好的足球投注网站树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。 平衡化旋转有两类： 单旋转 (左旋和右旋) 双旋转 (左平衡和右平衡) 每插入一个新结点时，AVL树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子(左、右子树的高度差)。 如果在某一结点发现高度不平衡，停止回溯。 从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。 如果这三个结点处于一条直线上(LL或RR)，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状相关。 如果这三个结点处于一条折线上(LR或RL)，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。 * * * * * * * * * * * * * * * +1 a 0 b h h-1 h 0 c h-1 +2 a -1 b h h-1 h +1 c h 圆圈表示节点；椭圆表示子树（内部符号表示其高度） 不平衡情况总结 LL型和RR型是对称的，LR型和RL型是对称的 不平衡的结点一定在根结点与新加入结点之间的路径上 它的平衡因子只能是2或者-2 如果是2，它在插入前的平衡因子是1 如果是-2，它在插入前的平衡因子是-1 右单旋转 左单旋转 左右双旋转 右左双旋转 LL单旋转 T3 h h+1 T2 h -1 b -2 a T1 如果在子树T1中插入一个新结点，该子树高度增1导致结点a的平衡因子变成+2，出现不平衡。 沿插入路径检查三个结点a、b和c。它们处于一条方向为“/”的直线上，需要做右单旋转。 以结点b为旋转轴，让结点a顺时针旋转。 c LL单旋转 T3 h T2 h h+1 -2 a -1 b T1 LL单旋转 a T3 h T2 h b -2 -1 0 0 h+1 T1 T2 h 双旋转 RL或者LR需要进行双旋转 这两种情况是对称的 我们只讨论 RL的情况 LR是一样的 RL型双旋转第一步 T3 h 2 a T0 h -1 b 1 c 或-1 T1 h-1 /h T2 h/ h-1 a RL第一步 插入前 a子树高h+2 插入后 a子树高h+3 需要进行先右后左的双旋转。 先做右单旋转,再做左单旋转 RL型双旋转第一步 1 b 2 a RL第一步 T0 h 1 c T1 h-1 /h T3 h T2 h/ h-1 插入前 a子树高h+2 插入后 a子树高h+3 RL型双旋转第一步 1 b 2 a RL第一步 T0 h 1 c T1 h-1 /h T3 h T2 h/ h-1 RL第二步 中间状态 平衡因子无意义 插入前 a子树高h+2 插入后 a子树高h+3 RL型双旋转第二步 b a T0 h c T1 h-1 /h T3 h T2 h/ h-1 RL第二步 插入前 a子树高h+2 插入后 a子树高h+3 RL型双旋转第二步 b a T0 h c T1 h-1 /h T3 h T2 h/ h-1 T1 h-1 /h 0 a的平衡因子为-1或0 b的平衡因子为0或1 RL第二步 插入前 a子树高h+2 调整后 c子树高h+2 * AVL树结构调整 左单旋转 右单旋转 先左后右旋转 先右后左旋转 */84 */66 左单旋转 */84 * A C h h h B D E A C h h+1 h B D E A C h h+1 h B D E 初始状态 插入后失衡 调整后平衡 右单旋转 */84 * A h h h D E B C A h+1 h h D E B C A B h h+1 D E h C 初始状态 插入后失衡 调整后平衡 先左后右旋转 */84 * A h h h D F B E h-1 G C A h h-1 h D F B E h-1 G C 初始状态 插入失衡，最近的失衡点为A A h h h D F B E h-1 G C 围绕A的左孩子B左旋 A h h h D F B E h-1 G C 围绕A右旋 先右后左旋转 */84 * A h h-1 h E F C D h G B A h h-1 h E F C D h-1 G B 初始状态 A