ai yay 📈📈📈📈

insert review

check if root is null; otherwise insert
check for dupe; print error otherwise
check if we go right or left and recursively call the method again

deleting yay

cases

If the node has no children (it’s a leaf)
1. find the node to delete; keep track of its parent node
2. check if it has children
3. free the deleted node; update the pointer of the parent node.
If it has 1 child
1. Same as case 1, except the parent links to the child of the deleted node and not null
If it has 2 children 2. Find le successor 1. The smallest number greater than the node we’re deleting 2. This is the left-most item in the right subtree of the guy we’re deleting. 3. Promote le successor to become the node we delete (by overwriting — copy and pasting — its data) 4. delete the successor from the left by calling delete on it again (it will either be type 1 or type 2) 5. Note that the successor will only be a case 1 or case 2 (if it had two children it wouldn’t be the successor!)

// The successor is the node JUST larger than the one we pass
Node* find_successor(Node *r)
{
	// We can assume 'r' has a left and right node != NULL
	Node* successor = r->right;
	while (successor->left != NULL)
	{
		successor = successor->left;
	}
	return successor;
}

// Observe: Delete returns the *child" that may or may not have been deleted
// Whatever 'r' we pass in is the child we are attemping to delete
 
Node* delete(Node *r, int key)
{
	if (r == NULL) return r; // Nothing to do here
	
	// Check if this is the guy we want to delete
	if (r->key == key)
	{
		// Case 1: No children
		if (r->left == NULL && r->right == NULL)
		{
			free(r);
			return NULL;
		}
		// Case 2.a) right is null => left isn't null
		else if (r->right == NULL)
		{
			// Return the child cuz that is still saying around
			Node* temp = r->left;
			free(r);
			return temp; 
		}
		else if (r->left == NULL)
		{
			// Return the child cuz that is still saying around
			Node* temp = r->right;
			free(r);
			return temp; 
		}
		// Case 3. Need to find sucessor
		else
		{
			// Find the successor (this is the node that replaces the one we delete)
			Node *successor = find_successor(r);
			// Promote
			r->key = successor->key;
			// Go into the right subtree and delete the successor duplicate
			// Remember, we CANNOT call delete on 'r' since that now has the same key
			// as the successor (the node we want to delete is the successor) 
			r->right = delete(r->right, successor->key);
		}
	}
	else
	{
		// Otherwise we have to keep searching for it
		if (key > r->key) r->left = delete(r->left, key);
		else r->right = delete(r->right, key);
	}
	return r;
}

Extra: Balancing a BST

(exercise 4.9) The old BST is already sorted, which is great.

To get the height, traverse and count the # of items. the log2 of that number SHOULD be the desired height.

todo MIGHT be useful to try and do. Could be a “crunchy” question

Checking for balance (this was a mid-term question)

We know the distance between all the leaves cannot be more than 1. I.e. all leaves could be a distance of 3 OR 4 from the root (not 2 or 5, otherwise we could balance it!)
To do this, we keep track of the minimum height and maximum height.

// When we call this we let min = 0 and max = 0 of course!
int min = 0, max = 0;
void traverse_height(Node *r, int at)
{
	traverse_height(r->right, at + 1);
	traverse_height(r->left, at + 1);
	
	if (r == NULL) 
	{
		at--; // it overshoots by 1
		if (at < min) min = at;
		if (at > max) max = at
	} 
}
 
int is_balanced(Node* r, int at)
{
	min = 0; max = 0;
	traverse_height(r, 0);
	
	if (max - min > 1) return 0; // NOT balanced
}

todo I need to remember for case 2 NOT to check if it’s not null, but instead to check the other side IS null

Complexity things again

if the bin tree is just items to the right or left, then it’s length n (basically a linked list). But elements are usually in random order. The chance you get that kinda list is very small.

Complete BST’s are the best case with no gaps

Insert is $O (L o g_{2} N)$ in best case and on average.

With BST’s we will definitely need to worry about HACKERS. If they start adding things in order because they are a mischievous bunch it will cause problems. We need to guarantee we have $l o g_{2} N$ some other way.

Tree Traversals

in order
preorder
postorder
todo read in notes

The complexity for quick sort is $N L o g_{2} N + N = N L o g_{2} N$

Tutorial

We made some trees
Inserting in random order = efficient BST
- If it’s not ordered = not efficient BST (linked list-esque)

deleting nodes

Traversals

They all have the same 3 steps, but they are in different orders:

Do “thing” but on the left
Do “thing” but on the right
Do “thing” but where you’re at

All traversals will be $O (N)$ where the unit of work is doing “something” at each node. Seems kinda trivial but eh.

In-order traversal (you print the numbers in order (increasing order))

Perform in-order traversal of the left sub-tree and recur this algo there
Do whatever at node “i” (usually just printing)
Do in-order traversal of the right sub-tree and recur this algo there

Pre-order traversal (same 3 lines as abv but in a different order)

Do stuff at node i
Perform pre-order traversal of the left sub-tree
Perform pre-order traversal of the right sub-tree This would be how you print the BST in a printBST function or if you want to duplicate it somehow.

Post-order traversal (same 3 lines but in a different-er order)

Do left subtree
Do right subtree
Work at i Would print the tree but… inverse! Useful for deleting the tree

todo Note: We can use In-order traversal to sort arrays. Create a BST by inserting every node from an array into one. Then, by traversing the BST via in-order traversal, we get the sorted array!

Worst case Big O: $O (N^{2})$ assuming the array is already in order. We’ve already discussed how each insert in the worst case is $O (N)$ . $N$ of those inserts gives $O (N^{2})$ . Then the in-order traversal is $O (N)$ so the total is $O (N^{2} + N) = O (N^{2})$

Had we used a self-balancing tree instead of a BST then the worst case would be the same as the average case discussed below

Average case Big O: The average insert takes $O (lo g (N))$ and we do that N times so it’s just $O (N lo g (N) + N) = O (N lo g (N))$ which is just as good as merge sort!

Tutorial problem

Set of instructions for robot
You’d want to add new instructions to the tail
But it’s slow! The reasonable unit of work would be comparisons.
2 big steps:
- Step 1: Load N commands from a text file and insert them at the tail
- Step 2:Traverse the linked list executing each command (Write the below on paper)
TASK 1: What is the complexity of traversing the linked-list of commands (step 2)
- $O (N)$ as we check every n nodes once.
TASK 2: (step 1)
- $O (N_{2})$ as for all n nodes (lines) we traverse n-1 of the old nodes to get to the tail of the linked list.
- The first node to insert would have 0 comparisons. The second would have 1 comparison (checking the tail). The third would cost 2 since we check the first node, then the tail, etc.
- So the total cost would be $0 + 1 + 2 + 3 + \dots + N - 3 + N - 2 + N - 1$ .
- So the formula (where $m = N - 1$ is $\frac{m ( m + 1 )}{2} = N^{2} /2 - N /2 ⟹ O (N^{2})$ complexity
- Alternatively, we can say that the worst case is when the list is size n; we would need to traverse $n - 1$ times for each n item which would also result in $O (N^{2})$

todo we submit this

🪴 Quartz 4.0

Explorer

03-05

deleting yay

Extra: Balancing a BST

Checking for balance (this was a mid-term question)

Complexity things again

The complexity for quick sort is $N L o g_{2} N + N = N L o g_{2} N$

Tutorial

Traversals

Tutorial problem

Graph View

Table of Contents

Backlinks

🪴 Quartz 4.0

Explorer

03-05

deleting yay

Extra: Balancing a BST

Checking for balance (this was a mid-term question)

Complexity things again

The complexity for quick sort is NLog2​N+N=NLog2​N

Tutorial

Traversals

Tutorial problem

Graph View

Table of Contents

Backlinks

The complexity for quick sort is $N L o g_{2} N + N = N L o g_{2} N$