Trees & Graphs
Still under HEAVY construction
Trees
Trees are a special type of graphs. More specifically, trees are graphs that follows certain rules:
- It has a single root (top) node
- Every node can have child nodes (k-ary)
- The tree is a directed graph (pointing downwards…)
- Trees do not contain cicles
- Each node in the tree can have just one parent
- All the nodes on a tree have to be connected
One othe most common tree is a binary tree (up to 2 child per node)
Node
A node is a fundamental part of a tree. It can have a name, which we call the “key.” A node may also have additional information. We call this additional information the “payload.” While the payload information is not central to many tree algorithms, it is often critical in applications that make use of trees.
Edge
An edge is another fundamental part of a tree. An edge connects two nodes to show that there is a relationship between them. Every node (except the root) is connected by exactly one incoming edge from another node. Each node may have several outgoing edges.
Root
The root of the tree is the only node in the tree that has no incoming edges. In Figure Figure 2, / is the root of the tree.
Level
The level of a node n is the number of edges on the path from the root node to n. For example, the level of the ‘J’ node in the tree below is three. By definition, the level of the root node is zero.
Height
The height of a tree is equal to the maximum level of any node in the tree. The height of the tree below Figure 2 is four.
A Level 0
____|____
/ \
B C 1
__|__ __|__
/ \ / \
D E F G 2
__|__ __|__
/ \ / \
H I J K 3
__|
/
L 4
A tree is COMPLETE if every single level in the tree is filled up with the possible exception of the final level that can be patially fill but that should be filled up from left to right
A tree is FULL if every node in the tree has either no childs or full k-ary children nodes
A tree is PERFECT if all the leaf node have the same depth
Complexity
Space O(N)
Traversing all nodes O(N)
Traver. subtrees O(log(N)) –> BUT, make sure tree is balnaced. An unbalanced tree will be O(N).
BST - Binary Search Tree
Is a binary with a property: a tree node is a BST if and only if its value is stricly greater than the values of every nodes to its left and its value is less then or equal to the values of every node to its right, and both of its children are either BST nodes themselves or None (null) values.
“Every node” node means not just at the same level, but all levels below.
There might be variation of the propoerty with regard of the “equal” value. Some might say BSTs do not have duplicates, some others might say they go in the left side…
A nice consequence of the BST properties is that for a given node, going always to the left will provide the smallest value for all the nodes in the under tree/subtree.
Graphs
A social network is a graph. The names are the vertices of the graph. (If you’re talking about just one of the vertices, it’s a vertex.) Each line (connection) is an edge, connecting two vertex. We denote an edge connecting vertices u and v by the pair (u,v). Because the “know each other” relationship goes both ways, the graph is undirected. An undirected edge (u,v) is the same as (v,u).
Edges connect vertices. Edges are represented by (u,v), meaning that there is an edge connecting vertices v and u.
In an undirected graph, an edge between two vertices is incident on the two vertices, and we say that the vertices connected by an edge are adjacent or neighbors. The number of edges incident on a vertex is the degree of the vertex.
The general term we use for a number that we put on an edge is its weight, and a graph whose edges have weights is a weighted graph.
The relationship between vertices does not always go both ways. When edges are directed we have a directed graph. If the directed graph has no cycles it is called a directed acyclic graph, or dag.
Graph representation
Edge list: List (or array) of edges (i.e [ [0,1], [0,3], [1,2] ] )
Adjacency matrix: Axis X and Y of the grid represent the vertices. A value of “1” in the means that the vertices x and y are connected (have an edge). The same graph in adjacency matrix form
[ [0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 0],
[1, 0, 0, 0] ]
Adjacency lists: For each vertex “i” , store an array of the vertices adjacent to it.
[ [1, 3],
[0, 2],
[1],
[0] ]