Thursday, 26 February 2015

  • . Trees and Graphs Trees, Binary Search Trees, Balanced Trees, Graphs
    • Svetlin Nakov
    • Telerik Corporation
    • www.telerik.com
  • 2. Table of Contents
    • Tree-like Data Structures
    • Trees and Related Terminology
    • Implementing Trees
    • Traversing Trees
    • Balanced Trees
    • Graphs
  • 3. Tree-like Data Structures Trees, Balanced Trees, Graphs, Networks
  • 4. Tree-like Data Structures
    • Tree-like data structures are
      • Branched recursive data structures
        • Consisting of nodes
        • Each node can be connected to other nodes
    • Examples of tree-like structures
      • Trees: binary / other degree, balanced, etc.
      • Graphs: directed / undirected, weighted, etc.
      • Networks
  • 5. Tree-like Data Structures Tree Graph 2 3 6 1 4 5 5 (20) 5 (10) 15 (15) 15 (30) 5 (5) 20(20) 10 (40) Network Project Manager Team Leader De-signer QA Team Leader Developer 1 Developer 2 Tester 1 Developer 3 Tester 2 7 19 21 14 1 12 31 4 11
  • 6. Trees and Related Terminology Node, Edge, Root, Children, Parent, Leaf , Binary Search Tree, Balanced Tree
  • 7. Trees
    • Tree data structure – terminology
      • Node, edge, root, child, children, siblings, parent, ancestor, descendant, predecessor, successor, internal node, leaf, depth, height, subtree
    Height = 2 Depth 0 Depth 1 Depth 2 17 15 14 9 6 5 8
  • 8. Binary Trees
    • Binary trees : most widespread form
      • Each node has at most 2 children
    10 17 15 9 6 5 8 Root node Left subtree Right child Right child Left child
  • 9. 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 2 ( x )
      • Balanced trees have for each node nearly equal number of nodes in its subtrees
  • 10. Binary Search Trees (2)
    • Example of balanced binary search tree
    • If the tree is balanced, add / search / delete operations take approximately log( n ) steps
    17 19 9 6 12 25
  • 11. Implementing Trees Recursive Tree Data Structure
  • 12. 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
  • 13. TreeNode<int> Structure TreeNode<int> int value List<TreeNode<int>> children 7 children 19 children 21 children 14 children 1 children 12 children 31 children 23 children 6 children
  • 14. 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]; }
  • 15.
    • 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
  • 16. Building a Tree
    • Constructing tree by nested constructors:
    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)) ); 7 14 19 23 6 21 31 1 12
  • 17. Tree Traversals DFS and BFS Traversals
  • 18. 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
  • 19.
    • 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; } 1 2 3 4 5 8 6 7 9 7 14 19 23 6 21 31 1 12
  • 20. DFS in Action (Step 1 )
    • Stack: 7
    • Output: (empty)
    7 14 19 23 6 21 31 1 12
  • 21. DFS in Action (Step 2 )
    • Stack: 7 , 19
    • Output: (empty)
    7 14 19 23 6 21 31 1 12
  • 22. DFS in Action (Step 3 )
    • Stack: 7 , 19 , 1
    • Output: (empty)
    7 14 19 23 6 21 31 1 12
  • 23. DFS in Action (Step 4 )
    • Stack: 7 , 19
    • Output: 1
    7 14 19 23 6 21 31 1 12
  • 24. DFS in Action (Step 5 )
    • Stack: 7 , 19 , 12
    • Output: 1
    7 14 19 23 6 21 31 1 12
  • 25. DFS in Action (Step 6 )
    • Stack: 7 , 19
    • Output: 1 , 12
    7 14 19 23 6 21 31 1 12
  • 26. DFS in Action (Step 7 )
    • Stack: 7 , 19 , 31
    • Output: 1 , 12
    7 14 19 23 6 21 31 1 12
  • 27. DFS in Action (Step 8 )
    • Stack: 7 , 19
    • Output: 1 , 12 , 31
    7 14 19 23 6 21 31 1 12
  • 28. DFS in Action (Step 9 )
    • Stack: 7
    • Output: 1 , 12 , 31 , 19
    7 14 19 23 6 21 31 1 12
  • 29. DFS in Action (Step 10 )
    • Stack: 7 , 21
    • Output: 1 , 12 , 31 , 19
    7 14 19 23 6 21 31 1 12
  • 30. DFS in Action (Step 11 )
    • Stack: 7
    • Output: 1 , 12 , 31 , 19 , 21
    7 14 19 23 6 21 31 1 12
  • 31. DFS in Action (Step 12 )
    • Stack: 7 , 14
    • Output: 1 , 12 , 31 , 19 , 21
    7 14 19 23 6 21 31 1 12
  • 32. DFS in Action (Step 13 )
    • Stack: 7 , 14 , 23
    • Output: 1 , 12 , 31 , 19 , 21
    7 14 19 23 6 21 31 1 12
  • 33. DFS in Action (Step 14 )
    • Stack: 7 , 14
    • Output: 1 , 12 , 31 , 19 , 21 , 23
    7 14 19 23 6 21 31 1 12
  • 34. DFS in Action (Step 15 )
    • Stack: 7 , 14 , 6
    • Output: 1 , 12 , 31 , 19 , 21 , 23
    7 14 19 23 6 21 31 1 12
  • 35. DFS in Action (Step 16 )
    • Stack: 7 , 14
    • Output: 1 , 12 , 31 , 19 , 21 , 23 , 6
    7 14 19 23 6 21 31 1 12
  • 36. DFS in Action (Step 17 )
    • Stack: 7
    • Output: 1 , 12 , 31 , 19 , 21 , 23 , 6 , 14
    7 14 19 23 6 21 31 1 12
  • 37. DFS in Action (Step 18 )
    • Stack: (empty)
    • Output: 1 , 12 , 31 , 19 , 21 , 23 , 6 , 14 , 7
    Traversal finished 7 14 19 23 6 21 31 1 12
  • 38.
    • 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 } 5 6 7 2 3 4 8 9 1 7 14 19 23 6 21 31 1 12
  • 39. BFS in Action (Step 1 )
    • Queue: 7
    • Output: 7
    7 14 19 23 6 21 31 1 12
  • 40. BFS in Action (Step 2 )
    • Queue: 7 , 19
    • Output: 7
    7 14 19 23 6 21 31 1 12
  • 41. BFS in Action (Step 3 )
    • Queue: 7 , 19 , 21
    • Output: 7
    7 14 19 23 6 21 31 1 12
  • 42. BFS in Action (Step 4 )
    • Queue: 7 , 19 , 21 , 14
    • Output: 7
    7 14 19 23 6 21 31 1 12
  • 43. BFS in Action (Step 5 )
    • Queue: 7 , 19 , 21 , 14
    • Output: 7 , 19
    7 14 19 23 6 21 31 1 12
  • 44. BFS in Action (Step 6 )
    • Queue: 7 , 19 , 21 , 14 , 1
    • Output: 7 , 19
    7 14 19 23 6 21 31 1 12
  • 45. BFS in Action (Step 7 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12
    • Output: 7 , 19
    7 14 19 23 6 21 31 1 12
  • 46. BFS in Action (Step 8 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31
    • Output: 7 , 19
    7 14 19 23 6 21 31 1 12
  • 47. BFS in Action (Step 9 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31
    • Output: 7 , 19 , 21
    7 14 19 23 6 21 31 1 12
  • 48. BFS in Action (Step 10 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31
    • Output: 7 , 19 , 21 , 14
    7 14 19 23 6 21 31 1 12
  • 49. BFS in Action (Step 11 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23
    • Output: 7 , 19 , 21 , 14
    7 14 19 23 6 21 31 1 12
  • 50. BFS in Action (Step 12 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
    • Output: 7 , 19 , 21 , 14
    7 14 19 23 6 21 31 1 12
  • 51. BFS in Action (Step 13 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
    • Output: 7 , 19 , 21 , 14 , 1
    7 14 19 23 6 21 31 1 12
  • 52. BFS in Action (Step 14 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
    • Output: 7 , 19 , 21 , 14 , 1 , 1 2
    7 14 19 23 6 21 31 1 12
  • 53. BFS in Action (Step 15 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
    • Output: 7 , 19 , 21 , 14 , 1 , 1 2 , 31
    7 14 19 23 6 21 31 1 12
  • 54. BFS in Action (Step 16 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
    • Output: 7 , 19 , 21 , 14 , 1 , 1 2 , 31 , 23
    7 14 19 23 6 21 31 1 12
  • 55. BFS in Action (Step 16 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
    • Output: 7 , 19 , 21 , 14 , 1 , 1 2 , 31 , 23 , 6
    7 14 19 23 6 21 31 1 12
  • 56. BFS in Action (Step 17 )
    • Queue: 7 , 19 , 21 , 14 , 1 , 12 , 31 , 23 , 6
    • Output: 7 , 19 , 21 , 14 , 1 , 1 2 , 31 , 23 , 6
    The queue is empty  stop 7 14 19 23 6 21 31 1 12
  • 57. Binary Trees DFS Traversals
    • DFS traversal of binary trees can be done in pre-order, in-order and post-order
      • Pre-order: left, root, right  6 , 9 , 12 , 17 , 19 , 25
      • In-order: root, left, right  17 , 9 , 6 , 12 , 19 , 25
      • Post-order: left, right, root  6 , 12 , 9 , 25 , 19 , 17
    17 19 9 6 12 25
  • 58. 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 }
  • 59. Trees and Traversals Live Demo
  • 60. Balanced Search Trees AVL Trees, B-Trees, Red-Black Trees, AA-Trees
  • 61. 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 log 2 (n) where n is the number of their nodes
      • Searching costs about log 2 (n) comparisons
  • 62. Balanced Binary Search Tree – Example 33 18 15 24 3 17 20 29 54 42 60 37 43 59 85
  • 63. 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 2 (n) steps
  • 64. B-Trees
    • B-trees are generalization of the concept of ordered binary search trees
      • B-tree of order d has between d and 2*d keys in a node and between d+1 and 2*d+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
  • 65.
    • B-Tree of order 2 , also known as 2 - 3 - 4 -tree:
    B-Tree – Example 17 21 7 11 18 20 26 31 2 4 5 6 8 9 12 16 22 23 25 27 29 30 32 35
  • 66. 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 &quot;Wintellect Power Collections for .NET&quot; are more flexible
      • http://powercollections.codeplex.com
  • 67. Graphs Definitions, Representation, Traversal Algorithms
  • 68. Graph Data Structure
    • Set of nodes with many-to-many relationship between them is called graph
      • Each node has multiple predecessors
      • Each node has multiple successors
    Node with multiple predecessors Node with multiple successors 7 19 21 14 1 12 31 4 11
  • 69. Graph Definitions
    • Node ( vertex )
      • Element of graph
      • Can have name or value
      • Keeps a list of adjacent nodes
    • Edge
      • Connection between two nodes
      • Can be directed / undirected
      • Can be weighted / unweighted
      • Can have name / value
    A Node A Edge B
  • 70. Graph Definitions (2)
    • Directed graph
      • Edges have direction
    • Undirected graph
      • Undirected edges
    7 19 21 1 12 4 3 22 2 3 G J F D A E C H
  • 71. Graph Definitions (3)
    • Weighted graph
      • Weight (cost) is associated with each edge
    3 G J F D A E C H Q K N 10 4 14 6 16 9 8 7 5 22
  • 72. Graph Definitions (4)
    • Path (in undirected graph)
      • Sequence of nodes n 1 , n 2 , … n k
      • Edge exists between each pair of nodes n i , n i+1
      • Examples:
        • A, B, C is a path
        • H, K, C is not a path
    G C B A H N K
  • 73. Graph Definitions (5)
    • Path (in directed graph)
      • Sequence of nodes n 1 , n 2 , … n k
      • Directed edge exists between each pair of nodes n i , n i+1
      • Examples:
        • A, B, C is a path
        • A, G, K is not a path
    G C B A H N K
  • 74. Graph Definitions (6)
    • Cycle
      • Path that ends back at the starting node
      • Example:
        • A, B, C, G, A
    • Simple path
      • No cycles in path
    • Acyclic graph
      • Graph with no cycles
      • Acyclic undirected graphs are trees
    G C B A H N K
  • 75. Graph Definitions (8)
    • Two nodes are reachable if
      • Path exists between them
    • Connected graph
      • Every node is reachable from any other node
    Unconnected graph with two connected components G J F D A Connected graph G J F D A E C H
  • 76. Graphs and Their Applications
    • Graphs have many real-world applications
      • Modeling a computer network like Internet
        • Routes are simple paths in the network
      • Modeling a city map
        • Streets are edges, crossings are vertices
      • Social networks
        • People are nodes and their connections are edges
      • State machines
        • States are nodes, transitions are edges
  • 77. Representing Graphs
    • Adjacency list
      • Each node holds a list of its neighbors
    • Adjacency matrix
      • Each cell keeps whether and how tw
        o nodes are connected
    • Set of edges
    1 2 3 4 1 2 3 4 {1,2} {1,4} {2,3} {3,1} {4,2} 1  {2, 4} 2  {3} 3  {1} 4  {2} 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 2 4 1 3
  • 78. Representing Graphs in C# public class Graph { int[][] childNodes; public Graph(int[][] nodes) { this.childNodes = nodes; } } Graph g = new Graph(new int[][] { new int[] {3, 6}, // successors of vertice 0 new int[] {2, 3, 4, 5, 6}, // successors of vertice 1 new int[] {1, 4, 5}, // successors of vertice 2 new int[] {0, 1, 5}, // successors of vertice 3 new int[] {1, 2, 6}, // successors of vertice 4 new int[] {1, 2, 3}, // successors of vertice 5 new int[] {0, 1, 4} // successors of vertice 6 }); 0 6 4 1 5 2 3
  • 79. Graph Traversal Algorithms
    • Depth-First Search (DFS) and Breadth-First Search (BFS) can traverse graphs
      • Each vertex should be is visited at most once
    BFS( node ) { queue  node visited[ node ] = true while queue not empty v  queue print v for each child c of v if not visited[ c ] queue  c visited[ c ] = true } DFS( node ) { stack  node visited[ node ] = true while stack not empty v  stack print v for each child c of v if not visited[ c ] stack  c visited[ c ] = true }
  • 80. Recursive DFS Graph Traversal void TraverseDFSRecursive(node) { if (not visited[node]) { visited[node] = true print node foreach child node c of node { TraverseDFSRecursive( c ); } } } vois Main() { TraverseDFS(firstNode); }
  • 81. Graphs and Traversals Live Demo
  • 82. 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)
  • 83. Trees and Graphs
    • Questions?
    http://academy.telerik.com
  • 84. Exercises
    • Write a program to traverse the directory C:WINDOWS and all its subdirectories recursively and to display all files matching the mask *.exe . Use the class System.IO.Directory .
    • Define classes File { string name, int size } and Folder { string name, File[] files , Folder[] childFolders } and using them build a tree keeping all files and folders on the hard drive starting from C:WINDOWS . Implement a method that calculates the sum of the file sizes in given subtree of the tree and test it accordingly. Use recursive DFS traversal.
  • 85. Exercises (2)
    • Implement the recursive Depth-First-Search (DFS) traversal algorithm. Test it with the sample graph from the demonstrations.
    • Implement the queue-based Breath-First-Search (BFS) traversal algorithm. Test it with the sample graph from the demonstrations.
    • Write a program for finding all cycles in given undirected graph using recursive DFS.
    • Write a program for finding all connected components of given undirected graph. Use a sequence of DFS traversals.
  • 86. Exercises (3)
    • Write a program for finding the shortest path between two vertices in a weighted directed graph. Hint: Use the Dijkstra's algorithm .
    • We are given a set of N tasks that should be executed in a sequence. Some of the tasks depend on other tasks. We are given a list of tasks { t i , t j } where t j depends on the result of t i and should be executed after it. Write a program that arranges the tasks in a sequence so that each task depending on another task is executed after it. If such arrangement is impossible indicate this fact.
    • Example: { 1 , 2 }, { 2 , 5 }, { 2 , 4 }, { 3 , 1 }  3 , 1 , 2 , 5 , 4 
    • REF:http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-graphs/#presentation-slides
Posted by at No comments:
Subscribe to: Posts (Atom)