CODEWITHSUNDEEP
algorithmbinary-search-tree
Shikhar
Shikhar

Reputation: 77

Meaning of Average Compares in BST

I am stuck with following question from the book 'Algorithms' 4th edition by Sedgewick and Wayne.

Add to BST a recursive method avgCompares() that computes the average number of compares required by a random search hit in a given BST (the internal path length of the tree divided by its size, plus one). Develop two implementations: a recursive method (which takes linear time and space proportional to the height), and a method like size() that adds a field to each node in the tree (and takes linear space and constant time per query).

I am not clear on what the author mean by Average Compare in this question.

Note: I don't need assistance on coding part.

Upvotes: 1

Views: 1240

Answers (1)

jszpilewski
jszpilewski

Reputation: 1642

To get the average number of compares for a BST you must sum the number of comparisons to find every node given that the length of search for every node is equal to internal path to that node + 1. Finally to get the average value you must divide the sum by the total number of nodes. So it is just the average length of a node search.

Upvotes: 1

Related Questions