Question on Binary Search Trees.

Question

Hi,

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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!

Answer 5

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.

Answer 6

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.

Answer 7

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.