Trees

About

An absctract data type that represents a hierarchical tree structure with a set of connected nodes.

Useful fo represent data in a non-linear form, making them suitable for representing hierarquical relationships.

Each node in the tree can be connected to many children nodes (depending on the type of tree), but must be connected to exactly one parent node.

You may assume that in a Tree with V number of vertices (nodes), it will have $E = V - 1$ amount of E edges. (Because each node will have at least 1 edge, connecting it to it's parent node)

These constraints mean:

• There are no cycles or "loops". (no node can be its own ancestor)

• Each child can be treated like the root node of its own subtree. (Making recursion a useful technique for tree traversal)

Terminology

node	The fundamental unit of the tree that holds data.
edge	The connection between two nodes.
root	The topmost node. (Has depth 0)
leaf	Node without children.
height	The longest path from the root to the deepest leaf.
degree	For a given node, its the number of children. (A leaf has degree of 0)
depth	The number of edges from the root to the node.
level	The same as depth, but it starts the count from 1, instead of 0.

Traversing Trees

There are 3 types of tree traversals. (That depends on when you do the visiting of the node)

• Pre-Order traversal. (Visit the node, then go Left, then go Right)

• In-Order traversal. (Go Left, then visit the node, then go Right)

• Post-Order traversal. (Go Left, then go Right, then visit the node)

Tree Types

General Trees

Trees where a node may have any amount of children.

Binary Tree

A tree type in which each node has at most two children. (It may have 0, 1 or 2)

Traversing Binary Trees

function preOrderWalk(currNode: BinaryNode<T> | null): void {
    if (!currNode) return;
    // Visit node
    currNode.value;
    
    preOrderWalk(currNode.left);
    preOrderWalk(currNode.right);
}

function inOrderWalk(currNode: BinaryNode<T> | null): void {
    if (!currNode) return;
       
    preOrderWalk(currNode.left);
    // Visit node
    currNode.value;
    preOrderWalk(currNode.right);
}

function postOrderWalk(currNode: BinaryNode<T> | null): void {
    if (!currNode) return;
    
    preOrderWalk(currNode.left);
    preOrderWalk(currNode.right);
    
    // Visit node
    currNode.value;
}

Full Binary Tree

A sub-type where every node has either 0 or 2 children.

Complete Binary Tree

All levels, except possibly the last, are fully filled.

All nodes are as far left as possible.

Perfect Binary Tree

All internal nodes have two children.

All leaves are at the same level.

Binary Search Tree (BST)

A Binary Tree in which:

• The left child contains values smaller than the parent.

• The right child contains values greater than the parent.

Searching an element

Runs on $O(log N )$ up to $O(N)$ in the worst case, depending on how the Tree structure is.

function findBST(node: BinaryNode<T>, needle: T): boolean {
    if (!node) return false;
    if (node.value === needle) return true;
    if (node.value < needle) return findBST(node.right, needle);
    return findBST(node.left, needle);
}

Inserting an element

Just look for the place that satisfy BST conditions and add.

Will eventually unbalance the tree.

function insertInBST(node: BinaryNode<T>, ancestor: BinaryNode<T>, path: "left" | "right", value: T): void {
    if (!node) {
        const newNode = {
            value,
            left: undefined,
            right: undefined
        }
        ancestor[path] = newNode;
    }
    if (node.value < value) findBST(node.right, node, "right", value);
    else findBST(node.left, node, "left", value);
}

Deleting an element

Deleting is bit more complicated and have 3 separate cases to look for:

• Case 1: The deleted node $X$ has no children, so $Ancestor_X$ just points to undefined.
• Case 2: The deleted node $X$ has only 1 child, so $Ancestor_X$ points to $X$ child.
• Case 3: The deleted node $X$ has both children, so $Ancestor_X$ will point to either:

  • The largest decendent node of $X_{left\ child}$. (largest on small side)
  • The smallest decendent node of $X_{right\ child}$. (smallest on large side)

Having a height property on each node, helps choosing in Case 3 which child has the highest height.

And choosing the child with the highest helps pruning the tree and reducing its height.

function deleteInBST(node: BinaryNode<T>, value: T, ancestor: BinaryNode<T>, path: "left" | "right", value: T): T | undefined {
    
}

Balanced Binary Tree

A Binary Tree where the height difference between the left and right subtrees of every node is at most 1.

AVL Tree

A self-balancing Binary Search Tree where the height of the left and right subtrees differ by at most 1.

Is more aggressive in maintaining the Tree balanced, since it may have more rotations and more complex rotations. (Compared to the Red-Black Tree)

Preferred in specific cases, where the aggressive balance maintainence is required.

Balance Rules

Searching an element

Has a better search time than Red-Black Trees.

Inserting an element

Deleting an element

Red-Black Tree

It is a self-balancing Binary Search Tree with specific coloring rules to maintain balance.

Usually for most cases Red-Black Trees are preferred over AVL Trees.

The color field can be just a 1bit property like 0 or 1.

Color Rules

The root node is always Black.

By default every new node in the Tree will be Red. Then it wil be checked to see if it can keep being Red or if it will be changed to Black.

A Red node can only have Black parents and children.

Balance Rules

Searching an element

Inserting an element

Have a better insertion time than AVL Trees. (Since it is less aggressive in balancing the Tree)

Deleting an element

Trie

A General Tree specifically used for efficient retrieval of strings, commonly used in autocomplete features.

Each node can have any number of children.

Searching an element

Inserting an element

1. Starting a the root of Trie.

2. Grab one character of the string being added. (From left to right, in most Languages)

3. Check if the current node has this character.

   1. If it doesn't add the new node with this character.

4. Set the current node to this node and Repeat 2.

5. The last node which refers to the last character of the word being added, can have a flag like isWord to inform that this node completes a word on the Trie.

Deleting an element

1. Recursevely walk the Tree until the end of the deleted string.

2. Delete the nodes on the Post Section of the Recursion, that have only one child.

In some scenarios no nodes will be deleted only the isWord will be set to false.

Fenwick Tree (Binary Indexed Tree)

A tree used for efficient prefix sums and range queries.

B-Trees

Self-balancing Search Trees.

B-Trees can have N children.

B+ Trees

Self-balancing Search Trees designed for filesystems and database systems.

Heap

It is a Binary Tree where every child is:

• Smaller than the current node. (Max Heap)

• Larger than the current node. (Min Heap)

Heap has a weak ordering, meaning that it is not totally ordered like a BST.

The order is only locally maintained, enough to satisfy the Heap conditions above.

Heap is usually a Full Binary Tree or Complete Binary Tree.

Whenever a node is added or deleted, the Tree MUST be ajusted.

Used in priority queues for example.

Node sequence of Heap

Nodes of the Heap follow a sequence to defines the first and last node of the Tree.

This sequence also helps on insertion and deletion, since inserted elements are added to the end (or last position), and deleted elements are deleted at position 0 (first position).

Inserting an element (Tree)

1. Elements are added at either:

   • The last level (height) where you have an empty space. (Usually from left to right)

   • New created level. (Usually from left to right)

2. Then check the added element $X$ against $Ancestor_X$ to see if it satisfy Heap conditions.
3. Repeat 2. until Heap conditions are satisfied.

The repeat 2. process is called Heapify Up, where the added node thies to bubble up in the Tree.

Runs on $O(log N )$ since the Tree is always balanced.

Deleting an element (Tree)

1. The top element is the one deleted.

2. Then the very last node $X$ in the Tree takes the place of the top node.
3. The $X$ node is checked against:

   1. In a MinHeap, the smallest of $X_{child}$, then if $X_{child} < X$ they swapp positions.
   2. In a MaxHeap, the highest of $X_{child}$, then if they swapp positions.
4. Repeat 3. until Heap conditions are satisfied.

The repeat 3. process is called Heapify Down, where the node that took place of the deleted node tries to bubble down in the Tree.

Runs on $O(log N )$ since the Tree is always balanced.

Implementing Heap with Arrays

Heaps can easily be implemented with Arrays Data Structures, and thus facilitating the removal of nodes.

You simulate left and right childs and parent nodes in Arrays with the following formulas: (where i is the current node index being looked)

• left child: $2i + 1$
• right child: $2i + 2$
• parent node: $\lfloor\frac{(i-1)}{2}\rfloor$

class MinHeap<T> {
    length: number = 0;
    #data: T[] = [];
    
    insert(value: T): void {
        this.data[this.length] = value;
        this.heapifyUp(this.length);
        this.length++;
    }
    
    delete(): T | undefined {
        if (this.length === 0) return undefined;
        if (this.length === 1) {
            this.length--;
            return this.data.pop();
        }
        const removed = this.data[0];
        this.data[0] = this.data[this.length - 1];
        delete this.data[this.length - 1];
        this.length--;
        this.heapifyDown(0);
        return removed;
    }
    
    private heapifyUp(i: number): void {
        if (i === 0) return;
        
        const parentI = this.parent(i);
        const parentValue = this.data[parentI];
        const currValue = this.data[i];
        
        // Since it is MinHeap we bubble up the value if currValue is smaller
        if (parentValue > currValue) {
            this.data[i] = parentValue;
            this.data[parentI] = currValue;
            this.heapifyUp(parentI);
        }
    }
    private heapifyDown(i: number): void {
        if (i >= this.length) return;
        
        const currLeftI = this.leftChild(i);
        const currRightI = this.rightChild(i);
        if (currLeftI >= this.length) return;
        
        const currLeftValue = this.data[currLeftI];
        const currRightValue = this.data[currRightI];
        const currValue = this.data[i];
        
        // Right node is the smallest child
        if (currLeftValue > currRightValue && currValue > currRightValue) {
            this.data[i] = currRightValue;
            this.data[currRightI] = currValue;
            this.heapifyDown(currRightI);
        }
        // Left node is the smallest child
        else if (currRightValue > currLeftValue && currValue > currLeftValue) {
            this.data[i] = currLeftValue;
            this.data[currLeftI] = currValue;
            this.heapifyDown(currLeftI);
        }
    }
    
    private parent(i: number): number {
        return Math.floor((i - 1) / 2);
    }
    private leftChild(i: number): number {
        return i * 2 + 1;
    }
    private rightChild(i: number): number {
        return i * 2 + 2;
    }
}