| TR#: | CS0182 |
| Class: | CS |
| Title: | Modified Binary Search Trees |
| Authors: | Alon Itai and Michael Rodeh |
| CS0182.pdf | |
| Abstract: | A degegerate node in a binary search tree is a node with only one child. It is shown that on the average, an n-node binary search tree has (n+1)/3 degenerate nodes. Suppose the insertion algorithm is modified as follows: Whenever a new node is to be inserted as a grandchild of a degenerate node, the new node, its parent and its grandparent are replaced by the 3-node full binary tree. This heuristic which is very easy to implement has the effect of reducing the average number of degenerate nodes to (n+1)/7 and the average height by a factor of 6/7, to ~1.188 log2(n) which is only 18.8% more than the optimum. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1980/CS/CS0182), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1980
To the main CS technical reports page