Hi guys,

I came along a task where I have to discuss a realworld application where to use Binary Search Trees. The Binary Search Tree is a self balancing tree where the smallest value is the root, or biggest. I was thinking where such a data structure might be useful, so far I haven't come up with something useful. Maybe somebody of you guys used BST in a realworld problem and would like to share the experience you have made solving this problem. Thanks

-Daniel

# Realworld Application of Binary Search Trees

Page 1 of 1## 3 Replies - 9336 Views - Last Post: 15 April 2012 - 01:42 PM

##
**Replies To:** Realworld Application of Binary Search Trees

### #2

## Re: Realworld Application of Binary Search Trees

Posted 15 April 2012 - 01:33 PM

*Moved to Computer Science*

Not exactly. A binary search tree is a tree such that values left of the root are smaller than it, and values right of the root are larger than it. Balanced binary search trees are a subset of binary search trees. Your definition sounds more like a Heap.

Both Red-Black and AVL Trees are commonly used to back hash table structures.

Quote

The Binary Search Tree is a self balancing tree where the smallest value is the root, or biggest.

Not exactly. A binary search tree is a tree such that values left of the root are smaller than it, and values right of the root are larger than it. Balanced binary search trees are a subset of binary search trees. Your definition sounds more like a Heap.

Both Red-Black and AVL Trees are commonly used to back hash table structures.

### #3

## Re: Realworld Application of Binary Search Trees

Posted 15 April 2012 - 01:34 PM

std::map is implemented as a RedBlack tree and I use it constantly.

Vanilla BSTs are not used as much since you incur penalties when the tree is not self balancing, hence the extensive usage in pseudo hash table containers.

edit: ninja'ed

Vanilla BSTs are not used as much since you incur penalties when the tree is not self balancing, hence the extensive usage in pseudo hash table containers.

edit: ninja'ed

### #4

## Re: Realworld Application of Binary Search Trees

Posted 15 April 2012 - 01:42 PM

macosxnerd101, on 15 April 2012 - 10:33 PM, said:

Both Red-Black and AVL Trees are commonly used to back hash table structures.

You mean to handle collisions? I wasn't aware of that. Can you give an example of a hash table implementation that uses trees?

Hm, now that I think about, I find this quite strange. Hashmaps generally don't require their elements to be comparable, so

*how*can they use a search tree in their implementation?

Page 1 of 1