www.delorie.com/gnu/docs/avl/libavl_191.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

11.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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003