CODEWITHSUNDEEP
c++c++11data-structurestreebinary-search-tree
FunkyPeanut
FunkyPeanut

Reputation: 1182

A way to copy and store all entries in a balanced binary search tree with O(1)

I am implementing a binary search tree in C++11. I want to add a feature that makes it possible to mark different versions of the data structure with constant time complexity.

What I thought about was to add another property to the root node called "name", "key" or "mark" - thus being accessible with O(1). But to save the tree version I would have to

  1. create a copy of the root (I thought of creating a new instance of the binary search tree and simply assign the tree I want to copy to this new instance)
  2. store the copied root in an array

It is sufficient if those stored roots have read-access only. But now my question is: Can I perform these 2 steps without adding time complexity?

Below there is a little sketch illustrating the process.

enter image description here

Thank you very much for your help.

FunkyPeanut

Upvotes: 0

Views: 326

Answers (1)

Fred Foo
Fred Foo

Reputation: 363607

I think what you're after is a persistent BST. This allows "copying" in O(1) time (just copy a pointer), while performing all the other BST operations with the same big-O times as the vanilla BST. The main difference is that operations that used to take O(1) space now take up to O(lg n) space, at least when the old version of the tree has been stored somewhere.

(You can implement persistent data structures in C++ quite easily with shared_ptr.)

Upvotes: 1

Related Questions