Delete Procedure for Binary Search Tree
The procedure below implements a Delete mechanism for a binary search tree, according to the specifications:
procedure Delete(var BST: BinarySearchTree; key: KeyType; var success: boolean);
{ PRE: The tree is not empty }
{ POST: If node with given key value exits, it is deleted }
{ and success is set to true. The current element is }
{ set to the Root of the tree. Otherwise, success is }
{ false. }
{ Bert G. Wachsmuth }
{ April 12, 1996 }
procedure Delete(var BST: BinarySearchTree;
key: KeyType;
var success: boolean);
var
p, parent, right : NodePointer;
procedure FindRightMost(var p, parent : NodePointer);
{ Utility procedure to find the right-most node and it's parent }
{ starting at node p }
begin
parent := p;
while (p^.right <> nil) do
begin
parent := p;
p := p^.right;
end;
end;
begin
p := BST.root;
FindNodes(p, parent, key);
if (p <> nil) then
begin
if (p^.left = nil) and (p^.right = nil) then
{**************************}
{* Deleting a leaf *}
{**************************}
begin
if (p <> BST.root) then
if (parent^.data.key nil) then
{*****************************************}
{* Deleting node with empty left subtree *}
{*****************************************}
begin
if (p <> BST.root) then
if (parent^.data.key nil) and (p^.right = nil) then
{******************************************}
{* Deleting node with empty right subtree *}
{******************************************}
begin
if (p <> BST.root) then
if (parent^.data.key right) then
parent^.right := right^.left
else
p^.left := right^.left;
Dispose(right);
BST.current := BST.root;
Success := true;
end
end
else
Success := false;
end;