Skip to main content

Binary search tree


binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
  • Both the left and right subtrees must also be binary search trees. 

Searching

Searching a binary search tree for a specific value can be a recursive or iterative process. 
bool BinarySearchTree::search(int val)
{
    Node *next = this->root();
 
    while (next != NULL) {
        if (val == next->value()) {
            return true;
        } else if (val < next->value()) {
            next = next->left();   
        } else {
            next = next->right();
        }
    } 
 
    //not found
    return false;
}


Insertion

Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees as before. Eventually, we will reach an external node and add the value as its right or left child, depending on the node's value. In other words, we examine the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than or equal to the root.
// implementation by recursion 
private static void internalInsert(Node node, int data){
    // Not the same value twice
    if (data == node.getValue()) {
        return;
    } else if (data < node.getValue()) {
        if (node.getLeft() == null) {
            node.setLeft(new TreeNode(data, null, null));
        }else{
            internalInsert(node.getLeft(), data);
        }
    }else{
        if (node.getRight() == null) {
            node.setRight(new TreeNode(data, null, null));
        }else{
            internalInsert(node.getRight(), data);
        }       
    }
}


//implementation by iteration
private Node m_root;
 
public void insert(int data) {
    if (m_root == null) {
        m_root = new TreeNode(data, null, null);
        return;
    }
    Node root = m_root;
    while (root != null) {
        // Not the same value twice
        if (data == root.getData()) {
            return;
        } else if (data < root.getData()) {
            // insert left
            if (root.getLeft() == null) {
                root.setLeft(new TreeNode(data, null, null));
                return;
            } else {
                root = root.getLeft();
            }
        } else {
            // insert right
            if (root.getRight() == null) {
                root.setRight(new TreeNode(data, null, null));
                return;
            } else {
                root = root.getRight();
            }
        }
    }
}


Deletion

There are three possible cases to consider:
  • Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
  • Deleting a node with one child: Remove the node and replace it with its child.
  • Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Replace the value of N with the value of R, then delete R.

Sort

A binary search tree can be used to implement a simple but efficient sorting algorithm. Similar to heapsort, we insert all the values we wish to sort into a new ordered data structure—in this case a binary search tree—and then traverse it in order, building our result:

The complete code for the BST class, is as follows:
public class BST {
public static void main(String[] args)
{
BST bst = new BST();
        int[] input = new int[] { 8, 3, 8, 10, 1, 6, 14, 4, 7, 13 };

        for (int i : input) {
            bst.insert(i);
        }

        System.out.println( "\nInorder Traversal:");
        bst.inorderTraversal();
  }

private BSTNode root;
 
   public void insert(int key) {
       insert(new BSTNode(key, null, null));
   }
 
   public void insert(BSTNode z) {
 
    //the note to be the parent of new code z
    BSTNode y = null;
    // the variable used to traverse the tree to find the place for z to be inserted.
    BSTNode x = root;
 
       while (x != null) {
           y = x;
 
           // 
           if (z.getKey() < x.getKey()) {
               x = x.getLeftChild();
           } else {
               x = x.getRightChild();
           }
       }
 
       z.setParent(y);
 
       if (y == null) {
           root = z;
       } else if (z.getKey() < y.getKey()) {
           y.setLeftChild(z);
       } else {
           y.setRightChild(z);
       }
   }
 
public void inorderTraversal() {
       inorderTraversal(root);
   }
 
   private void inorderTraversal(BSTNode node) {
       if (node != null) {
           inorderTraversal(node.getLeftChild());
           System.out.print(node.getKey() + " ");
           inorderTraversal(node.getRightChild());
       }
   }
 
}

class BSTNode {
 
    private int key;
    private BSTNode parent;
    private BSTNode leftChild;
    private BSTNode rightChild;

    public BSTNode(int key, BSTNode leftChild, BSTNode rightChild) {
        this.setKey(key);
        this.setLeftChild(leftChild);
        this.setRightChild(rightChild);
    }

    public void setKey(int key) {
        this.key = key;
    }

    public int getKey() {
        return key;
    }

    public void setParent(BSTNode parent) {
        this.parent = parent;
    }

    public BSTNode getParent() {
        return parent;
    }

    public void setLeftChild(BSTNode leftChild) {
        this.leftChild = leftChild;
    }

    public BSTNode getLeftChild() {
        return leftChild;
    }

    public void setRightChild(BSTNode rightChild) {
        this.rightChild = rightChild;
    }

    public BSTNode getRightChild() {
        return rightChild;
    }
}



Comments

Popular posts from this blog

Stretch a row if data overflows in jasper reports

It is very common that some columns of the report need to stretch to show all the content in that column. But  if you just specify the property " stretch with overflow' to that column(we called text field in jasper report world) , it will just stretch that column and won't change other columns, so the row could be ridiculous. Haven't find the solution from internet yet. So I just review the properties in iReport one by one and find two useful properties(the bold highlighted in example below) which resolve the problems.   example:
<band height="20" splitType="Stretch"> <textField isStretchWithOverflow="true" pattern="" isBlankWhenNull="true"> <reportElement stretchType="RelativeToTallestObject" mode="Opaque" x="192" y="0" width="183" height="20"/> <box leftPadding="2"> <pen lineWidth="0.25"/> …

JasperReports - Configuration Reference

Spring - Operations with jdbcTemplate

This class manages all the database communication and exception handling using a java.sql.Connection that is obtained from the provided DataSource. JdbcTemplate is a stateless and threadsafe class and you can safely instantiate a single instance to be used for each DAO.


Use of Callback Methods
JdbcTemplate is based on a template style of programming common to many other parts of Spring. Some method calls are handled entirely by the JdbcTemplate, while others require the calling class to provide callback methods that contain the implementation for parts of the JDBC workflow. This is another form of Inversion of Control. Your application code hands over the responsibility of managing the database access to the template class. The template class in turn calls back to your application code when it needs some detail processing filled in. These callback methods are allowed to throw a java.sql.SQLException, since the framework will be able to catch this exception and use its built-in excepti…