Tree

B Tree implementation

Pinterest LinkedIn Tumblr

B-tree is a tree data structure that keeps data sorted and support search, sequential access, insertions, and deletions in logarithmic time. If the data is not able to store in main memory, it store in the secondary memory.

B-tree is optimized for systems that read and write large blocks of data. So, the B-tree is a good data structure for external memory. It accesses the minimum number of times when to access the record from database.

Write a program to implement B-Tree?

Algorithm Explanation

B-tree root has at least one key. It supports Insertions and deletions operations.
Insert operation inserts the key to the leaf node. Delete operations remove the node with non-empty subtree.
When data is inserted or removed from a node, its number of child nodes changes.
When to insert the element to the b-tree, it search the leaf node and add the new node. The delete operations search particular node and delete the node.

Source Code

package com.dsacode.DataStructre.btree;
 
import java.util.Random;
 
 
class BSTNode {
    public BSTNode left, right;
    public int data;
    public BSTNode(){
        left = null;
        right = null;
        data = 0;
    }
    public BSTNode(int n){
        left = null;
        right = null;
        data = n;
    }
 
}
 
class BT {
    private BSTNode root;
    public BT(){
        root = null;
    }
 
    public boolean isEmpty(){
        return root == null;
    }
 
    public void insert(int data){
        root = insert(root, data);
    }
 
    private BSTNode insert(BSTNode node, int data){
        if (node == null)
            node = new BSTNode(data);
        else{
            if (data <= node.data)
                node.left = insert(node.left, data);
            else
                node.right = insert(node.right, data);
        }
        return node;
    }
 
    public void delete(int k){
        if (isEmpty())
            System.out.println("Tree Empty");
        else if (search(k) == false)
            System.out.println("Sorry " + k + " is not present");
        else{
            root = delete(root, k);
            System.out.println(k + " deleted from the tree");
        }
 
    }
 
    private BSTNode delete(BSTNode root, int k) {
        BSTNode p, p2, n;
        if (root.data == k) {
            BSTNode lt, rt;
            lt = root.left;
            rt = root.right;
            if (lt == null && rt == null)
                return null;
            else if (lt == null){
                p = rt;
                return p;
            }else if (rt == null){
                p = lt;
                return p;
            }else{
                p2 = rt;
                p = rt;
                while (p.left != null)
                    p = p.left;
                p.left=(lt);
                return p2;
            }
        }
 
        if (k < root.data){
            n = delete(root.left, k);
            root.left=(n);
        }else{
            n = delete(root.right, k);
            root.right=n;
        }
        return root;
    }
 
    public int countNodes(){
        return countNodes(root);
    }
 
    private int countNodes(BSTNode r){
        if (r == null)
            return 0;
        else{
            int l = 1;
            l += countNodes(r.left);
            l += countNodes(r.right);
            return l;
        }
    }
 
    public boolean search(int val){
        return search(root, val);
    }
 
    private boolean search(BSTNode r, int val){
        boolean found = false;
        while ((r != null) && !found){
            int rval = r.data;
            if (val < rval)
                r = r.left;
            else if (val > rval)
                r = r.right;
            else{
                found = true;
                break;
            }
            found = search(r, val);
        }
        return found;
    }
 
    public void inorder(){
        inorder(root);
    }
 
    private void inorder(BSTNode r){
        if (r != null)  {
            inorder(r.left);
            System.out.print(r.data + " ");
            inorder(r.right);
        }
    }
 
    public void preorder(){
        preorder(root);
    }
 
    private void preorder(BSTNode r){
        if (r != null){
            System.out.print(r.data + " ");
            preorder(r.left);
            preorder(r.right);
        }
    }
}
 
public class BTreeImpl{
    public static int N = 20;
    public static void main(String args[]){
        Random random = new Random();
        BT bt = new BT();
 
        System.out.println("Sorting of randomly generated numbers using B TREE");
 
        for (int i = 0; i < N; i++)
            bt.insert(Math.abs(random.nextInt(100)));
 
        System.out.println("The elements of the tree: ");
        bt.preorder();
 
        System.out.println("\nThe sorted sequence is: ");
        bt.inorder();
 
    }
 
} 

Output

Sorting of randomly generated numbers using B TREE
The elements of the tree:
99 37 20 10 3 19 19 21 35 35 95 86 55 47 77 75 59 67 83 89
The sorted sequence is:
3 10 19 19 20 21 35 35 37 47 55 59 67 75 77 83 86 89 95 99

Source Explanation

The b-Tree application uses random to find the number to insert into the b-tree.
The insert operation gets the root node and the data. It makes sure the binary search tree property when to insert the data.
The delete operation checks the node from the tree. If the search operation finds the key, it delete and make sure the b-tree properties. If the key does not find in b-tree, it returns false.
The search operation get the value and root node. If the value is less than or equal to the root node, the search in the left subtree. If the node value is greater than or equal to root node it search the right subtree.

Complexity

OperationsBest CaseAverage Caseworst Case
SearchO(log(n))O(log(n))
InsertionO(log(n))O(log(n))
DeletionO(log(n))O(log(n))

Real Applications

  1. Databases use B-tree to store data
  2. CouchDB uses a data structure called a B-tree to index its documents and views

Reference

  1. https://www.cs.usfca.edu/~galles/visualization/BTree.html
  2. https://en.wikipedia.org/wiki/B-tree#In_filesystems
  3. http://www.bluerwhite.org/btree/
  4. http://www.semaphorecorp.com/btp/algo.html

Write A Comment