Archived

This topic is now archived and is closed to further replies.

Optimal binary search trees?

This topic is 6585 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Well if you haven't taken your exam yet, here is some info. If you need any more detail about anything, just ask what specifically you need.

A binary tree is either an empty set of nodes or a set of nodes with one node designated as the root. Each node has two subtrees, the left subtree and right subtree descending from it.

The binary search tree is an ordered binary tree in which each node contains an item, in which all items in the left subtree precede the root item, and the root item precedes all the items in the right subtree.

For example:
----------------|melon|----------------
----------------/-----\----------------
---------|apple|-------|orange|--------
---------/-----\-------/------\--------
----|NULL|--|lemon|--|NULL|--|pear|----

Lemon is less than melon, but greater than apple. And pear is greater than lemon and greater than orange.

To make the tree you would need functions to:
-Initialize the tree to empty
-Determine whether the tree is empty
-Determine whether the tree is full
-Determine the number of items in the tree
-Add an item to the tree
-Delete an item from the tree
-Search the tree for an item
-Visit each item of in the tree

Well that's about it. Need anything else just ask.

Share this post


Link to post
Share on other sites
Could anyone give a clear explanation of a dynamic programming algorithm for building an optimal binary search tree? I've spent the last two hours poring over the measly two pages that my Algorithm Analysis book gives the topic, and another hour searching the net, and I still haven't been able to pin the thing down =( Of course, I'm required to understand the algorithm for an exam =/

Thanks,
--Feyr

Share this post


Link to post
Share on other sites