Subarray merging
Merge Sort
Merge sort is a generally recursive algorithm that takes an array, divides it repeatedly until hitting the base case, where only one element is present. Then it compares the return of the base case with the next one, orders it and bubbles up with the sorted result.
Implementation
Complexity
Worst case complexity. Also depending on implementation $$ O(n)
# Trees - Trees are constructed from nodes. Nodes may now have pointers to one or more other nodes. - A set of nodes with a sinlge starting point is the root of the tree. - Each node is connected by an edge to another node (those edges are one-directional) - A tree is a connected graph - In a tree, every child has one parent (as opposed to in a graph) - A leaf is a node with no children - A binary tree is a tree with at most two children per node ## Binary trees - A binary trees is perfect if all of it's nodes have no or two nodes, and all leaves are at the same depth. - In a perfect binary tree, each level doubles the number of nodes, which means that a perfect binary tree of height h has2^h+1 -1
- A binary tree is complete if - the leaves are on at most two different levels - the second to bottom level is completely filled in - and the leaves on the bottom level are as far to the left as possible - A Binary tree is full if - every node has exactly 0 or 2 children. ## Tree height The height of a tree is the amount of edges from the root of a tree to the furthest leaf of the tree. ### Edge cases The height of a tree with one node is 0. The height of a tree with no nodes is -1. ## Tree Depth The depth of a node v is the length of the path from v to the root. # Qs Why -1? By definition should it still not be 0. 2^h + 1