当前位置：网站首页>Search - binary sort tree (2)

Search - binary sort tree (2)

2022-07-18 16:32:00 【InfoQ】

‍ Hello everyone , If you want to know more about binary sort trees, you can see the previous article


  • Delete on binary sort tree

Suppose the deleted node P It is any node of binary sort tree ,F by P The parent node of . For the sake of simplicity , set up P yes F The left child node of . 
The following three situations are discussed :

(1) if *P For leaf nodes , be , Only need to modify P The parent node of F The corresponding child field of is empty . for example , P=83, Just put the node 82 Just leave the right child field blank .

(2） if P The node has only one left child node or one right child node . At this time, just take the left child node or the right child node as its parents F The left or right child node of .( Replace the original P that will do ) for example ,P=75, It has only one left child 74, therefore , Delete 75, Just use 74 Belt replacement 75 The location of , the 74 As 73 The right child , But the 75 Just release it .

(3) if P Nodes have both left child nodes and right child nodes . for example ,P by 80 Node No , here , It can't be replaced by its left child node , Nor can it be replaced by the right child node . It can only be used P The direct precursor of the middle order traversal of or the direct successor of the middle order traversal P. You can use 75 Instead of 80, But the 75 The left child 74 Turn into 73 The right child ; or 82 Instead of 80, But the 82 The right child 83 Turn into 85 The left child .
Or the left subtree directly replaces , Connect the original right subtree of the node to the rightmost end of the original left subtree . Pictured 70 Receive 80 On ,85 Receive 75 On the right subtree .

  • Binary sort tree delete recursive algorithm

Status DeleteBST(BiTree&T,ElemTypekey){
 if(! T) return FALSE;( There is no keyword to find )
 else{
if EQ(key,T->data.key) {
return Delete(T);
}( Find success )
else if LT(key,P->data.key) return DeleteBST(T->Ichild,key);
 else return DeleteBST(T->rchild,key);
}
}// DeleteBST

  • Actual process algorithm

Status Delete(BiTree&p){ 
( Delete a node from the binary sort tree P, And connect its left or right subtree )
if(!P->rchild){( Deleted node P There is no right subtree , Just connect the left subtree ) 
q=p;p=p->lchild; 
free(q);( use P The left child of takes the place of the deleted node P)
}
else if(!P->lchild){( Deleted node P There is no left subtree , Just connect the right subtree )
q=p;
p=p->rchild;
free(q);( use P The right child of takes the place of the deleted node P)
}
else{( node P There are both left and right subtrees , Including the left child and the right child ) 
q=p; s=p->lchild;(q Parent nodes as traversal precursors )
while(s->rchild){
q=s;s=s->rchild
}( Find along the right branch S)
p->data=s->data;( use P Traversal precursor of S Data coverage of P The data of )
if (q!= p)q->rchild=s->lchild;( Left child has right child , Modify the right subtree ) 
else q->lchild=s->lchild;( Left child has no right child , Modify left subtree ) 
delete s;
}( Delete node S) 
return TRUE;
}Delete

原网站

版权声明
本文为[InfoQ]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/199/202207160946472402.html

边栏推荐

猜你喜欢

随机推荐