#Day24 #100DaysOfCode
Yesterday, I just had my fresher test. I felt sad because I had not revised thoroughly enough. The content was something I already learnt but not remembered at that specific time. I have learnt all about time complexity but what it asks was just some specific complexity of a specific sorting algorithm. Even for BST, I just briefly went through it the day before the test and didn't even think it should appear. Just my luck!
Binary in Binary Search Tree means each node can have at most 2 children. Search in BST means searching for a node within O(logn) time.
There are 3 ways of traversing the BST: inorder(LNR), preorder(NLR), postorder(LRN).
there are two algorithms involved with deleting a node from a BST (having 2 children)
1. find the smallest value on the right subtree
2. find the largest value on the left subtree
mllkl
deletion in BST does not delete the node itself but rather find a substitute and delete its keeper.
finding the smallest value on the right subtree means having to continuously go to the left on that subtree to find the leftmost node of that subtree.
the reason for choosing the leftmost I think is because the problem will be reduced to deleting a node that has a single child or deleting a leaf node that doesn't break the structure of the tree, since the leftmost node can't have a left branch. if forcefully delete a node with two children, the tree structure will be broken.
similarly, finding the largest value on the left subtree means having to continuously go to the right on that subtree until reaching the rightmost node of that subtree.
http://webdocs.cs.ualberta.ca/~holte/T26/del-from-bst.html
Yesterday, I just had my fresher test. I felt sad because I had not revised thoroughly enough. The content was something I already learnt but not remembered at that specific time. I have learnt all about time complexity but what it asks was just some specific complexity of a specific sorting algorithm. Even for BST, I just briefly went through it the day before the test and didn't even think it should appear. Just my luck!
Binary in Binary Search Tree means each node can have at most 2 children. Search in BST means searching for a node within O(logn) time.
There are 3 ways of traversing the BST: inorder(LNR), preorder(NLR), postorder(LRN).
there are two algorithms involved with deleting a node from a BST (having 2 children)
1. find the smallest value on the right subtree
2. find the largest value on the left subtree
mllkl
deletion in BST does not delete the node itself but rather find a substitute and delete its keeper.
finding the smallest value on the right subtree means having to continuously go to the left on that subtree to find the leftmost node of that subtree.
the reason for choosing the leftmost I think is because the problem will be reduced to deleting a node that has a single child or deleting a leaf node that doesn't break the structure of the tree, since the leftmost node can't have a left branch. if forcefully delete a node with two children, the tree structure will be broken.
similarly, finding the largest value on the left subtree means having to continuously go to the right on that subtree until reaching the rightmost node of that subtree.
http://webdocs.cs.ualberta.ca/~holte/T26/del-from-bst.html
