You are not logged in. Please login at www.codechef.com to post your questions!

×

How can I use binary search tree to implement set operations?

I have read about binary search trees in Wikipedia and it says that it is used to implement sets, multisets and associative arrays. My question is can any binary search tree be used as sets supporting set operations? If so, how?

I have read and coded using regular BST, AVL tree, treap and splay tree. All the articles I can find describe the regular operations that can be performed on them like insert, delete, search. e-maxx.ru described operations like union on treap. I cannot use the same concept on remaining trees. How to implement other set operations like difference, intersection etc on different trees? Are there any general methods for these? I mean for example, finding kth smallest element has same procedure in each of the above mentioned trees (after the tree is built). What about for other methods?

asked 09 Nov '15, 19:37

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×699

question asked: 09 Nov '15, 19:37

question was seen: 1,567 times

last updated: 09 Nov '15, 19:37