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

#1 Learn4Life  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10669
  • View blog
  • Posts: 39,635
  • 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.
Was This Post Helpful? 1
  • +
  • -

#3 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3106
  • View blog
  • Posts: 19,145
  • 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 :(
Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2134
  • View blog
  • Posts: 3,272
  • Joined: 21-June 11

Re: Realworld Application of Binary Search Trees

Posted 15 April 2012 - 01:42 PM

View Postmacosxnerd101, 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?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1