Please enable JavaScript.

Coggle requires JavaScript to display documents.

Trees - Coggle Diagram

- - - - Meassuring the height of the tree, for example
        
        The Height algorithm makes exactly one addition for every
        internal node of the extended tree, and it makes one comparison to check whether the tree is empty for every internal and external node
        
        The number of external nodes x is
        always 1 more than the number of internal nodes n
        
        The most important divide-and-conquer algorithms for binary trees are the
        three classic traversals: preorder, inorder, and postorder
        
        All three traversals visit
        nodes of a binary tree recursively, i.e., by visiting the tree’s root and its left and right subtrees. They differ only by the timing of the root’s visit
        
        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)
        
        In the preorder traversal, the root is visited before the left and right subtrees
        are visited (in that order)
- - - - Types of trees
        
        Rooted trees
        
        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
        
        Aplications
        
        describing
        hierarchies, from file directories to organizational charts of enterprises
        
        implementing dictionaries
        
        analysis of recursive
        algorithms
        
        state-space trees
        
        Important for backtracking and branch-and-bound
        
        For any vertex v in a tree T , all the vertices on the simple path from the root
        to that vertex are called ancestors of v
        
        The vertex itself is usually considered its
        own ancestor; the set of ancestors that excludes the vertex itself is referred to as the set of proper ancestors
        
        If (u, v) is the last edge of the simple path from the
        root to vertex v (and u = v), u is said to be the parent of v and v is called a child of u; vertices that have the same parent are said to be siblings. A vertex with no
        children is called a leaf ; a vertex with at least one child is called parental
        
        All the vertices for which a vertex v is an ancestor are said to be descendants of v; the
        proper descendants exclude the vertex v itself
        
        1 more item...
        
        Ordered trees
        
        An ordered tree is a rooted tree in which all the children of each
        vertex are ordered
        
        A binary tree can be defined as 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 a right child of its parents; a binary tree may also be empty
        
        It is possible to solve many problems involving binary trees
        by recursive algorithms
        
        In a binary search tree, a number assigned to each parental vertex is larger than all
        the numbers in its left subtree and smaller than all the numbers in its right subtree
        
        1 more item...