Time Complexity
Average Case complexity = average complexity over all possible inputs/situations (we need to know the likelihood of each of the input!)
Worst Case complexity = the worst complexity over all possible inputs/situations
Best Case complexity (mostly useless) = the best complexity over all possible inputs/situations
Amortized complexity = average time taken over a sequence of consecutive operations
Trees
Binary Search Tree
1. Definition
Binary Search Tree is a tree which is either empty or
- values in the left subtree are smaller than in the root.
- values in the right subtree are larger than in the root.
- root's left and right subtrees are also Binary Search Trees.
AVL Trees
The imbalance at a node is:
the height of its left subtree - the height of its right subtree
1. Definition
A binary tree is said to be AVL when the imbalance at each node is either 1,0 or -1.
2. Perfect Binary Tree = Maximal AVL tree of a given height
If the tree has height h, then the number of nodes is
3. Fibonacci trees = Minimal AVL trees of a given height
In general, we obtain the Fibonacci tree of height h+2 (called
the size of
= 1 + size of + size of .
Because all minimal AVL trees of a given height have the same size, we can pick just one representative AVL tree for every height.
Complexities
Fix out the relationship between Fibonacci trees and Fibonacci numbers, then get the height (number of comparation we might take) of tree from its size, then we can find complexities for search(x), insert(x) and delete(x) are