Pseudo code Binary Search Tree

Question

Suppose T is the root node of a Binary Search Tree. Tree nodes will be implemented with the usual BST attributes, and an additional attribute called x.deleted is included, which can be set to True or False. Using this new attribute, describe how to delete nodes from the BST T. Provide the pseudo-code for this new algorithm, which is called LazyDelete(T,z). Next, explain how to update the TreeSearch(T,z) algorithm and the TreeInsert(T,z) so that it works with this new lazy binary search tree. You may assume that no duplicates are in the data set at any one time. However, it is possible that we insert a key 5, then delete a 5, and then re-insert a 5. Your algorithms should work in this scenario. What are the downfalls of this new lazy approach? 

Reference pseudocode for TreeSearch and TreeInsert found here.. https://en.wikipedia.org/wiki/Binary_search_tree

Answer 1

[In this revision of my earlier answer, I have tried to address the issues raised by Donald W. I have tried to be consistent in using T as the name of a binary search tree (so T.root refers to the root node of T, NIL if T is empty), x, y, and z as tree nodes, and k as a search key. There is a total ordering on the keys, and no two nodes have the same key.]

Normally, a node is removed from a binary search tree by replacing it with its successor or predecessor and the subtree it heads. If a node is a leaf, it can just be clipped.

Lazy deletion, on the other hand, uses these x.deleted flags to speed up deletion by letting us skip the step of finding x's predecessor or successor node. This solves a performance problem in the short term, but creates long-term issues. See after the code.

To understand the implementation of lazy deletion, I chose to create a child class of BST called LazyBst that inherits most of its implementation from BST. BST's methods don't pay any attention to the deleted flags.

class LazyBst extends BST

// Below are LazyBst's overrides of BST's method. Most use their BST counterparts.

// Lazy-Tree-Search is the same as BST's except it checks deleted flag when it's found.

Lazy-Tree-Search(T k) // Replaces Tree-Search

// Find a node in T the node z with z.k = k, NIL if none.

z := Tree-Search(T, k)

if z = NIL or z.deleted // Deleted nodes are used in search, but never returned,

return NIL

else

return z

// Lazy deletion of a key is a breeze. Just find the element and set the deleted flag.

// Remember that BST's methods ignore the delete flags.

Lazy-Delete(T z) // This is a Lazy replacement for Tree-Delete(T z).

if z = NIL

return

else

z.deleted = true

// tree-insert() allows duplicate keys, so our Lazy-Insert() does too.

// For this function and also tree-insert(),

// z is a node, but it needs to not be part of any tree:

// this function will assign parent node and child nodes (possibly NIL) to node z,

// and that would corrupt any tree that z was part of.

Lazy-Insert(T, z)

Tree-Insert(T,z) // Insert as normal,

z.deleted = false // ... and then set flag.

// If BST successor is deleted, look for Lazy successor of _that_ node (in the tree it heads)

Lazy-Successor(z)

z := Tree-Successor(z)

if z = NIL

return NIL

else if z.deleted

return Lazy-Successor(z) // Recursive call.

else

return z

// If BST predecessor is deleted, look for Lazy predecessor of _that_ node (in the tree it heads)

Lazy-Predecessor(n)

z := Tree-Predecessor(n)

if z = NIL

return NIL

else if z.deleted

return Lazy-Predecessor(z)

else

return z

Downfall of lazy deletion:

Search is slowed down by having to check deleted notes as it searches, and as traffic comes in and out, the tree grows full of deleted nodes. Lazy delete might be ok if the application can regularly be allowed to shut dump contents, shuffle, and rebuild, which removes all deleted nodes. Normal delete can use occasional dump/shuffle/rebuild if deletions happen often, but at least it shrinks the tree.

Answer 2

I feel like this problem is poorly worded. For example, in the linked wikipedia article, the parameter z is used to refer to a node in the tree and the parameter key is used to refer to the key of a node that may or may not be in the tree. So referring to TreeSearch(T, z) doesn't make much sense, because you don't typically search a BST for a node. If you already have the node, there's no need to perform a search. I assume that they mean TreeSearch(T, key), because you would search a tree for a node that contains a particular key. Now that we know that z is used ambiguously in this question, it's not clear what the question is actually asking for with LazyDelete(T, z) and TreeInsert(T, z). Is z the node to be deleted and inserted (in other words, we've already done a search and found the node to operate on) or do they also mean to use key here instead of z? This is an important detail, because the implementation is very different. I'll provide an answer for the two different interpretations of LazyDelete() here, though:

// We already have the node that we want to delete

LazyDelete(T, z)

z.deleted := true

// We need to search for the node to delete and then delete it

LazyDelete(T, key)

x := T.root

while x ≠ NIL do

if x.key = key

x.deleted := true

x := NIL

else if x.key < key

x := x.right

else

x := x.left

endif

repeat

Can you write the new search and insert methods yourself based on this?