Realworld Application of Binary Search Trees

Page 1 of 1

3 Replies - 12074 Views - Last Post: 15 April 2012 - 01:42 PM

#1 Learn4Life

Reputation: 0
• Posts: 10
• Joined: 14-April 12

Realworld Application of Binary Search Trees

Posted 15 April 2012 - 01:30 PM

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

Is This A Good Question/Topic? 0

Replies To: Realworld Application of Binary Search Trees

#2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12148
• Posts: 45,161
• Joined: 27-December 08

Re: Realworld Application of Binary Search Trees

Posted 15 April 2012 - 01:33 PM

*Moved to Computer Science*

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 KYA

• Wubba lubba dub dub!

Reputation: 3196
• Posts: 19,226
• Joined: 14-September 07

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

#4 sepp2k

• D.I.C Lover

Reputation: 2511
• Posts: 3,983
• Joined: 21-June 11

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?