3、BST的刷除 3、平衡二叉树和平衡的二叉查找树 现在3种情况已绕一到情况2，被副结点p最多只有1个非空的孩子 ”平衡二叉树 child中(p->Ichild)?p->lchild;p->rchild;lfcase1时child空，香测非空 任一结点的左右子树高度大致相同，即只要二叉制高度为0g,则可认为 它是平衡的。 f(Iparent)”p的限亲为空，说明p是根，即根结点 ◆ 充全平衡二又树 *T=child;嗜是情况1，则树为空：否则child)取代p成为根 任一结点的左右子树高度亮全相同（满二叉树） els0(广p非授，它的孩子取代它与'p的双亲连接，即p 平街的二叉查找树 if p==parent->Ichild parent->lchild=child; 满足B$T性质的平衡二又制 else parent->rchild=child; ◆AVL到，任一结点的左右子树的高度之整的绝对值不如过1，h则1.44Ig肌 计(p=q)情况3，将p的数据copy到rq中 ◆红幕制：h2lgn q->key=p>key;I嗜有其他败据赤得copy ■平衡机制 AVL制：4种莫转 free(p方除p 红鼎树：2种城转 )时间Cm 55 25 3、BST的删除 //现在3种情况已统一到情况2，被删结点*p最多只有1个非空的孩子 child=(p->lchild)？p->lchild; p->rchild; //case1时child空，否则非空 If ( !parent ) //*p的双亲为空，说明 *p是根，即删根结点 *T=child; //若是情况1，则树为空；否则*child取代*p成为根 else { //*p非根，它的孩子取代它与*p的双亲连接，即删 *p if ( p==parent->lchild ) parent->lchild=child; else parent->rchild=child; if ( p != q ) //情况3，将*p的数据copy到*q中 q->key=p->key; //若有其他数据亦需copy } free( p ); //删除*p } //时间O(h) 26 3、平衡二叉树和平衡的二叉查找树 „ 平衡二叉树 任一结点的左右子树高度大致相同，即只要二叉树高度为O(lgn)，则可认为 它是平衡的。 „ 完全平衡二叉树 任一结点的左右子树高度完全相同（满二叉树） „ 平衡的二叉查找树 满足BST性质的平衡二叉树 ™ AVL树：任一结点的左右子树的高度之差的绝对值不超过1，h≈1.44lgn ™ 红黑树：h≈2lgn „ 平衡机制 AVL树：4种旋转 红黑树：2种旋转