A 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
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
Post a Comment