0

Can u tell me some of the best search algorithms using tree concepts, bcoz whenever i try to do so; i only get "Binary Search Tree"...pls help me with this!

Edited by pritaeas: Moved.

3
Contributors
2
Replies
25
Views
4 Years
Discussion Span
Last Post by mike_2000_17
1

The search algorithm is pretty trivial, that's why you always get back to the "Binary Search Tree". Once you have a binary search tree constructed, searching for a particular element or range is a simple matter of recursively going down the branch which should contain the sought-after value depending on whether it's less-than (go left) or not (go right).

The real trick is constructing that tree, and especially, maintaining it (i.e., dynamically inserting and removing elements from it). This is where different binary search tree methods differ, like mainly the AVL trees and the Red-Black trees. This is where you would add some bits of information and/or design special algorithms to keep the tree reasonably balanced (all leaf nodes at roughly the same depth) after an insertion or deletion. If the tree cannot be kept balanced, the performance is going to degrade, and also, using a recursive search algorithm would start to be dangerous (stack overflow issues).

And then there are other kinds of binary search trees that are more complex because they don't involve a single-dimensional quantity (e.g., like a set of numbers or words in alphabetical order). But all the same principles apply, it's just that everything is more complicated, including the search algorithm (but still pretty straight-forward, compared to the create / insert / remove algorithms).

And then there are different storage methods (e.g., linked-structures, compact layouts, cache-oblivious layouts, or hybrids). But that is a separate issue (memory locality).

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.