10.5.3 Aside: Comparison of Deletion Algorithms

This book has presented algorithms for deletion from BSTs, TBSTs, and RTBSTs. In fact, we implemented two algorithms for RTBSTs. Each of these four algorithms has slightly different performance characteristics. The following table summarizes the behavior of all of the cases in these algorithms. Each cell describes the actions that take place: “link” is the number of link fields set, “tag” the number of tag fields set, and “succ/pred” the number of general successor or predecessors found during the case.

		BST*	TBST	Right-Looking TBST	Left-Looking TBST
	Case 1	1 link	2 links 1 succ/pred	2 links 1 succ/pred	1 link
	Case 2	1 link	1 link 1 tag	1 link 1 tag	1 link 1 tag
	Case 3	2 links	3 links 1 tag 1 succ/pred	3 links   1 succ/pred	2 links 1 tag
	Case 4 subcase 1	4 links   1 succ/pred	5 links 2 tags 2 succ/pred	5 links 1 tag 2 succ/pred	4 links 1 tag 1 succ/pred
	Case 4 subcase 2	4 links   1 succ/pred	5 links 2 tags 2 succ/pred	5 links 1 tag 2 succ/pred	4 links 1 tag 1 succ/pred

* Listed cases 1 and 2 both correspond to BST deletion case 1, and listed cases 3 and 4 to BST deletion cases 2 and 3, respectively. BST deletion does not have any subcases in its case 3 (listed case 4), so it also saves a test to distinguish subcases.

As you can see, the penalty for left-looking deletion from a RTBST, compared to a plain BST, is at most one tag assignment in any given case, except for the need to distinguish subcases of case 4. In this sense at least, left-looking deletion from an RTBST is considerably faster than deletion from a TBST or right-looking deletion from a RTBST. This means that it can indeed be worthwhile to implement right-threaded trees instead of BSTs or TBSTs.