Tree


Tree is a non-linear data structure which organizes data in hierarchical structure and this is a recursive definition.

A tree T is a set of nodes storing elements such that the nodes have a parent-child
relationship that satisfies the following
If T is not empty, T has a special tree called the root that has no parent.
Each node N of T different than the root has a unique parent node P.

Different Types of Tree data structure

1)     Binary Tree
2)     Binary search tree
3)     AVL tree or height balanced binary tree
4)     Red-Black tree
5)     Splay tree
6)     N-ary tree
7)     Trie Structure
8)     Suffix tree
9)     Huffman Tree
10) B Trees (or general m-way search trees)
11) B+ Trees

Binary Tree

Binary tree provides the best possible ratio between the number of nodes and height. Height h for a complete binary tree with N nodes will be O(logN)
n = 1 + 2 + 4 + ... + 2h-1 + 2h = 2h+1 - 1

Solving for h
h = O(log n)

Binary Search Tree

A BST is a binary tree where nodes are ordered in the following way:
1)     each node contains one
2)     the keys in the left subtree are less then the key in its parent node, in short L < P;
3)     the keys in the right subtree are greater the key in its parent node, in short P < R;
4)     duplicate keys are not allowed.

Java program to create a Binary Search Tree:
BinarySearchTree-SourceCode

package com.mk.ds.tree;

public class BinarySearchTree<T> {
    public Node<T> root;

    public BinarySearchTree() {
        this.root = null;
    }

    public boolean find(int id) {
        Node<T> current = root;
        while (current != null) {
            if (current.data == id) {
                return true;
            } else if (current.data > id) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }

    public boolean delete(int id) {
        Node<T> parent = root;
        Node<T> current = root;
        boolean isLeftChild = false;
        while (current.data != id) {
            parent = current;
            if (current.data > id) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
            if (current == null) {
                return false;
            }
        }
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            }
            if (isLeftChild == true) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        } else if (current.left != null && current.right != null) {

            Node<T> successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    public Node<T> getSuccessor(Node<T> deleleNode) {
        Node<T> successsor = null;
        Node<T> successsorParent = null;
        Node<T> current = deleleNode.right;
        while (current != null) {
            successsorParent = successsor;
            successsor = current;
            current = current.left;
        }
        if (successsor != deleleNode.right) {
            successsorParent.left = successsor.right;
            successsor.right = deleleNode.right;
        }
        return successsor;
    }

    public void insert(int id) {
        Node<T> newNode = new Node<T>(id);
        if (root == null) {
            root = newNode;
            return;
        }
        Node<T> current = root;
        Node<T> parent = null;
        while (true) {
            parent = current;
            if (id < current.data) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }

    public void display(Node<T> root) {
        if (root != null) {
            display(root.left);
            System.out.print(" " + root.data);
            display(root.right);
        }
    }

    public static void main(String arg[]) {
        BinarySearchTree<Integer> b = new BinarySearchTree<>();
        b.insert(1);
        b.insert(2);
        b.insert(3);
        b.insert(4);
        b.insert(6);
        b.display(b.root);
    }
}

class Node<T> {
    int data;
    Node<T> left;
    Node<T> right;

    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

AVL Tree or Height balance binary tree

AVL tree is self-balancing binary search tree. In AVL tree the difference between left and right subtree can’t be more than one.
All the operation in tree depends on the height of tree if height is maintained or rebalanced after each insertion then sorting, searching, deletion etc operation will be efficient.
Refer below code for AVL Tree insertion-
AVLTreeSourceCode

package com.mk.ds.tree;

class AVLNode {
    int data, height;
    AVLNode left, right;

    AVLNode(int data) {
        this.data = data;
        height = 1;
        left = null;
        right = null;
    }
}

class AVLTree {
    AVLNode root;
    private int height(AVLNode N) {
        if (N == null)
            return 0;
        return N.height;
    }

    public AVLNode insert(AVLNode node, int value) {
        if (node == null)
            return (new AVLNode(value));
        if (value < node.data)
            node.left = insert(node.left, value);
        else if (value > node.data)
            node.right = insert(node.right, value);
        else
            return node;

        node.height = 1 + max(height(node.left),
                height(node.right));
        int balance = getBalance(node);
        if (balance > 1 && value < node.left.data)
            return rightRotate(node);
        if (balance < -1 && value > node.right.data)
            return leftRotate(node);
        if (balance > 1 && value > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        if (balance < -1 && value < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

    private int max(int leftNodeHeight, int rightNodeHeight) {
        return (leftNodeHeight > rightNodeHeight) ? leftNodeHeight : rightNodeHeight;
    }

    private AVLNode rightRotate(AVLNode avlNode) {
        AVLNode node = avlNode.left;
        AVLNode rightChild = node.right;

        node.right = avlNode;
        avlNode.left = rightChild;

        avlNode.height = max(height(avlNode.left), height(avlNode.right)) + 1;
        node.height = max(height(node.left), height(node.right)) + 1;

        return node;
    }

    private AVLNode leftRotate(AVLNode avlNode) {
        AVLNode node = avlNode.right;
        AVLNode leftChild = node.left;

        node.left = avlNode;
        avlNode.right = leftChild;

        avlNode.height = max(height(avlNode.left), height(avlNode.right)) + 1;
        node.height = max(height(node.left), height(node.right)) + 1;
        return node;
    }

    private int getBalance(AVLNode N) {
        if (N == null)
            return 0;
        return height(N.left) - height(N.right);
    }

    public void display(AVLNode root) {
        if (root != null) {
            display(root.left);
            System.out.print(" " + root.data);
            display(root.right);
        }
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 15);
        tree.root = tree.insert(tree.root, 17);
        tree.display(tree.root);
    }
}
Red black Tree-

Red Black tree properties –
1)     All the Nodes are either black or red.
2)     Root node will always be black.
3)     No adjacent node will be red
4)     Every patch from root to null leaf have the same no of black nodes.
5)     The height of Red Black tree will always be O(log N)
6)     Leaf node are also assume as black node.
7)     AVL trees are more balanced than Red Black tree but in AVL there are more re-balancing take place as compare to Red Black tree
8)     In Red Black tree first recoloring occurs if it doesn’t work than rotation occurs.


Splay Tree-

Splay tree is also self-balancing BST.
The main idea of splay tree is to bring the recently accessed item to root of the tree, this makes the recently searched item to be accessible in O(1) time if accessed again.
Generally in billions of the records only few records are accessed frequently, which is very often in many practical applications.
Whenever a search is called for a node we do a rotation to make the searched node as root node.

N-ary Tree-

N-Ary tree is a tree in which nodes can have at most N children

Trie Structure

1)     Trie is a discreet data structure,
2)     This also known as digital tree, radix tree or prefix tree.
3)     It’s a ordered tree structure which take advantage of string keys.
4)     In binary search tree each node have at max two child node but in trie tree can have more than two child node.
5)     In a trie, every node (except the root node) stores one character or a digit. By traversing the trie down from the root node to a particular node n, a common prefix of characters or digits can be formed which is shared by other branches of the trie as well.

Suffix tree

A suffix tree is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix tree allows a particularly fast implementation of many important string operations. The construction of such a tree for the string S takes time and space linear in the length of S. Once constructed, several operations can be performed quickly

Huffman Tree

1)     Huffman trees each node has zero or two children
2)     The data in each leaf node is unique and only leaf nodes have data

B Trees (or general m-way search trees)

1)     B-tree nodes can have more than two children.
2)     A B-tree node may contain more than one element.


B+ Trees

B+-tree maintains the following invariants:

1)     Every node has one more references than it has keys.
2)     All leaves are at the same distance from the root.
3)     For every non-leaf node N with k being the number of keys in N: all keys in the first child's subtree are less than N's first key; and all keys in the ith child's subtree (2 ≤ i ≤ k) are between the (i − 1)th key of n and the ith key of n.
4)     The root has at least two children.
5)     Every non-leaf, non-root node has at least floor(d / 2) children.
6)     Each leaf contains at least floor(d / 2) keys.
7)     Every key from the table appears in a leaf, in left-to-right sorted order.

B Tree vs B+ Trees

1)     In B tree, data are stored in internal or leaf nodes. But in B+-tree, data is stored only in leaf nodes.
2)     B+ trees store search keys but B tree has no redundant value.
3)     In a B+ tree, leaf nodes data are ordered as linked list but in B tree the leaf node cannot be stored using a linked list. Many database systems' implementations prefer the structural simplicity of a B+ tree.





1 comment:

Subscribe to: Posts (Atom)