Binary Search Tree

 Binary Search Tree (BST) Implementation In Java

Binary Tree adalah struktur data yang mirip dengan Linked List. Bila Linked List dianalogikan sebagai rantai yang linier maka Binary Tree dianalogikan sebagai pohon. Binary Tree dikelompokkan menjadi tree yang tidak berurut (unordered Binary Tree) dan tree yang terurut (ordered Binary Tree).

Berikut Implementation In Java :

	class BST_class {
	class Node {
	int key;
	Node left, right;
	public Node(int data){
	key = data;
	left = right = null;
	}
	}
	Node root;
	BST_class(){
	root = null;
	}
	void deleteKey(int key) {
	root = delete_Recursive(root, key);
	}
	Node delete_Recursive(Node root, int key) {
	if (root == null) return root;
	if (key < root.key)
	root.left = delete_Recursive(root.left, key);
	else if (key > root.key)
	root.right = delete_Recursive(root.right, key);
	else {
	if (root.left == null)
	return root.right;
	else if (root.right == null)
	return root.left;
	root.key = minValue(root.right);
	root.right = delete_Recursive(root.right, root.key);
	}
	return root;
	}
	int minValue(Node root) {
	int minval = root.key;
	while (root.left != null) {
	minval = root.left.key;
	root = root.left;
	}
	return minval;
	}
	void insert(int key) {
	root = insert_Recursive(root, key);
	}
	Node insert_Recursive(Node root, int key) {
	if (root == null) {
	root = new Node(key);
	return root;
	}
	if (key < root.key)
	root.left = insert_Recursive(root.left, key);
	else if (key > root.key)
	root.right = insert_Recursive(root.right, key);
	return root;
	}
	void inorder() {
	inorder_Recursive(root);
	}
	void inorder_Recursive(Node root) {
	if (root != null) {
	inorder_Recursive(root.left);
	System.out.print(root.key + " ");
	inorder_Recursive(root.right);
	}
	}
	boolean search(int key) {
	root = search_Recursive(root, key);
	if (root!= null)
	return true;
	else
	return false;
	}
	Node search_Recursive(Node root, int key) {
	if (root==null || root.key==key)
	return root;
	if (root.key > key)
	return search_Recursive(root.left, key);
	return search_Recursive(root.right, key);
	}
	}
	class Main{
	public static void main(String[] args) {
	BST_class bst = new BST_class();
	bst.insert(45);
	bst.insert(10);
	bst.insert(7);
	bst.insert(12);
	bst.insert(90);
	bst.insert(50);
	System.out.println("BST yang telah dibuat:");
	bst.inorder();
	System.out.println("\n BST setelah delete 12:");
	bst.deleteKey(12);
	bst.inorder();
	System.out.println("\nBST setelah delete 90:");
	bst.deleteKey(90);
	bst.inorder();
	System.out.println("\nBST setelah delete 45:");
	bst.deleteKey(45);
	bst.inorder();
	boolean ret_val = bst.search (50);
	System.out.println("\n50 ditemukan dalam BST:\n" + ret_val );
	ret_val = bst.search (12);
	System.out.println("\n12 ditemukan dalam BST:\n" + ret_val );
	}
	}

view raw Implementation In Java hosted with ❤ by GitHub

Berikut Operasi pada binary tree Implementasi dari Source Code di atas:

	class BST_class {
	//node class that defines BST node
	class Node {
	int key;
	Node left, right;
	public Node(int data){
	key = data;
	left = right = null;
	}
	}
	// BST root node
	Node root;
	// Constructor for BST =>initial empty tree
	BST_class(){
	root = null;
	}
	//delete a node from BST
	void deleteKey(int key) {
	root = delete_Recursive(root, key);
	}
	//recursive delete function
	Node delete_Recursive(Node root, int key) {
	//tree is empty
	if (root == null) return root;
	//traverse the tree
	if (key < root.key) //traverse left subtree
	root.left = delete_Recursive(root.left, key);
	else if (key > root.key) //traverse right subtree
	root.right = delete_Recursive(root.right, key);
	else {
	// node contains only one child
	if (root.left == null)
	return root.right;
	else if (root.right == null)
	return root.left;
	// node has two children;
	//get inorder successor (min value in the right subtree)
	root.key = minValue(root.right);
	// Delete the inorder successor
	root.right = delete_Recursive(root.right, root.key);
	}
	return root;
	}
	int minValue(Node root) {
	//initially minval = root
	int minval = root.key;
	//find minval
	while (root.left != null) {
	minval = root.left.key;
	root = root.left;
	}
	return minval;
	}
	// insert a node in BST
	void insert(int key) {
	root = insert_Recursive(root, key);
	}
	//recursive insert function
	Node insert_Recursive(Node root, int key) {
	//tree is empty
	if (root == null) {
	root = new Node(key);
	return root;
	}
	//traverse the tree
	if (key < root.key) //insert in the left subtree
	root.left = insert_Recursive(root.left, key);
	else if (key > root.key) //insert in the right subtree
	root.right = insert_Recursive(root.right, key);
	// return pointer
	return root;
	}
	// method for inorder traversal of BST
	void inorder() {
	inorder_Recursive(root);
	}
	// recursively traverse the BST
	void inorder_Recursive(Node root) {
	if (root != null) {
	inorder_Recursive(root.left);
	System.out.print(root.key + " ");
	inorder_Recursive(root.right);
	}
	}
	boolean search(int key) {
	root = search_Recursive(root, key);
	if (root!= null)
	return true;
	else
	return false;
	}
	//recursive insert function
	Node search_Recursive(Node root, int key) {
	// Base Cases: root is null or key is present at root
	if (root==null || root.key==key)
	return root;
	// val is greater than root's key
	if (root.key > key)
	return search_Recursive(root.left, key);
	// val is less than root's key
	return search_Recursive(root.right, key);
	}
	}
	class Main{
	public static void main(String[] args) {
	//create a BST object
	BST_class bst = new BST_class();
	/* BST tree example
	45
	/ \
	10 90
	/ \ /
	7 12 50 */
	//insert data into BST
	bst.insert(45);
	bst.insert(10);
	bst.insert(7);
	bst.insert(12);
	bst.insert(90);
	bst.insert(50);
	//print the BST
	System.out.println("The BST Created with input data(Left-root-right):");
	bst.inorder();
	//delete leaf node
	System.out.println("\nThe BST after Delete 12(leaf node):");
	bst.deleteKey(12);
	bst.inorder();
	//delete the node with one child
	System.out.println("\nThe BST after Delete 90 (node with 1 child):");
	bst.deleteKey(90);
	bst.inorder();
	//delete node with two children
	System.out.println("\nThe BST after Delete 45 (Node with two children):");
	bst.deleteKey(45);
	bst.inorder();
	//search a key in the BST
	boolean ret_val = bst.search (50);
	System.out.println("\nKey 50 found in BST:" + ret_val );
	ret_val = bst.search (12);
	System.out.println("\nKey 12 found in BST:" + ret_val );
	}
	}

view raw BST Java hosted with ❤ by GitHub

Berikut output :