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

Live - solving the jasper report out of memory and high cpu usage problems

I still can not find the solution. So I summary all the things and tell my boss about it. If any one knows the solution, please let me know.


Symptom: 1.The JVM became Out of memory when creating big consumption report 2.Those JRTemplateElement-instances is still there occupied even if I logged out the system
Reason:         1. There is a large number of JRTemplateElement-instances cached in the memory 2.The clearobjects() method in ReportThread class has not been triggered when logging out
Action I tried:      About the Virtualizer: 1.Replacing the JRSwapFileVirtualizer with JRFileVirtualizer 2.Not use any FileVirtualizer for cache the report in the hard disk Result: The japserreport still creating the a large number of JRTemplateElement-instances in the memory     About the work around below,      I tried: item 3(in below work around list) – result: it helps to reduce  the size of the JRTemplateElement Object                Item 4,5 – result : it helps a lot to reduce the number of  JRTemplateE…