summaryrefslogtreecommitdiff
path: root/05-13.md
diff options
context:
space:
mode:
Diffstat (limited to '05-13.md')
-rw-r--r--05-13.md214
1 files changed, 214 insertions, 0 deletions
diff --git a/05-13.md b/05-13.md
new file mode 100644
index 0000000..13e8970
--- /dev/null
+++ b/05-13.md
@@ -0,0 +1,214 @@
+[\<- 05/11](05-11.md)
+
+---
+
+## BST - Insertion
+
+- To insert data, we need to follow the branches to an empty subtree and then insert the new node
+- All inserts take place at a leaf or at a leaflike node - a node that has only one subtree
+- Example: insert 15, 13
+
+![example tree](05-13_img1.png)
+
+- For 15
+ - 15 is less than 17
+ - 15 is greater than 6
+ - 15 is greater than 14 -> insert in the right child of the 14 node
+
+- For 13
+ - 13 is less than 17
+ - 13 is greater than 6
+ - 13 is less than 14 -> insert in the left child of the 14 node
+
+## Exercise
+
+- Give me an arbitrary number and let's insert it into the tree
+ - 50
+ - 30
+ - 60
+ - 20
+ - 100
+ - 10
+
+- for 50
+ - We start with an empty tree, so 50 becomes the root
+
+- for 30
+ - 30 is less than 50 -> insert in the left child of the root
+
+- for 60
+ - 60 is greater than 50 -> insert in the right child of the root
+
+- for 20
+ - 20 is less than 50
+ - 20 is less than 30 -> insert in the left child of the 30 node
+
+- for 100
+ - 100 is greater than 50
+ - 100 is greater than 60 -> insert in the right child of the 60 node
+
+- for 10
+ - 10 is less than 50
+ - 10 is less than 30
+ - 10 is less than 20 -> insert in the left child of the 20 node
+
+- What's the runtime for something like this? **O(h)** (h being the height of the tree)
+
+## Insertion Code
+
+```
+bool insertNode(NODE *root, NODE *np){
+ assert(np != NULL);
+
+ //Base case
+ if(root == NULL) root = np;
+
+ //If the node to be inserted is smaller than the root's data, it lies in left subtree
+ if(np->data < root->data) return insertNode(root->left, np);
+
+ //If the node to be inserted is greater than the root's data, it lies in the right subtree
+ else if(np->data > root->data) return insertNode(root->right, np);
+
+ //if x is the same as root's data
+ else return false;
+}
+```
+
+- This code doesn't work (why?)
+ - It creates a disconnected tree
+ - The solution? Double pointers!
+
+- What is the correct code?
+
+```
+bool insertNode(NODE **root, NODE *np){
+ assert(np != NULL);
+
+ //Base case
+ if(*root == NULL) *root = np;
+
+ //If the node to be inserted is smaller than the root's data, it lies in left subtree
+ if(np->data < (*root)->data) return insertNode(&(root)->left, np);
+
+ //If the node to be inserted is greater than the root's data, it lies in the right subtree
+ else if(np->data > (*root)->data) return insertNode(&(*root)->right, np);
+
+ //if x is the same as root's data
+ else return false;
+}
+```
+
+- Notice that in the above version, root is a double pointer
+
+There is another way!
+
+```
+NODE *insertNode(NODE *root, NODE *np){
+ assert(np != NULL);
+
+ //Base case
+ if(root == NULL) return np;
+
+ //If the node to be inserted is smaller than the root's data, it lies in left subtree
+ if(np->data < root->data) root->left = insertNode(root->left, np);
+
+ //If the node to be inserted is greater than the root's data, it lies in the right subtree
+ else if(np->data > root->data) root->right = insertNode(root->right, np);
+
+ //if x is the same as root's data
+ else return false;
+}
+```
+
+- Notice that the above code returns a NODE * (and not a boolean)
+- Keep in mind that the above code is relatively complex
+
+## BST - Deletion
+
+- Deleting nodes with no children is easy, you just search for and free them (doesn't affect the rest of the tree)
+
+- Deleting nodes with one child is a little challenging, because we want to maintain the node's child, but also to remove that node
+ - take the "abandoned" child and have the "grandparent" node take care of it
+
+- Deleting a node with two children is more challenging
+ - The "grandparent" node only has one available pointer, but now there are two "abandoned" children
+ - The "abandoned" children must form their own BST, the root of this new tree will be pointed to by the "grandparent"
+
+### Turning two subtrees into a tree
+
+- Either take the minimum value from the right or the maxiumum value from the left
+ - They will become the root, basically replacing the removed parent
+
+### Summary
+
+- Assume the node to be deleted is `Ndel`, there are four cases
+ - `Ndel` has **no children** -> delete it
+ - `Ndel` has **only a right subtree** -> delete `Ndel` and attach its right subtree to `Ndel`'s parent
+ - `Ndel` has **only a left subtree** -> delete `Ndel` and attach the left subtree to `Ndel`'s parent
+ - `Ndel` has **two subtrees** -> replace `Ndel`'s data by either the largest node in its left subtree or the smalles node in its right subtree
+
+## BST - Deletion Big-O
+
+- What's the worst-case big O?
+ - The only looping in the process is the searching -> O(h)
+
+## Let's Work on the Code
+
+- One Challenge
+ - Deletion may change the structure of the subtree, leading to a different root of the subtree. How could we connect the parent with the new root of the subtree?
+ - Solution: We pass the new root of the subtree (after deletion) back to the parent
+
+### Deletion Code
+
+```
+NODE *deleteNODE(NODE *root, int x, bool *found){
+ //base case
+ if(root == NULL){
+ *found = false;
+ return root;
+ }
+
+ //If the node to be deleted is smaller than the root's data, it lies in left subtree
+ if(x < root->data) root->left = deleteNode(root->left, x, found);
+
+ //If the node to be deleted is greater than the root's data, it lies in right subtree
+ else if(x > root->data) root->right = deleteNode(root->right, x, found);
+
+ //if x is same as root's data, this is the node to be deleted
+ else{
+ *found = true;
+
+ //node with only one child or no child
+ if(root->left == NULL){
+ NODE *temp = root->right;
+ free(root);
+ return temp;
+ }
+ else if(root->right == NULL){
+ NODE *temp = root->left;
+ free(root);
+ return temp;
+ }
+
+ //node with two children: Get the smallest in the right subtree
+ NODE *temp = minimum(root->right);
+
+ //Copy the inorder successor's content to this node
+ root->data = temp->data;
+
+ //Delete the inorder successor
+ root->right = deleteNode(root->right, temp->data, found);
+ }
+
+ return root;
+}
+```
+
+---
+
+|SET |Unsorted Array|Sorted Array|Hash Table|Unsorted Linked List|Sorted Linked List |BST |
+|---------------|--------------|------------|----------|--------------------|-----------------------------------|-----------------------|
+|**Search/Find**|O(n) |O(log(n)) |O(n) |O(n) |O(n) |O(h) (log(n) <= h <= n)|
+|**Add** |O(n) |O(n) |O(n) |O(n) |O(n) |O(h) (log(n) <= h <= n)|
+|**Remove** |O(n) |O(n) |O(n) |O(n) |O(n) |O(h) (log(n) <= h <= n)|
+|**Min/Max** |O(n) |O(1) |O(m) |O(n) |O(1) (assuming fast access to tail)|O(h) (log(n) <= h <= n)|