UniveWiki

Appearance

Tree ​

Terminology ​

TermsDefinitionNotes
RootThe topmost node of a tree, which any non-empty tree must haver has no parents, level(r∈T)=0
ParentImmediate predecessor of a node vif u is the predecessor, then (u,v)∈A
ChildImmediate successor of a node uif v is the successor, then (u,v)∈A
SiblingsChildren of the same parent node
Path p from a node u to a node u′p=<n0,n1,…,nk> where <ni−1,ni>∈A with i=1,…,k
Length of a pathThere is always a path from u to u of length 0
Degree of a node
Level of a node
Depth of a node
Height of a node
Depth of a tree
Height of a node
Ancestor of a nodeEvery node is an ancestor of itself
Descendant of a nodeEvery node is a descendant of itself
Proper ancestor
Proper descendant
Subtree
Induced subtree
Internal node
Leaf/external node
Terminal node
Neighbour of anode

Trees ​

TreeDefintionNotes
Rooted treeIt is a pair T=(N,A) with |N|<∞ a finite set of nodes and A⊆N×N is a finite set of edges
Binary treeAn empty tree is a binary tree. A tree having a root node and two binary subtrees (respectively left subtree and right subtree) is a binary tree
K-ary treeA tree where the children of a node are labeled with distinct positive integers i∈N+∧i∈[1,k] and no labels larger than k are presentBinary tree is a 2-ary tree
Complete k-ary treeA k-ary where all the leaves have the same depth and all the internal nodes u have exactly deg(u)=kf(h=k)=kh, i(h=k)=kh−1/k−1, h=logk(n)
Balanced binary tree
Binary search tree

Data Structures ​

Data StructureS(n)Parent(Tree t, Node v)Children(Tree t, Node v)
Father's VectorΘ(n)T(n)=O(1)T(n)=Θ(n)
Positional Vector with complete k-ary treeΘ(n)T(n)=O(1)T(n)=O(k)
Pointers to Children with binary treeΘ(nk)T(n)=O(1)T(n)=O(1)
List of Pointers to Children---
Left Child Right SiblingΘ(n)T(n)=O(1)T(n)=Θ(deg(v))

General Tree ​

cpp

Binary Tree ​

cpp

BST ​

cpp

Visits ​

VisitOrder
Pre-OrderRoot > L-Child > R-Child
SymmetricL-Child > Root > R-Child
Post-OrderL-Child > R-Child > Root
BFSAt each level, go from L to R

Things that are useful for the exams ​

Height
Empty Tree−1

Decompose and Recombine ​

For divide-et-impera algorithms where we need to evaluate or verify some properties of the trees we have a blueprint

cpp
int recomb(Node u, Node v){
    // Combine answers
    // Return
}

int decomp(Node u){
    // BASE CASES: Empty Tree or Leaf, or any other given case...
    if(u == nullptr){
        // immediate answer
    }
    // DIVIDE ET IMPERA
    else{
        result_sx = decomp(u->left);     
        result_dx = decomp(u->right);
        // evaluate some more more conditions...
        
        //COMBINE
        return recomb(result_sx, result_dx);
    }
}
int recomb(Node u, Node v){
    // Combine answers
    // Return
}

int decomp(Node u){
    // BASE CASES: Empty Tree or Leaf, or any other given case...
    if(u == nullptr){
        // immediate answer
    }
    // DIVIDE ET IMPERA
    else{
        result_sx = decomp(u->left);     
        result_dx = decomp(u->right);
        // evaluate some more more conditions...
        
        //COMBINE
        return recomb(result_sx, result_dx);
    }
}
T(n)={T(k)+T(n−k−1)+dn>0cn=0

Exam ​

The implicit implementations for the exams are the following ones: