Video: Trees and Tree Traversal Algorithms (Bulgarian)

July 20, 2020 Nikolay Kostov (Nikolay.IT)

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

Video (in Bulgarian)

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 treesare 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 treeshave 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; }
}
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

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)
    {
      this.root.AddChild(child.root);
    }
  }
  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

Breadth-First Search (BFS)

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