2、BST的插入和生成 2、BST的插入和生成 ■举例 量一般情况 轴入实例10,18,3,8,12,2,7,3到 不同的输入实例（数据集不同、或排列不同），生成的 树的形态一般不同。对n个结点的同一数据集，可生成n!棵 BST. ⑧ ■例外情况 但有时不同的实例可能生成相同的BST,例如：（2,3， 7,8,5,4)和(2,3,7,5,8,4)可构造同一棵BST。 ⑧ ⑧② ⑧ ■排序树名称的由来 因为B$T的中序序列有序，所以对任意关键字序列，构造 BST的过程，实际上是对其排序。 生成n个结点的BST的平均时间是O(nlgn,但它约为堆排 序的2一3倍，因此它并不适合排序。 3、 BST的删除 3、BST的副除 保证测一结点不能将以该结点为根的子制侧去，且仍须满足ST性质，即： ■基本思想 一结点相当于有序序列中的一个结点。 c3:*p有2个孩子，有2种处理方式： 基本思短 ①找到*p的中序后健或前驱，用*p的右或左)子树取代*p与其双亲 音垫碧资学之me清肉关限秦（彻值U),著找不到侧通 连接： 左或右)子则作为的左或右)子树与连 在测障*p时处理其子树的连接问■，同时保持BST性质不变。 parent case产p是叶子，无须连接子树，只需将*parent中指向产p的指针置空 parent cse2:*p只有1个孩子，只须连获障一的1裸子制，放可令此孩子取代*p与 其双亲连接（种状态） /PL\/SR 只有左孩子 p风南右被子 3、BST的副除 3、BST的酬除 ■基本思想 ②中q听p:找*q的中序后望p,并变parent指向*p的双来，将p的右子制取代 ■算法 与其双亲*parenti挂接，将产p的内客copy到*q中，相当于副去了*q:将*q的 作转换为的媒作，对称地，也可找*的中序前驱 void DelBSTNode(BSTree "T,KeyType key))(rT是根 BSTree'q,*child,"parent=NULL,*p=*T; while(p)(找特结点 if(p->key=key)break;∥已找到 parent=p;川循环不变式是parent为rp的双亲 p=(key p->key )p->Ichild;p->rchild; if(p)return;1找不到被结点，返回 “q的中序后撞城是其右孩于 qp;g记住被结点p if(q->lchild&&q->rchild)//case3,找*q的中序后罐 for(parent=qpq->rchild:p->lchild;parent-p,pp->lchild); 44 19 2、BST的插入和生成 „举例 10 10 18 10 3 18 10 3 18 8 10 3 18 8 12 10 3 18 2 8 12 10 3 18 2 8 12 7 10 3 18 2 8 12 7 3 输入实例 {10， 18， 3， 8， 12， 2， 7， 3} 20 2、BST的插入和生成 „ 一般情况 不同的输入实例（数据集不同、或排列不同），生成的 树的形态一般不同。对n个结点的同一数据集，可生成n！棵 BST。 „ 例外情况 但有时不同的实例可能生成相同的BST，例如：（2，3， 7，8，5，4）和（2，3，7，5，8，4）可构造同一棵BST。 „ 排序树名称的由来 因为BST的中序序列有序，所以对任意关键字序列，构造 BST的过程，实际上是对其排序。 生成n个结点的BST的平均时间是O(nlgn), 但它约为堆排 序的2－3倍，因此它并不适合排序。 21 3、BST的删除 保证删一结点不能将以该结点为根的子树删去，且仍须满足BST性质。即： 删一结点相当于删有序序列中的一个结点。 „ 基本思想 ™ 查找待删结点*p，令parent指向其双亲（初值NULL）；若找不到则返 回，否则进入下一步。 ™ 在删除*p时处理其子树的连接问题，同时保持BST性质不变。 case1:*p是叶子，无须连接子树，只需将*parent中指向*p的指针置空 case2:*p只有1个孩子，只须连接唯一的1棵子树，故可令此孩子取代*p与 其双亲连接（4种状态） parent p child child parent p parent p child parent p child *p只有左孩子 *p只有右孩子 22 3、BST的删除 „ 基本思想 case3: *p有2个孩子，有2种处理方式： ①找到*p 的中序后继(或前驱)*s，用*p的右(或左)子树取代*p与其双亲 *parent连接；而*p的左(或右)子树PL则作为*s的左(或右)子树与*s连 接。缺点：树高可能增大。 PL sR s pr parent PL sR p parent s pr 23 3、BST的删除 „ 基本思想 ②令q=p，找*q的中序后继*p，并令parent指向*p的双亲，将*p的右子树取代*p 与其双亲*parent连接。将*p的内容copy到*q中，相当于删去了*q，将删*q的 操作转换为删*p的操作。对称地，也可找*q的中序前驱 因为*p最多只有1棵非空的子树，属于case2。实际上case1也是case2的特 例。因此，case3采用该方式时，3种情况可以统一处理为case2。 q=p parent p child q=p p child *q的中序后继就是其右孩子 24 3、BST的删除 „ 算法 void DelBSTNode( BSTree *T, KeyType key) { //*T是根 BSTree *q, *child, *parent=NULL, *p=*T; while ( p ) { //找待删结点 if ( p->key ==key ) break; //已找到 parent=p; //循环不变式是*parent为*p的双亲 p＝( key < p->key ) ? p->lchild; p->rchild; } if ( !p ) return; //找不到被删结点，返回 q=p; //q记住被删结点*p if (q->lchild && q->rchild ) //case3，找*q的中序后继 for(parent=q,p=q->rchild; p->lchild; parent=p, p=p->lchild);