DEQUE
Double-ended queue (or Deque pronounced as “Deck”)
is an data structure where items can be added to or removed from any end. It is
implemented as Linked List with head and tail. Deque is used for maintaining a
LRU cache.
Showing posts with label data structures. Show all posts
Showing posts with label data structures. Show all posts
Tuesday, October 4, 2016
Data structures - Binary Search Trees (BST)
BINARY SEARCH TREES (BSTs)
Useful for searching, inserting, deleting in
O(logn) time.
BST property – ALL nodes (not just immediate) left
of a particular intermediate node (x) will be smaller than x.
ALL nodes (not just immediate) right of a
particular intermediate node (x) will be greater than x.
Sorted Arrays (Binary Search) are good for searching
but bad for insertion (requires shifting of elements). Linked Lists are good
for insertions but searching is bad/slow. BST offers best of both worlds where
searching as well as addition/deletion happens in O(logn) time. It also solves
the next greater (successor) and next smaller (predecessor) problem.
Another use case for BST – Designing a Runway
management system. You need to manage landing times of an incoming aircraft.
There is a pool of times (numbers). You can only add (or allow the aircraft) the
incoming time/number if there is NO existing numbers within ‘k’ limit. These
kind of problems require insertion/deletion/searching. Even a dictionary will
not solve this problem because of the ‘k’ margin. Dictionaries are good of
searching ONLY A PARTICULAR VALUE. (NOT CHECK WHETHER IT LIES IN A RANGE).
Taken from - https://www.youtube.com/watch?v=9Jry5-82I68
Successor
(or next big) – Successor of x can be found be looking right. If the right of x
(lets call it r) does not have any left child i.e. ‘r’ might have a long list
of right children but if it doesn’t have a left child – then r is the successor
of x.
Otherwise – left of left of left of left of left………
till NULL IS THE successor x. (LAST node along left direction).
If there is nothing on right of ‘x’…go parent of
parent of parent of…… UNTIL YOU GET A FORWARD SLASH.(/)
Predecessor
(or next small) – SIMILAR approach as above. Start by looking left. If it has a
right child. Go right of right of right of… till NULL.
If there is nothing on left, go parent of parent
of parent of….UNTIL YOU GET A BACKWARD SLASH (\).
INORDER TREE WALK – x.left,x,x.right
PREORDER TREE WALK – x,x.left,x.right
POSTORDER TREE WALK – x.left,x.right,x
PRINTING LEVEL BY LEVEL – can be done using a
Queue.
Diameter –
max(u,v) {{{ where u and v are leaf nodes }}}
Formula – max( (lheight+rheight+1) ,
(ldiameter + rdiameter) )
DELETION OF
NODE IN A BST– (MOST COMPLEX)
There are 3 cases. The third case has 2 subcases.
Case 1 – The node being deleted is a leaf node.
(easy)
Case 2 – The node being deleted has only 1 child
(i.e either left child or right child). This needs JUST TRANSPLANT (no pointer update).
Case 3 -
The node being deleted has BOTH left and right children. In this case, pictorially, we replace the node with
its successor (defined
above). Pictorially that is it. Algorithmically it is tough.
Case 3 has 2 sub-cases.
a)
The right child itself IS THE SUCCESSOR.
b)
The SUCCESSOR is different from the right child
and is SOMEWHERE IN THE LEFT (left of
left of left…. TILL NULL). This will happen IF THE RIGHT CHILD HAS A LEFT
CHILD.
For case a – We need a TRANSPLANT and updating pointers of
the node being replaced.
For case b – We need to do couple things –
§
TRANSPLANT SUCCESSOR WITH SUCCESSOR.RIGHT
§
get the SUCCESSOR to the TOP
§
Run steps for case a
NOTE
– TRANSPLANTING TAKES CARE OF UPDATING PARENT POINTERS BUT YOU NEED TO TAKE
CARE OF LEFT/RIGHT CHILD POINTERS YOURSELF.
Case 3a and 3b can be pictorially represented by –
Sunday, September 4, 2016
Algorithms - Heaps
Heaps – Heap is a form of binary
tree. Its underlying data structure can be a list with children nodes in 2k+1
and 2k+2 position It could be a max-heap or min-heap.
A max-heap is kind of heap with top node (root
node) having the maximum value.
Heap (minheap) provide optimal time for all three –
insert, findminimum, deleteminimum.
The children index (2i and 2i + 1) can found
very easily as multiplying by 2 is nothing BUT LEFT SHIFT. Parent on the other
hand(i/2) can be found using RIGHT SHIFT.
Priority queues are implemented using heaps.
(min-heap).
MAX-HEAPIFY – This operation when done on a list A
in position i i.e MAX-HEAPIFY(A,i) brings the ith element “downwards” (if it is smaller), so the
subtree rooted at i obeys MAX HEAP PROPERTY.
Implementation of MAX-HEAPIFY in Python –
def max_heapify(A, i):
left = 2
* i + 1
right =
2 * i + 2
largest
= i
if left
< len(A) and A[left] > A[largest]:
largest = left
if right
< len(A) and A[right] > A[largest]:
largest = right
if
largest != i:
A[i], A[largest] = A[largest], A[i]
max_heapify(A, largest)
The complexity of MAX-HEAPIFY is O(logn).
To build
a MAX-HEAP, you run MAX-HEAPIFY on the lower nodes (having children)
UPTO to the top node. There is no point in running MAX-HEAPIFY on bottommost
children nodes.
So for array of size n, you run MAX-HEAPIFY from
floor(n/2) till the top node (i.e n=0). Below is the implementation –
def buildmaxheap(list):
i=int(len(list)/2)
while
(i>=0):
max_heapify(list,i)
i=i-1
The above is the fundamental step of heapsort.
Following steps are done in heapsort –
1)
Build max-heap (A)
2)
From last element to i=1, loop
3)
Exchange current element with A[0] //top most
element.
4)
Reduce heap-size, so that the last element is
disconnected.
5)
Run MAX-HEAPIFY(A,0)
Below is the implementation –
i = len(list)
list2 = []
while (i>0):
list[i-1],list[0] = list[0],list[i-1]
list2.append(list.pop())
max_heapify(list,0)
i = i-1
Subscribe to:
Posts (Atom)