1

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.

Improve this question
3
  • 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 Commented May 24, 2010 at 23:36
  • 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. Commented May 24, 2010 at 23:47
  • 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 Commented May 24, 2010 at 23:59

7 Answers 7

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Are You talking about Balanced Search Tree??
Yes that's taking a binary tree a step further to a BST: red black, avl etc. Binary Trees on their own aren't much use
2

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.

Improve this answer

Comments

1

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.

Improve this answer

Comments

0

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

Improve this answer

Comments

0

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.

Improve this answer

1 Comment

@Jason Hall - Sorry for agreeing that insert, delete, and search are indeed needed every time for any given situation.
0

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!
Improve this answer

2 Comments

Actually reversing the order of everything in the tree can be O(1) time complexity if you just store a flag dictating whether you use < or > in your comparisons :-)
Actually iterating over elements of tree in both directions is symmetric. "(node) ->parent ->right node" "(node) ->parent ->left node"
0

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.