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 –
No comments:
Post a Comment