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. emaxx.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
