Question on Binary Search Trees

1
votes

I was thinking of implementing a binary search trees. I have implemented some very basic operations such as search, insert, delete.

Please share your experiences as to what all other operations i could perform on binary search trees, and some real time operations(basic) that is needed every time for any given situation.. I hope my question was clear..

Thanks.

7
data-structuresbinary-tree
what are you trying to do exactly? you can apply them to many situations, but if you don't have a particular situation in mind it's hard to tell you what you need – Claudiu
I am curious to learn trees, so seeking some good websites which list all possible operations that can be performed on Trees, and its applications and various types of trees.. I have gone through wiki articles, but those are basic. I need to go to an advance level.. PS: This is not an HW. – AGeek
The Wikipedia article is actually one of the best sources: en.wikipedia.org/wiki/Binary_tree it's unusually clear and well written for a Wikipedia Computer Science topic – Chris S

7 Answers

2
votes

Try a traversal operation (e.g., return the elements in the tree as a List, in order) and make sure that the tree remains balanced when elements are inserted/deleted.

2
votes

You may want to look at the different ways of returning the tree:

  • Depth-first (going all the way down a branch and back up, repeat)
  • In-order (going around the tree)
  • Level-order (each level as drawn in a diagram)
  • Returning as a flat array.

And if you're feeling particularly adventurous, take an array and import it in as a tree. There is a specific format for this that goes something like (1(2(3)),(5) - that example isn't balanced but you get the idea, and it's on Wikipedia.

1
votes

You might also want to implement a rotation operation. A rotation changes the structure without change the order of the elements. This is usually used to balance the tree (to make sure the leaves are all close to the same depth) and can also be used to change the root to a given element if you know it will be showing up in the search more often.

My ASCII art is not great, but a rotation can turn this tree:

        f
    d       g
  b   e           
 a c

into this tree:

        d
    b       f
  a   c   e   g

The second tree being balanced will make searches for f and g slower, and searches for d,a,b,c faster with e staying the same.

0
votes

If this is homework, Good luck!

If this is curiousity, have fun!

If you want to implement this in production code without even knowing the basic operations, Don't do it!

http://www.boost.org/doc/libs/1_38_0/boost/graph/detail/array_binary_tree.hpp

0
votes

At the very least, a binary search tree should have an insert, delete, and search operation. Any other operations will depend on what you intend to do with your tree, although some generic suggestions are: return parent of a given node, find left and right child of a given node, return the root node, preorder, inorder, and postorder traversals, as well as a breadth-first traversal.

0
votes

If you really just want a list of stuff that might be useful or fun to implement...

  1. Reverse the order of everything in the tree. This is O(N) I think?
  2. Subtree, elements between x and y as a binary search tree themselves -- should be O(log N) I think?
  3. Minimum, maximum? Yeah, trivial but I'm out of ideas!
0
votes

I think I've seen somewhere "map" operation. When you change all elements of tree with monotonic function. I.e. function with property to always ascend ( f(x+dx) >= f(x) ) or always descend ( f(x+dx) <= f(x) ). In one case you'll need to apply that function to each node in other you'll need also to mirror tree (swap "left" and "right" nodes) because order of resulted values will be reversed.