Binary tree to get the minimum element in O (1)

Question

I get multiple access to the minimum element of the binary tree. What implementations allow me to access the minimum element in constant time, and not O(log n) ?

Answer 1

Find it once in O (log n), and then compare the new values ​​that you are going to add using this cached minimum element.

UPD: about how this might work if you remove the minimum element. You just need to spend O (log n) again and find a new one.

Imagine you have 10,000,000,000,000 integers in your tree. Each element requires 4 bytes in memory. In this case, your entire tree requires about 40 TB of hard disk space. The O (log n) time that should be spent searching for the minimum element in this huge tree is about 43 operations. Of course, these are not the easiest operations, but in any case, this is almost nothing even for 20-year-old processors.

Of course, this is true if it is a real world problem. If for some purposes (perhaps academic) you need a real O (1) algorithm, then I'm not sure that my approach can give you such performance without the use of additional memory.

Answer 2

Depending on your other requirements, min-heap may be what you are looking for. This gives you a constant search for the minimum element.

However, you cannot perform some other operations with the same ease as with a simple binary search tree, for example, to determine whether a value is in the tree or not. You can take a look at splay trees , a kind of self-balancing binary tree that provides improved access time to recently accessed items.

Answer 3

This may seem silly, but if you basically get access to the minimal element and don't change the tree too much, then a pointer to the minimal add / delete element (on any tree) may be the best solution.

Answer 4

A tree walk will always be O (log n). Did you write the tree implementation yourself? You can always simply link the link to the current element with the lowest value next to your data structure and update it when adding / removing nodes. (If you are not writing a tree, you can also do this by wrapping the tree implementation in your own wrapper object, which will do the same.)

Answer 5

There is an implementation in TAOCP that uses “fallback” pointers to incomplete nodes to complete a double linked list by nodes in order (I don't remember the details right now, but I want you to have a has_child flag for each direction so that it worked).

With this and a start pointer, you can have a start element in O (1) time.

This solution is no faster or more efficient than minimum caching.

Answer 6

If by the smallest element you mean the element with the smallest value, you can use the TreeSet with a custom Comparator that sorts the elements in the correct order to store the individual elements, and then simply calls SortedSet#first() or #last() to maximize efficiency use the largest / smallest values.

Please note that adding new elements to the TreeSet bit slower compared to other sets / lists, but if you do not have a large number of elements that are constantly changing, this should not be a problem.

Answer 7

If you can use a small memory, it sounds like a combo collection can work for you.

For example, what you are looking for looks like a linked list. You can always get a minimal element, but inserting or searching for an arbitrary node may take longer because you need to do an O (n) search

If you combine a linked list and a tree, you can get the best of both worlds. To find an item for get / insert / delete operations, you must use the tree to search for the item. The holder element node will have to have ways to move from the tree to the linked list for delete operations. Also, the linked list must be a doubly linked list.

So, I think that getting the smallest element will be O (1), any arbitrary search / delete will be O (logN) - I think that even the insert will be O (logN), because you can find where to put it in the tree, look to the previous item and go to your linked node list from there, and then add the "next".

Hmm, this starts to seem like a really useful data structure, maybe a little wasteful in memory, but I don't think any operation would be worse than O (logN) if you don't need to balance the tree.

Answer 8

If you upgrade / "upcomplex" your binary tree to a threaded binary tree , then you can get O (1) first and last elements.

Basically you keep a link to the current first and last nodes.

Immediately after insertion, if the first previous one is not null, update first. Similarly for the latter.

Whenever you delete, you first check to see if the deleted node is the first or the last. And update what is stored first, last accordingly.