Binary tree: $O(n)$ for `insert`

, `delete`

and `search`

.

Some better trees:

- AVL Trees
- B-trees
- Splay trees
- Weight …

Similar to binary search tree. But also different in a few ways:

- The height of an AVL tree is $O(log n)$.
- Each internal node has a balance property equal to -1, 0, 1.
- Balance value = height of the left subtree - height of the right sub tree.

Have to store the height of sub-trees.

-1 - Right heavy, +1 - Left heavy, 0 - Balanced.

- Same as BST

After insert, if a node’s balance factor is not -1, 0 or +1, we have to do one single rotation to fix it.

If there is a “bent”, then we have to do double rotation

```
for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root)
// BalanceFactor(X) has to be updated:
if (Z == right_child(X)) { // The right subtree increases
if (BalanceFactor(X) > 0) { // X is right-heavy
// ===> the temporary BalanceFactor(X) == +2
// ===> rebalancing is required.
G = parent(X); // Save parent of X around rotations
if (BalanceFactor(Z) < 0) // Right Left Case (see figure 5)
N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X)
else // Right Right Case (see figure 4)
N = rotate_Left(X, Z); // Single rotation Left(X)
// After rotation adapt parent link
} else {
if (BalanceFactor(X) < 0) {
BalanceFactor(X) = 0; // Z’s height increase is absorbed at X.
break; // Leave the loop
}
BalanceFactor(X) = +1;
Z = X; // Height(Z) increases by 1
continue;
}
} else { // Z == left_child(X): the left subtree increases
if (BalanceFactor(X) < 0) { // X is left-heavy
// ===> the temporary BalanceFactor(X) == –2
// ===> rebalancing is required.
G = parent(X); // Save parent of X around rotations
if (BalanceFactor(Z) > 0) // Left Right Case
N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X)
else // Left Left Case
N = rotate_Right(X, Z); // Single rotation Right(X)
// After rotation adapt parent link
} else {
if (BalanceFactor(X) > 0) {
BalanceFactor(X) = 0; // Z’s height increase is absorbed at X.
break; // Leave the loop
}
BalanceFactor(X) = –1;
Z = X; // Height(Z) increases by 1
continue;
}
}
// After a rotation adapt parent link:
// N is the new root of the rotated subtree
// Height does not change: Height(N) == old Height(X)
parent(N) = G;
if (G != null) {
if (X == left_child(G))
left_child(G) = N;
else
right_child(G) = N;
break;
} else {
tree->root = N; // N is the new root of the total tree
break;
}
// There is no fall thru, only break; or continue;
}
// Unless loop is left via break, the height of the total tree increases by 1.
```

- If the key is a leaf, delete and rebalance.

Maximum possible height is $log(n)$, if we have $n$ nodes.

If the height is $h$, let `minsize(h)`

be the minimum number of nodes for an AVL tree of height $h$.

Then

```
minsize(0) = 0,
minsize(1) = 1,
minsize(h + 2) = 1 + minsize(h + 1) + minsize(h)
```

minsize(h) = fib(h+2) - 1 (why?)

$log_b(x) = log_b(a) * log_a(x)$

$lim_{n \to \infty} \frac{2^{3n}}{2^n} = lim_{n \to \infty} {2^{2n}} = \infty$

in Big O of | $ln(n)$ | lg_2(n) | lg_2(n^2) | (lg_2(n))^2 | n | n lg_2 n | 2^n | 2^{3n} |
---|---|---|---|---|---|---|---|---|

ln(n) | Y | Y | Y | Y | Y | Y | Y | Y |

log(n) | Y | Y | Y | Y | Y | Y | Y | Y |

log(n^2) | Y | Y | Y | Y | Y | Y | Y | Y |

(lg_2(n))^2 | N | N | N | Y | Y | Y | Y | Y |

n | N | N | N | N | Y | Y | Y | Y |

n log n | N | N | N | N | N | Y | Y | Y |

2^n | N | N | N | N | N | N | Y | Y |

2^{3n} | N | N | N | N | N | N | N | Y |

$\exists n_0, \exists c, \forall n, n \geq n_0 \implies f(n) \leq c \cdot g(n)$

$n \leq 1n$

$n \leq n \cdot log(n), n \geq 2$

$n \leq c \cdot n \cdot log(n)$

Therefore we have c = 1, and n_0 = 2.

Assume for a contradiction that $nlog(n) \in O(n)$, so

$\exists c, \exists n_0, \forall n, n \geq n_0 \implies nlog(n) \leq c \cdot n$.

$log(n) \leq c$ $n \leq 2^c$

Suppose $n > 2^c$, then $n \geq n_0 \implies n \leq 2^c$. Which is a contradiction.

First prove $6n^5 + n^2 - n^3 \in O(n^5)$

$\exists n_0, \exists c, \forall n, n \geq n_0 \implies f(n) \leq c \cdot g(n)$

$6n^5 + n^2 - n^3 \leq 6n^5 + n^2 \leq 6n^5 + n^5 \leq 7n^5$

Let c = 7, and n = 1.

Then prove $6n^5 + n^2 - n^3 \in \Omega(n^5)$

$\exists n_0, \exists c, \forall n, n \geq n_0 \implies f(n) \geq c \cdot g(n)$

$6n^5 + n^2 - n^3 \geq 6n^5 - n^3 \geq 5n^5$

Let c = 5, and n != 1.

$3n^2 - 4n \geq bn^2$

$3n - 4 \geq bn$

$3n - bn \geq 4$

$n(3-b) \geq 4$

$n \geq \frac{4}{3-b}$

```
-----------------
Applications
-----------------
Operating System
-----------------
Hardware
```

- Provides services
- Resource manager
- Control program (protection)

A process contains

- An address space
- Set of OS resources
- Set of general-purpose registers with current values

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Introduction to refactoring.

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Decorator pattern.

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Publish and Subscribe Pattern.

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Iterator and Builder design pattern.

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Introduction to JUnit.

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Polymorphism, Abstract Classes, Interfaces, Liskov, Singleton.

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

More topics on Java memory model.

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

CRC cards and how to properly develop software with a team.

A good piece of code should look clean, concise and does what it is supposed to do.

I am not an expert in software engineering, but during my time contributing to IFCAT project, I did find some design flaws, and this is how I fixed them.

This post mainly serves as my personal reference in the future when I try to code Node.js systems. But also is a good read for anyone who is new to programming.

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Java memory model and some CRC.

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Introduction to Java programming. This note assumes you are somewhat knows how to program, many obvious details are ignored.

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Basic introduction to version control and how to use SVN.

Notes taken for CSCB36 course at UofT, this post is for Chapter 6, Predicate Logic.

Notes taken for CSCB36 course at UofT, this post is for Chapter 5, Propositional Logic.

Notes taken for CSCB36 course at UofT, this post is for Chapter 0, mainly talks about sets and fundamental mathematical units.

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 5.2. For course MATA22 at UTSC.

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 5.1. For course MATA22 at UTSC.

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 4.2. For course MATA22 at UTSC.

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 4.1. For course MATA22 at UTSC.