coding_ss/BST.java at master · Shikhar30Shah/coding_ss · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import java.util.*;
import java.time.*;
public class BST {
    class Node
    {
        int key;
        Node l,r;
        Node (int data)
        {
            key = data;
            l = r = null;
        }
    }
    Node root;
    BST ()
    {
        root = null;
    }
    void Insert (int data)
    {
        root = InsertNon(root, data);
    }
    Node InsertNon (Node root, int data)
    {
        if (root == null)
        {
            root = new Node(data);
            return root;
        }
        if (data < root.key)
            root.l = InsertNon(root.l, data);
        else if (data > root.key)
            root.r = InsertNon(root.r, data);
        return root;
    }
    int max(Node root)
    {
        int maximum = root.key;
        while(root.r!= null)
        {
            maximum = root.r.key;
            root = root.r;
        }
        return maximum;
    }
    void Delete (int data)
    {
        root = DeleteNon(root, data);
    }
    Node DeleteNon (Node root, int data)
    {
        if (root == null)
            return root;
        if (data < root.key)
            root.l = DeleteNon (root.l, data);
        else if (data > root.key)
            root.r = DeleteNon (root.r, data);
        else
        {
            if (root.l == null)
                return root.r;
            else if (root.r == null)
                return root.l;
            root.key = max(root.l);
            root.l = DeleteNon(root.l, root.key);
        }
        return root;
    }
    /*void inorder ()
    {
        inorderNon(root);
    }
    void inorderNon (Node root)
    {
        if (root != null)
        {
            inorderNon(root.l);
            System.out.print(root.key + " --> ");
            inorderNon(root.r);
        }
    }*/
    void Create (int n)
    {
        if (n != 0)
        {
            for (int i=1;i<=n;i++)
                Insert(i);
        }
    }
    public static void main (String args[])
    {
        BST bstree = new BST();
        int n = 8000;
        bstree.Create(n);
        Random rnd = new Random();
        double time1 = System.nanoTime();
        bstree.Insert(rnd.nextInt());
        double time2 = System.nanoTime();
        double timein = (time2-time1)/1000; //in microseconds
        System.out.println("The time taken for Insertion in BST for N = 2000 is " + timein + " (in microseconds)");
        double tim1 = System.nanoTime();
        bstree.Delete(rnd.nextInt(n));
        double tim2 = System.nanoTime();
        double timedel = (tim2-tim1)/1000; // in microseconds
        System.out.println("The time taken for Deletion in BST for N = 2000 is " + timedel + " (in microseconds)");
    }
}