Tuesday, June 10, 2014

[Binary Tree] : List construction and operations using a Binary Tree [Array Implementation] [Java]

We'll construct a list of a predefined size using a binary tree with support for delete operation.
To find an element in this list is more efficient that linear search in arrays. The number of operations to be performed is less than or equal to the depth d of the tree plus 1 (d+1).

1. n is the number of leaves i.e. the number of elements to be contained in the list
2. d is the depth of the tree
3. Nodes are numbered starting at 0 for the root of the binary tree.
4. size is the number of nodes (leaves+non leaves) in the binary tree and is given by 2*n-1
    i.e.  

    size = 2 * n - 1
5. The first elements of the list are assigned to nodes numbered 2^d - 1 through 2* n - 2 and
6. the remainder (if any) to nodes numbered n - 1 through 2 ^ d - 2
7. info field contains the content of the node
8. BLANKS in info means that the node is non-leaf node
9. lcount stands for the number of leaves in the left subtree of the node. (left child)
10. lcount = 0 means that the node is a leaf node.
11. buildtree takes user input to build the binary tree structure of the list.
12. findelement is a method that can be used to access the list contents using their indexes with number of           operations less than d+1
13. delete method deletes an element from the list and restructure the binary tree.

                    0
             1             2
     3           4    5          6

if we delete list element 4 i.e. element number 6 in the binary tree structure, the resulting structure will become

                    0
             1             2->this element will store the contents of element #5
     3           4  

14. Display method displays the list content starting from element number 1 in the list.

Code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class TreeArray {

    private static int MAXELTS = 100;
    private static int NUMNODES = 2 * MAXELTS - 1;
    private static String BLANKS = "          ";

    static class nodetype {

        String info;
        int lcount;
        boolean used;
    }

    static nodetype[] node = new nodetype[NUMNODES];

    static {
        for (int i = 0; i < NUMNODES; ++i) {
            node[i] = new nodetype();
        }
    }

    static int findelement(int k) {
        int p, r;

        r = k;
        p = 0;
        while (node[p].info.matches(BLANKS)) {
            if (r <= node[p].lcount) {
                p = p * 2 + 1;
            } else {
                r -= node[p].lcount;
                p = p * 2 + 2;
            }
        }
        return p;
    }

    static void delete(int p) {
        int b, f, q;

        if (p == 0) {
            node[p].used = false;
        } else {
            f = (p - 1) / 2;
            if (p % 2 != 0) {
                b = 2 * f + 2;
                --node[f].lcount;
            } else {
                b = 2 * f + 1;
            }

            if (!node[b].info.matches(BLANKS)) {
                node[f].info = node[b].info;
                node[b].used = false;
            }

            node[p].used = false;
            q = f;

            while (q != 0) {
                f = (q - 1) / 2;
                if (q % 2 != 0) {
                    --node[f].lcount;
                    b = 2 * f + 2;
                } else {
                    b = 2 * f + 1;
                }
                if (!node[b].used && !node[q].info.matches(BLANKS)) {
                    node[f].info = node[q].info;
                    node[q].used = false;
                }
                q = f;
            }
        }
    }

    static int size, n; //n is the number of leaves

    static void buildtree(int n) {
        int d, f, i, p, power;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        d = 0;
        power = 1;
        while (power < n) {
            ++d;
            power *= 2;
        }
        size = 2 * n - 1;
        int index = 0;
        for (i = power - 1; i < size; i++, index++) {
            try {
                System.out.println("Enter element #" + index + " info: ");
                node[i].info = br.readLine();
                node[i].used = true;
            } catch (IOException e) {
                System.out.println("Error reading input");
            }
        }
        for (i = n - 1; i < power - 1; i++, index++) {
            try {
                System.out.println("Enter element #" + index + " info: ");
                node[i].info = br.readLine();
                node[i].used = true;
            } catch (IOException e) {
                System.out.println("Error reading input");
            }
        }
        for (i = 0; i < n - 1; ++i) {
            node[i].used = true;
            node[i].lcount = 0;
            node[i].info = BLANKS;
        }

        for (i = n - 1; i < size; ++i) {
            p = i;
            while (p != 0) {
                f = (p - 1) / 2;
                if (p % 2 != 0) {
                    ++node[f].lcount;
                }
                p = f;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("Enter the size of the list: ");
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();

        buildtree(n);
        System.out.println("\nTree List contructed successfully!");

        System.out.println("\n\nIndex of element to display contents of: ");
        System.out.println("Contents: " + node[findelement(scan.nextInt())].info);

        System.out.println("Index of Element to delete: ");
        delete(findelement(scan.nextInt()));

        System.out.println();
        display(0);
    }

    static void display(int elementNo) {
        if ((elementNo * 2 + 1) < size && node[elementNo * 2 + 1].used == true) {
            if (!node[elementNo * 2 + 1].info.matches(BLANKS)) {
                System.out.println(node[elementNo * 2 + 1].info + " ");
            }
            display(elementNo * 2 + 1);
        }
        if ((elementNo * 2 + 2) < size && node[elementNo * 2 + 2].used == true) {
            if (!node[elementNo * 2 + 2].info.matches(BLANKS)) {
                System.out.println(node[elementNo * 2 + 2].info + " ");
            }
            display(elementNo * 2 + 2);
        }
    }
}

A sample run:

Enter the size of the list: 
4
Enter element #0 info: 
11
Enter element #1 info: 
22
Enter element #2 info: 
33
Enter element #3 info: 
44

Tree List contructed successfully!


Index of element to display contents of: 
4
Contents: 44
Index of Element to delete: 
4

11 
22 
33 

No comments:

Post a Comment