CODEWITHSUNDEEP
pythonalgorithmdata-structures
BioShock
BioShock

Reputation: 793

Adding,deleting and inserting elements in O(logn)

We are asked to create an algorithm that runs in worst case in O(logn)

The algo consists of 3 functions:getmin();getmax();add();

The first pop the smallest element from the stack, and it returns it; getmax pop the greatest element from the stack and it returns it; add put elements on the stack.

I was thinking to a RB tree; but i realized that is quite difficult to implement by my own(starting from zero).

There exists others trees or data structure less complicated to implement and that runs in O(logn)?

I can use just basic python operations(i.e. only lists,..)

Upvotes: 3

Views: 1225

Answers (1)

IVlad
IVlad

Reputation: 43467

I would suggest a Treap. In my opinion, it is the easiest Balanced Binary Search Tree to implement because you only need 2 basic rotations.

To search for a given key value, apply a standard binary search algorithm in a binary search tree, ignoring the priorities.

To insert a new key x into the treap, generate a random priority y for x. Binary search for x in the tree, and create a new node at the leaf position where the binary search determines a node for x should exist. Then, as long as x is not the root of the tree and has a larger priority number than its parent z, perform a tree rotation that reverses the parent-child relation between x and z.

To delete a node x from the treap, if x is a leaf of the tree, simply remove it. If x has a single child z, remove x from the tree and make z be the child of the parent of x (or make z the root of the tree if x had no parent). Finally, if x has two children, swap its position in the tree with the position of its immediate successor z in the sorted order, resulting in one of the previous cases. In this final case, the swap may violate the heap-ordering property for z, so additional rotations may need to be performed to restore this property.

Getting the minimum and maximum can be done by moving all the way left from the root for the minimum, and all the way right for the maximum.

Upvotes: 2

Related Questions