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 13 Replies  6880 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 RedBlack 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 RedBlack 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 RedBlack 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
