- Tree-like Data Structures
- Trees and Related Terminology
- Implementing Trees
- Traversing Trees
- DFS and BFS Traversals

- Balanced Search Trees
- Balanced Trees in .NET

- Tree-like data structures are:
- Branched recursive data structures
- Consisting of
`nodes`

- Each node connected to other nodes

- Consisting of

- Branched recursive data structures
- Examples of tree-like structures
`Trees`

: binary, balanced, ordered, etc.`Graphs`

: directed / undirected, weighted, etc.`Networks`

`Tree`

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

`Binary trees`

: the most widespread form- Each node has at most 2 children

`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`

- All the elements of the left subtree of

- For each node
- 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

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

steps

- 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

```
public TreeNode(T value)
{
this.value = value;
this.children = new List<TreeNode<T>>();
}
public T Value
{
get { return this.value; }
set { this.value = value; }
}
public void AddChild(TreeNode<T> child)
{
child.hasParent = true;
this.children.Add(child);
}
public TreeNode<T> GetChild(int index)
{
return this.children[index];
}
```

- The class
`Tree<T>`

keeps tree’s root node

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

Flexible constructor for building trees

```
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))
);
```

`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

```
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
}
```

- 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

- 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
}
```

- Ordered Binary Trees (
`Binary Search Trees`

)- For each node
`x`

the left subtree has values`≤ x`

and the right subtree has values`> x`

- For each node
- 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

- Ordered binary search trees that have height of

- 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`

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

- B-tree of order
- 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

- .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

- 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)