#### Archived

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

# Optimal binary search trees?

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

## 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

##### Share on other sites
Feyr,
Are you referring to a balanced tree? If you can hold out until Thursday night, I have a couple books at home that I can look through for you.

Six

##### 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

1. 1
Rutin
28
2. 2
3. 3
4. 4
5. 5

• 13
• 11
• 10
• 13
• 20
• ### Forum Statistics

• Total Topics
632949
• Total Posts
3009412
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!