Subscribe To Our Newsletter
You will receive our latest post and tutorial.
Thank you for subscribing!

required
required


Graph

A graph data structure is a collection of nodes that have data and are connected to other nodes.

Let’s try to understand this through an example. On facebook, everything is a node. That includes User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note…anything that has data is a node.

Every relationship is an edge from one node to another. Whether you post a photo, join a group, like a page, etc., a new edge is created for that relationship.

A graph is a pair (V, E), where V is a set of nodes, called vertices, and E is a collection of pairs of vertices, called edges.

 

 

Applications of Graphs

  • Representing relationships between components in electronic circuits
  • Transportation networks: Highway network, Flight network
  • Computer networks: Local area network, Internet, Web
  • Databases: For representing ER (Entity Relationship) diagrams in databases, for

    representing dependency of tables in databases

November 12, 2019

Trees

Tree is a data structure similar to a linked list but instead of each node pointing simply to the next node in a linear fashion, each node points to a number of nodes. Tree is an example of non- linear data structures. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form.

A tree is a collection of entities called nodes. Nodes are connected by edges. Each node contains a value or data, and it may or may not have a child node 

The first node of the tree is called the root. If this root node is connected by another node, the root is then a parent node and the connected node is a child.

Tree Properties:

  • Root is the topmost node of the tree
  • Edge is the link between two nodes
  • Child is a node that has a parent node
  • Parent is a node that has an edge to a child node
  • Leaf is a node that does not have a child node in the tree
  • Height is the length of the longest path to a leaf
  • Depth is the length of the path to its root

General Tree

Properties

Usage

Types of Tree

  1.  Binary Tree 
  2.  Binary Search Tree 
  3.  AVL Tree 
  4.  B-Tree 

Binary Tree

A tree is called binary tree if each node has zero child, one child or two children. Empty tree is also a valid binary tree. We can visualize a binary tree as consisting of a root and two disjoint binary trees, called the left and right subtrees of the root.

Properties

  1. A left child precedes a right child in the order of children of a node. Or in other others, left side of tree is small than right side of tree

Usage

Note that Strict Binary Tree is a binary tree with each node has exactly two children or no children.

Full Binary Tree

A binary tree is called full binary tree if each node has exactly two children and all leaf nodes are at the same level.

Complete Binary Tree

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Properties
1. Every level is filled, except the last level.

2. All nodes are filled starting from left

 

Applications of Binary Trees

Following are the some of the applications where binary trees play an important role:

    • Expression trees are used in compilers.
    • Huffman coding trees that are used in data compression algorithms.
    • Binary Search Tree (BST), which supports search, insertion and deletion on a collection of items in O(logn) (average).
    • Priority Queue (PQ), which supports search and deletion of minimum (or maximum)on a collection of items in logarithmic time (in worst case).
    • Binary Search Trees(BSTs) are used to quickly check whether an element is present in a set or not.
    • Heap is a kind of tree that is used for heap sort.
    • A modified version of a tree called Tries is used in modern routers to store routing information.
    • Most popular databases use B-Trees and T-Trees, which are variants of the tree structure we learned above to store their data
    • Compilers use a syntax tree to validate the syntax of every program you write.
    • In HTML, the Document Object Model (DOM) works as a tree.
@NoArgsConstructor
@AllArgsConstructor
@Data
@ToString
public class TreeNode {

    private User data;
    private TreeNode left;
    private TreeNode right;
    
    public TreeNode(User data) {
        this.data = data;
    }
}

@ToString
@NoArgsConstructor
@AllArgsConstructor
@Data
class User implements Serializable, Comparable<User> {

    /**
     * 
     */
    private static final long serialVersionUID = 1L;
    private String            name;
    private Integer           rating;

    @Override
    public int compareTo(User other) {
        // TODO Auto-generated method stub
        return this.rating.compareTo(other.getRating());
    }
}

Insert data into Binary Tree

public TreeNode insert(TreeNode parent, User data) {
    /**
     * if node is null, put the data there
     */
    if (parent == null) {
        return new TreeNode(data);
    }

    User parentData = parent.getData();

    /**
     * if parent is greater than new node, go left<br>
     * if parent is less than new node, go right<br>
     */
    if (parentData.getRating() > data.getRating()) {
        parent.setLeft(insert(parent.getLeft(), data));
    } else {
        parent.setRight(insert(parent.getRight(), data));
    }

    return parent;
}

public TreeNode insert(User data) {
    if(root==null) {
        root = new TreeNode(data);
        return root;
    }
    return insert(root,data);
}

 

public class BinaryTreeMain {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        TreeNode root = new TreeNode();

        root.setData(new User("Folau", 20));

        BinaryTree binaryTree = new BinaryTree(root);

        binaryTree.insert(new User("Lisa", 30));
        binaryTree.insert(new User("Laulau", 15));
        binaryTree.insert(new User("Kinga", 12));
        binaryTree.insert(new User("Fusi", 35));
        binaryTree.insert(new User("Nesi", 34));
        binaryTree.insert(new User("Melenesi", 32));
        

        System.out.println("PreOrder Traversal");
        
        binaryTree.preOrder(root, "root");
        
        System.out.println("InOrder Traversal");
        
        binaryTree.inOrder(root);
        
        System.out.println("PostOrder Traversal");
        
        binaryTree.postOrder(root);
    }

}
PreOrder Traversal
root - User(name=Folau, rating=20)
left - User(name=Laulau, rating=15)
left - User(name=Kinga, rating=12)
right - User(name=Lisa, rating=30)
right - User(name=Fusi, rating=35)
left - User(name=Nesi, rating=34)
left - User(name=Melenesi, rating=32)
InOrder Traversal
User(name=Kinga, rating=12)
User(name=Laulau, rating=15)
User(name=Folau, rating=20)
User(name=Lisa, rating=30)
User(name=Melenesi, rating=32)
User(name=Nesi, rating=34)
User(name=Fusi, rating=35)
PostOrder Traversal
User(name=Kinga, rating=12)
User(name=Laulau, rating=15)
User(name=Melenesi, rating=32)
User(name=Nesi, rating=34)
User(name=Fusi, rating=35)
User(name=Lisa, rating=30)
User(name=Folau, rating=20)

Now that inserting elements into binary tree is done. We have ways to navigate through or traverse a tree data structure.

We have two options. Breadth-First Search(BFS) and Depth-First Search(DFS)

Depth-First Search

DFS is an algorithm for traversing or searching tree data structure. One starts at the root and explores as far as possible along each branch before backtracking.

DFS explores a path all the way to a leaf before backtracking and exploring another path. There 3 types of DFS: pre-order, in-order, and post-order

Inorder traversal

  1. First, visit all the nodes in the left subtree
  2. Then the root node
  3. Visit all the nodes in the right subtree

Time Complexity: O(n). Space Complexity: O(n)

/**
 * 1. Traverse the left subtree in Inorder.<br>
 * 2. Visit the root.<br>
 * 3. Traverse the right subtree in Inorder.<br>
 * Time Complexity: O(n). Space Complexity: O(n).<br>
 */
public void inOrder(TreeNode node) {
    if (node != null) {
        inOrder(node.getLeft());
        System.out.println(node.getData().toString());
        inOrder(node.getRight());
    }
}

Preorder traversal

  1. Visit root node
  2. Visit all the nodes in the left subtree
  3. Visit all the nodes in the right subtree

Time Complexity: O(n). Space Complexity: O(n)

/**
 * 1. Visit the root.<br>
 * 2. Traverse the left subtree in Preorder.<br>
 * 3. Traverse the right subtree in Preorder.<br>
 * Time Complexity: O(n). Space Complexity: O(n).
 */
public void preOrder(TreeNode node) {
    if (node != null) {
        System.out.println(node.getData().toString());
        preOrder(node.getLeft());
        preOrder(node.getRight());
    }
}

Postorder traversal

  1. Visit all the nodes in the left subtree
  2. Visit all the nodes in the right subtree
  3. Visit the root node

Time Complexity: O(n). Space Complexity: O(n).

/**
 * 1. Traverse the left subtree in Postorder.<br>
 * 2. Traverse the right subtree in Postorder.<br>
 * 3. Visit the root.<br>
 * Time Complexity: O(n). Space Complexity: O(n).<br>
 */
public void postOrder(TreeNode node) {
    if (node != null) {
        postOrder(node.getLeft());
        postOrder(node.getRight());
        System.out.println(node.getData().toString());
    }
}

 

Breadth-First Search

BFS is an algorithm for traversing or searching tree data structure. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.

BFS algorithm traverses the tree level by level and depth by depth.

public void bfs() {

    int level = 1;
    queue.add(new LevelNode(root, level));

    while (queue.isEmpty() != true) {
        LevelNode levelNode = queue.poll();
        TreeNode node = levelNode.getNode();
        
        level++;
        
        // 1. process node
        System.out.println("level: "+levelNode.getLevel()+", data: "+ node.getData().toString());
        
        // 2. push left and right child nodes onto queue
        if(node.getLeft()!=null) {
            queue.add(new LevelNode(node.getLeft(), level));
        }
        
        if(node.getRight()!=null) {
            queue.add(new LevelNode(node.getRight(), level));
        }
        
    }
}

Source code on Github

 

November 9, 2019

Heap

  1. Max-Heap: The value of a node must be greater than or equal to the values of its children. The greatest value is at the root. The same property must be true for all subtrees. 
    35 33 42 10 14 19 27 44 26 31

     


    Max-Heap construction

    Max-Heap deletion

    @NoArgsConstructor
@AllArgsConstructor
@Data
@ToString
public class MaxHeap {

    private List<Integer> data = new ArrayList<>();

    /**
     * Function to return the position of the parent for the node currently at position
     */
    private int parent(int position) {
        if (position == 0) {
            return 0;
        }
        return (position - 1) / 2;
    }

    /**
     * Function to return the position of the left child for the node currently at position
     */
    private int left(int position) {
        return (2 * position) + 1;
    }

    /**
     * Function to return the position of the right child for the node currently at position
     */
    private int right(int position) {
        return (2 * position) + 2;
    }

    private void swap(int firstPosition, int secondPosition) {
        System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition));
        int tmp = this.data.get(firstPosition);
        this.data.set(firstPosition, this.data.get(secondPosition));
        this.data.set(secondPosition, tmp);
        System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition));

    }

    public void add(int item) {
        this.data.add(item);

        // increase the size of an array Heap[++size] = element;
        int current = getSize() - 1;

        System.out.println("adding: " + item + " to position: " + current);

        heapifyUp(current);
    }

    public int peek() {
        return data.get(0);
    }

    /**
     * Step 1 − Remove root node.<br>
     * Step 2 − Move the last element of last level to root.<br>
     * Step 3 − Compare the value of this child node with its parent.<br>
     * Step 4 − If value of parent is less than child, then swap them.<br>
     * Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
     */
    public int poll() {
        int head = data.get(0);

        // replace the root of the heap with the last element
        data.set(0, this.data.get(getSize() - 1));
        data.remove(getSize() - 1);
        // call heapify-down on the root node
        heapifyDown(0);

        return head;
    }

    /**
     * Step 1 − Create a new node at the end of heap.<br>
     * Step 2 − Assign new value to the node.<br>
     * Step 3 − Compare the value of this child node with its parent.<br>
     * Step 4 − If value of parent is less than child, then swap them.<br>
     * Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
     */
    private void heapifyUp(int position) {
        int temp = this.data.get(position);

        if (position > 0 && temp > this.data.get(parent(position))) {
            System.out.println("heapifyUp - position: " + position + ", data: " + this.data.get(parent(position)));
            // swap the two if heap property is violated
            swap(position, parent(position));

            // call heapify-up on the parent
            heapifyUp(parent(position));
        }
    }

    /**
     * Step 1 − Remove root node.<br>
     * Step 2 − Move the last element of last level to root.<br>
     * Step 3 − Compare the value of this child node with its parent.<br>
     * Step 4 − If value of parent is less than child, then swap them.<br>
     * Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
     */
    private void heapifyDown(int position) {

        int largest = position;
        int leftChild = left(position);
        int rightChild = right(position);

        // compare `A[i]` with its left and right child
        // and find the largest value
        int size = getSize();

        if (leftChild < size && this.data.get(leftChild) > this.data.get(largest)) {
            largest = leftChild;
        }

        if (rightChild < size && this.data.get(rightChild) > this.data.get(largest)) {
            largest = rightChild;
        }

        if (largest != position) {

            // swap with a child having lesser value
            swap(position, largest);

            // call heapify-down on the child
            heapifyDown(largest);
        }
    }

    public void print() {
        System.out.println("\nList");
        for (Integer d : data) {
            System.out.println("data: " + d);
        }
        System.out.println("\nTree");
        System.out.println("Root: " + data.get(0));
        for (int i = 1; i <= getSize() / 2; i++) {

            try {
                System.out.print("Parent: " + this.data.get(i - 1));
            } catch (Exception e) {

            }

            try {
                System.out.print(", Left: " + this.data.get(this.left(i - 1)));
            } catch (Exception e) {

            }

            try {
                System.out.print(", Right: " + this.data.get((this.right(i - 1))));
            } catch (Exception e) {

            }
            System.out.println();
        }
        System.out.println("\n");
    }

    public int getSize() {
        return this.data.size();
    }

}

     

  2. Min-Heap: The value of a node is greater than or equal to the value of its parent. The smallest value is at the root. The same property must be true for all subtrees. 
    35 33 42 10 14 19 27 44 26 31

     

@NoArgsConstructor
@AllArgsConstructor
@Data
@ToString
public class MinHeap {

    private List<Integer> data = new ArrayList<>();

    /**
     * Function to return the position of the parent for the node currently at position
     */
    private int parent(int position) {
        if (position == 0) {
            return 0;
        }
        return (position - 1) / 2;
    }

    /**
     * Function to return the position of the left child for the node currently at position
     */
    private int left(int position) {
        return (2 * position) + 1;
    }

    /**
     * Function to return the position of the right child for the node currently at position
     */
    private int right(int position) {
        return (2 * position) + 2;
    }

    private void swap(int firstPosition, int secondPosition) {
        System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition));
        int tmp = this.data.get(firstPosition);
        this.data.set(firstPosition, this.data.get(secondPosition));
        this.data.set(secondPosition, tmp);
        System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition));

    }

    public void add(int item) {
        this.data.add(item);

        // increase the size of an array Heap[++size] = element;
        int current = getSize() - 1;

        System.out.println("adding: " + item + " to position: " + current);

        heapifyUp(current);
    }

    public int peek() {
        return data.get(0);
    }

    public int poll() {
        int head = data.get(0);

        // replace the root of the heap with the last element
        data.set(0, this.data.get(getSize() - 1));
        data.remove(getSize() - 1);
        // call heapify-down on the root node
        heapifyDown(0);

        return head;
    }

    /**
     * Step 1 − Create a new node at the end of heap.<br>
     * Step 2 − Assign new value to the node.<br>
     * Step 3 − Compare the value of this child node with its parent.<br>
     * Step 4 − If value of parent is greater than child, then swap them.<br>
     * Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
     */
    private void heapifyUp(int position) {
        int temp = this.data.get(position);

        if (position > 0 && temp < this.data.get(parent(position))) {
            System.out.println("heapifyUp - position: " + position + ", data: " + this.data.get(parent(position)));
            // swap the two if heap property is violated
            swap(position, parent(position));

            // call heapify-up on the parent
            heapifyUp(parent(position));
        }
    }


    /**
     * Step 1 − Remove root node.<br>
     * Step 2 − Move the last element of last level to root.<br>
     * Step 3 − Compare the value of this child node with its parent.<br>
     * Step 4 − If value of parent is greater than child, then swap them.<br>
     * Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
     */
    private void heapifyDown(int position) {

        int smallest = position;
        int leftChild = left(position);
        int rightChild = right(position);

        // compare `A[i]` with its left and right child
        // and find the smallest value
        int size = getSize();

        if (leftChild < size && this.data.get(leftChild) < this.data.get(smallest)) {
            smallest = leftChild;
        }

        if (rightChild < size && this.data.get(rightChild) < this.data.get(smallest)) {
            smallest = rightChild;
        }

        if (smallest != position) {

            // swap with a child having lesser value
            swap(position, smallest);

            // call heapify-down on the child
            heapifyDown(smallest);
        }
    }

    public void print() {
        System.out.println("\nList");
        for (Integer d : data) {
            System.out.println("data: " + d);
        }
        System.out.println("\nTree");
        System.out.println("Root: " + data.get(0));
        for (int i = 1; i <= getSize() / 2; i++) {

            try {
                System.out.print("Parent: " + this.data.get(i - 1));
            } catch (Exception e) {

            }

            try {
                System.out.print(", Left: " + this.data.get(this.left(i - 1)));
            } catch (Exception e) {

            }

            try {
                System.out.print(", Right: " + this.data.get((this.right(i - 1))));
            } catch (Exception e) {

            }
            System.out.println();
        }
        System.out.println("\n");
    }

    public int getSize() {
        return this.data.size();
    }

}

 

Heap Data Structure Applications

  • Heap is used while implementing a priority queue.
  • Dijkstra’s Algorithm
  • Heap Sort
November 3, 2019

CSS Introduction

CSS (Cascading Style Sheets) is used to style and lay out web pages — for example, to alter the font, color, size, and spacing of your content, split it into multiple columns, or add animations and other decorative features. It is a simple design language intended to simplify the process of making web pages presentable.

CSS handles the look and feel part of a web page. Using CSS, you can control the color of the text, the style of fonts, the spacing between paragraphs, how columns are sized and laid out, what background images or colors are used, layout designs,variations in display for different devices and screen sizes as well as a variety of other effects.

CSS is easy to learn and understand but it provides powerful control over the presentation of an HTML document. Most commonly, CSS is combined with the markup languages HTML or XHTML.

Advantages of CSS

  • CSS saves time − You can write CSS once and then reuse same sheet in multiple HTML pages. You can define a style for each HTML element and apply it to as many Web pages as you want.
  • Pages load faster − If you are using CSS, you do not need to write HTML tag attributes every time. Just write one CSS rule of a tag and apply it to all the occurrences of that tag. So less code means faster download times.
  • Easy maintenance − To make a global change, simply change the style, and all elements in all the web pages will be updated automatically.
  • Superior styles to HTML − CSS has a much wider array of attributes than HTML, so you can give a far better look to your HTML page in comparison to HTML attributes.
  • Multiple Device Compatibility − Style sheets allow content to be optimized for more than one type of device. By using the same HTML document, different versions of a website can be presented for handheld devices such as PDAs and cell phones or for printing.
  • Global web standards − Now HTML attributes are being deprecated and it is being recommended to use CSS. So its a good idea to start using CSS in all the HTML pages to make them compatible to future browsers.

 

How does CSS work?

When a browser displays a document, it must combine the document’s content with its style information. It processes the document in a number of stages, which we’ve listed below. Bear in mind that this is a very simplified version of what happens when a browser loads a webpage, and that different browsers will handle the process in different ways. But this is roughly what happens.

  1. The browser loads the HTML (e.g. receives it from the network).
  2. It converts the HTML into a DOM (Document Object Model). The DOM represents the document in the computer’s memory. The DOM is explained in a bit more detail in the next section.
  3. The browser then fetches most of the resources that are linked to by the HTML document, such as embedded images and videos … and linked CSS! JavaScript is handled a bit later on in the process, and we won’t talk about it here to keep things simpler.
  4. The browser parses the fetched CSS, and sorts the different rules by their selector types into different “buckets”, e.g. element, class, ID, and so on. Based on the selectors it finds, it works out which rules should be applied to which nodes in the DOM, and attaches style to them as required (this intermediate step is called a render tree).
  5. The render tree is laid out in the structure it should appear in after the rules have been applied to it.
  6. The visual display of the page is shown on the screen (this stage is called painting).

What happens if CSS has an error?

The answer is that it does nothing, and just moves on to the next bit of CSS!

If a browser is parsing your rules, and encounters a property or value that it doesn’t understand, it ignores it and moves on to the next declaration. It will do this if you have made an error and misspelled a property or value, or if the property or value is just too new and the browser doesn’t yet support it.

Similarly, if a browser encounters a selector that it doesn’t understand, it will just ignore the whole rule and move on to the next one.

November 3, 2019

Git branch

List all branches within a repository

git branch 

//or 

git branch --list

List all of remote branches

git branch -a

Create a local branch

git branch {branch-name}

Example: create a branch name test-100

git branch test-100

Check for the new created branch

folaukaveinga@Folaus-MacBook-Pro-3 demo % git branch
  develop
  master
  test-100

Push new local branch to remote

git push --set-upstream origin {branch-name}

Delete local branch

Use -d for safe delete. This means that if there are changes or commits in the branch that have not been commited or pushed up to remote, delete won’t work.

git branch -d {branch-name}

Use -D to force delete the specified branch, even if it has unmerged changes.

git branch -D {branch-name}

Delete a remote branch

git push origin --delete {branch-name}

 

Rename a branch locally

if you want to rename the branch remotely, Use push origin to reflect the change remotely.

git branch -m {new-branch-name}

Pull a remote branch to local

When you want to pull a remote branch to your local.

git pull origin {remote-branch-name}

// and

git checkout {remote-branch-name}

 

November 2, 2019
Prev
Next