Trees

Trees

1. A tree is a connected acyclic graph

   • A graph that has no cycles but is not necessarily connected is called a forest
     • each of its connected components is a tree
   • the number of edges in a tree is always one less than the number of its vertices
   • for every two vertices in a tree, there always exists exactly one simple path from one of these vertices to the other
     • This property makes it possible to select an arbitrary vertex in a free tree and consider it as the root of the so-called rooted tree

2. Rooted tree

   • is usually depicted by placing its root on the top (level 0 of the tree), the vertices adjacent to the root below it (level 1) and so on

3. Ordered trees

   • is a rooted tree in which all the children of each vertex are ordered

4. Binary tree

   • an ordered tree in which every vertex has no more than two children and each child is designated as either a left child or a right child of its parent
     • can also be empty
     • A binary tree is usually implemented for computing purposes by a collection of nodes corresponding to vertices of the tree.
   • can also be defined recursively, what makes it possible to solve many problems involving binary trees by recursive algorithms

5. Searching and insertion in a binary search tree

   • binary search tree is a binary tree whose nodes contain elements of a set of orderable items, one element per node, so that for every node all elements in the left subtree are smaller and all the elements in the right subtree are greater than the element in the subtree’s root
     • When we need to search for an element of a given value v in such a tree, we do it recursively
       • If the tree is empty, the search ends in failure
       • If the tree is not empty, we compare v with the tree’s root K(r)
         • If they match, a desired element is found and the search can be stopped
         • if they do not match, we continue with the search in the left subtree of the root if v < K(r) and in the right subtree if v > K(r)
   • In the worst case of the binary tree search, the tree is severely skewed

6. The game of Nim

   • Nim is generally played with several piles of chips, but we consider the one-pile version first
     • Thus, there is a single pile of n chips
       • Two players take turns by removing from the pile at least one and at most m chips
         • the number of chips taken may vary from one move to another, but both the lower and upper limits stay the same
           • The standard approach to determining which positions are winning and which are losing is to investigate small values of n first
             • Any instance with 1 ≤ n ≤ m chips is obviously a winning position for the player to move next

7. Binary Tree Traversals and Related Properties

   • the definition itself divides a binary tree into two smaller structures of the same type
     • Because of that, many problems about binary trees can be solved by applying the divide-and-conquer technique
       • As an example, let us consider a recursive algorithm for computing the height of a binary tree
         • the height is defined as the length of the longest path from the root to a leaf
           • Hence, it can be computed as the maximum of the heights of the root’s left and right subtrees plus 1
             • We measure the problem’s instance size by the number of nodes n(T ) in a given binary tree T
               • the number of comparisons made to compute the maximum of two numbers and the number of additions A(n(T )) made by the algorithm are the same
                 • It helps in the analysis of tree algorithms to draw the tree’s extension by replacing the empty subtrees by special nodes.
                   • The extra nodes are called external
                   • The original nodes are called internal
   • The most important divide-and-conquer algorithms for binary trees are the three classic traversals: preorder, inorder, and postorder
     • In the preorder traversal, the root is visited before the left and right subtrees are visited (in that order).
     • In the inorder traversal, the root is visited after visiting its left subtree but before visiting the right subtree.
     • In the postorder traversal, the root is visited after visiting the left and right subtrees (in that order).

Bilder und Dateien der Mindmap