Hi,
I need help on making the delete operation on an in-right threaded binary search tree. It’s a question of the book, but one on which I can’t make out on my own. I don’t like asking about what is basically homework, but it beats chimping out for naught. This is the datastructure:
TYPE BinaryTreeNode;
TYPE Tree IS ACCESS BinaryTreeNode;
TYPE BinaryTreeNode IS RECORD
Info : Element;
Thread: Boolean := False;
Left, Right : Tree := NULL;
END RECORD;
And this is the operation:
procedure Delete (T : IN OUT Tree; K : IN KeyType) is
Current: Tree := T;
Previous : Tree;
use ada.text_io;
BEGIN -- Insert
loop
if K < keyof (Current.Info) then
if Current.Left = null then -- Connect to left subtree
exit;
else
Previous := Current;
Current := Current.Left;
end if;
else -- Equal treated as greater
if K = KeyOf(Current.info) then
if Current.Left = null and (Current.Thread or Current.Right = null) then
if Current = Previous.Right and Current.Thread then
Previous.Thread := True;
Previous.Right := Current.Right;
end if;
Free (Current);
elsif Current.Right /= null and not Current.Thread then
if Current = Previous.Left then
Previous.Left := Current.right;
if Current.Right.Thread then
Previous.Left.Thread := True;
Previous.Left.Right := Previous;
end if;
else
Previous.Right := Current.Right;
end if;
elsif Current.Left /= null and Current.Thread then
if Current = Previous.Left then
-- null ?
else
Previous.Right := Current.Left;
end if;
else
null;
-- ??
end if;
end if;
end if;
end loop;
raise NotFound;
end Delete;
I looked for material on the web but the details differ and the language is never Ada… and I can’t read python or god forbids, a derivative of C.
Up to the branch “K = KeyOf(Current.Info)” I know it’s correct, in the sense that the correct node is indeed found. I can’t make heads or tails of the rest, and I haven’t even touched the branch the node to delete has a child on both sides.
The Elements of Programming Style (Second Edition) (Kernighan and Plauger, 1978) list a number of “rules” for good programming style. One of them is “Use recursive procedures for recursively-defined data structures.” Iterative manipulation of recursive data is often far more complicated than the recursive equivalent. It may then be easier to see what needs to be done. Even if you want to create an iterative solution, getting a recursive solution right and then transforming it is usually simpler than creating the iterative solution directly.
What I’d be doing to start with (you may have already told us that this approach wouldn’t work for you? if so, apologies) is looking at the figure in this post and working out how the linkage would have to change on deleting any of the nodes.
Issues you’d need to cover later include,
what happens if the node you need to delete is the top node?
what happens if the node you need to delete is the only node?
are you sure that Previous is always initialized before use?
In the past, I’ve had a dummy Tree node as the root of the whole structure - Previous could perhaps be initialized to this?
I KNOW, I’ve realized how bad the threaded version is. For instance, it’s not possible anymore to display an isolated subtree, because chances are threads will link it to the upper nodes. I can’t imagine someone would a few dozens of so bad and couldn’t use any other structure! But an assignment it is…
However, I do find interesting how the benefits and drawbacks and the algorithms themselves transform to fit tighter or specific requirements. This was probably the point of the exercice, consider the rest of the book has a heavy emphasis on performance. These explanations are really neat and I’m eager to dig into it more when I’ll have to copy to Ada “Algorithms and Data Structures, Writh” with Oberon code.
here my issue is that I can’t figure out what cases I must cover exactly. Once the element has been located (which works) I see four cases:
Current has a left child, which has either/or a left or right child
Current has a right child (notwithstanding threads), idem
Current has neither
Current has both.
But I can’t get what to do with the threads. What does it change if Current itself is a left or right child of Previous ? If curren (the element to delete) has a left child, may I assume that I would need to go down the tree to threads that could link to current ?