## Topics covered:

• Tree-like Data Structures
• Trees and Related Terminology
• Implementing Trees
• Traversing Trees
• DFS and BFS Traversals
• Balanced Search Trees
• Balanced Trees in .NET

## Presentation Content

### Tree-like Data Structures

• Tree-like data structures are:
• Branched recursive data structures
• Consisting of `nodes`
• Each node connected to other nodes
• Examples of tree-like structures
• `Trees`: binary, balanced, ordered, etc.
• `Graphs`: directed / undirected, weighted, etc.
• `Networks`

### Trees

• `Tree` data structure – terminology
• Node, edge, root, child, children, siblings, parent, ancestor, descendant, predecessor, successor, internal node, leaf, depth, height, subtree

### Binary Trees

• `Binary trees`: the most widespread form
• Each node has at most 2 children

### Binary Search Trees

• `Binary search trees`are `ordered`
• For each node `x` in the tree
• All the elements of the left subtree of `x` are `≤ x`
• All the elements of the right subtree of `x` are `> x`
• Binary search trees can be `balanced`
• `Balanced trees`have height of `~ log(x)`
• Balanced trees have for each node nearly equal number of nodes in its subtrees

### Binary Search Trees (2)

• Example of balanced binary search tree
• If the tree is balanced, add / search / delete operations take approximately `log(n)` steps

### Recursive Tree Definition

• The recursive definition for `tree` data structure:
• A single node is tree
• Tree nodes can have zero or multiple children that are also trees
• Tree node definition in C#
``````public class TreeNode<T>
{
private T value;
private List<TreeNode<T>> children;
…
}
``````

The value contained in the node
List of child nodes, which are of the same type

### Implementing TreeNode<T>

``````public TreeNode(T value)
{
this.value = value;
this.children = new List<TreeNode<T>>();
}
public T Value
{
get { return this.value; }
set { this.value = value; }
}
{
child.hasParent = true;
}
public TreeNode<T> GetChild(int index)
{
return this.children[index];
}
``````
• The class `Tree<T>` keeps tree’s root node

### Implementing Tree<T>

``````public class Tree<T>
{
private TreeNode<T> root;
public Tree(T value, params Tree<T>[] children) :    this(value)
{
foreach (Tree<T> child in children)
{
}
}
public TreeNode<T> Root
{
get {  return this.root; }
}
}
``````

Flexible constructor for building trees

### Building a Tree

``````Tree<int> tree =
new Tree<int>(7,
new Tree<int>(19,
new Tree<int>(1),
new Tree<int>(12),
new Tree<int>(31)),
new Tree<int>(21),
new Tree<int>(14,
new Tree<int>(23),
new Tree<int>(6))
);
``````

### Tree Traversal Algorithms

• `Traversing a tree` means to visit each of its nodes exactly one in particular order
• Many traversal algorithms are known
• `Depth-First Search`(DFS)
• Visit node’s successors first
• Usually implemented by recursion
• `Breadth-First Search`(BFS)
• Nearest nodes visited first
• Implemented by a queue
• `Depth-First Search` first visits all descendants of given node recursively, finally visits the node itself
• DFS algorithm pseudo code

### Depth-First Search (DFS)

``````DFS(node)
{
for each child c of node
DFS(c);
print the current node;
}
``````
• `Breadth-First Search` first visits the neighbor nodes, later their neighbors, etc.
• BFS algorithm pseudo code

``````BFS(node)
{
queue  node
while queue not empty
v  queue
print v
for each child c of v
queue  c
}
``````

### Binary Trees DFS Traversals

• DFS traversal of binary trees can be done in pre-order, in-order and post-order
• Pre-order: root, left, right → 17, 9, 6, 12, 19, 25
• In-order: left, root, right → 6, 9, 12, 17, 19, 25
• Post-order: left, right, root → 6, 12, 9, 25, 19, 17

### Iterative DFS and BFS

• What will happen if in the Breadth-First Search (BFS) algorithm a stack is used instead of queue?
• An iterative Depth-First Search (DFS) – in-order
``````BFS(node)
{
queue  node
while queue not empty
v  queue
print v
for each child c of v
queue  c
}
``````
``````DFS(node)
{
stack  node
while stack not empty
v  stack
print v
for each child c of v
stack  c
}
``````

### Balanced Binary Search Trees

• Ordered Binary Trees (`Binary Search Trees`)
• For each node `x` the left subtree has values `≤ x` and the right subtree has values `> x`
• Balanced Trees
• For each node its subtrees contain nearly equal number of nodes → nearly the same height
• Balanced Binary Search Trees
• Ordered binary search trees that have height of `log2(n)` where `n` is the number of their nodes
• Searching costs about `log2(n)` comparisons

### Balanced Binary Search Trees

• Balanced binary search trees are hard to implement
• Rebalancing the tree after insert / delete is complex
• Well known implementations of balanced binary search trees
• `AVL trees`– ideally balanced, very complex
• `Red-black trees`– roughly balanced, more simple
• `AA-Trees` – relatively simple to implement
• Find / insert / delete operations need `log(n)` steps

### B-Trees

• `B-trees` are generalization of the concept of ordered binary search trees
• B-tree of order `d` has between `d` and `2xd` keys in a node and between `d+1` and `2xd+1` child nodes
• The keys in each node are ordered increasingly
• All keys in a child node have values between their left and right parent keys
• If the b-tree is balanced, its search / insert / add operations take about log(n) steps
• B-trees can be efficiently stored on the disk

### Balanced Trees in .NET

• .NET Framework has several built-in implementations of balanced search trees:
• `SortedDictionary<K,V>`
• Red-black tree based map of key-value pairs
• `OrderedSet<T>`
• Red-black tree based set of elements
• External libraries like "`Wintellect Power Collections for .NET`" are more flexible

### Summary

• Trees are recursive data structure – node with set of children which are also nodes
• Binary Search Trees are ordered binary trees
• Balanced trees have weight of log(n)
• Graphs are sets of nodes with many-to-many relationship between them
• Can be directed/undirected, weighted / unweighted, connected / not connected, etc.
• Tree / graph traversals can be done by Depth-First Search (DFS) and Breadth-First Search (BFS)