Implementasi Binary Search Tree

 

Pengenalan Binary Search Tree

    Selain terdapat struktur data linear, seperti array, stack, dan queue, terdapat juga struktur data non-linear. Bentuk struktur data, seperti tree dan graph merupakan struktur data non-linear. Berbeda dengan struktur data linear, dimana setiap data dihubungkan satu demi satu, struktur data non-linear memiliki hubungan data yang dapat saling dihubungkan dengan aturan tertentu. Singkatnya struktur data non-linear cenderung memiliki struktur lebih fleksibel.

    Pada pembahasan kali ini yang dibahas adalah binary search tree (pohon biner). Pohon biner memiliki syarat tertentu dimana setiap data memiliki 2 anak, yaitu left child dan right child. Pada binary search tree left child memiliki data yang nilainya kurang dari data parent-nya. Sedangkan, right child memiliki data yang nilainya lebih dari data parent-nya. Selain itu, pohon biner juga memiliki root, dimana root merupakan parent tertinggi di pohon biner. Root tidak boleh memiliki parent.

Implementasi Binary Search Tree

    Untuk lebih memahaminya, dapat dilihat source code berikut

    

	/**
	* BST Implementation in Java
	*
	* @author Anggito Anju
	* @version ver 1.0 - 9 June 21
	*/
	public class BST
	{
	BSTNode root;
	BST() {
	root = null;
	}
	/* === UTILITY METHOD === */
	public static BSTNode find(BSTNode node, int value) {
	while(node != null) {
	if(value < node.data) {
	node = node.left;
	}
	else if(value > node.data) {
	node = node.right;
	}
	else {
	return node;
	}
	}
	return node;
	}
	public static BSTNode insert(BSTNode node, int value) {
	if(node == null) {
	BSTNode newNode = new BSTNode(value);
	node = newNode;
	}
	if(value < node.data) {
	node.left = insert(node.left, value);
	}
	else if(value > node.data) {
	node.right = insert(node.right, value);
	}
	return node;
	}
	public static BSTNode findMinNode(BSTNode node) {
	BSTNode curr = node;
	while(curr != null && curr.left != null) {
	curr = curr.left;
	}
	return curr;
	}
	public static BSTNode remove(BSTNode node, int value) {
	if(node == null) {
	return null;
	}
	if(value < node.data) {
	node.left = remove(node.left, value);
	}
	else if(value > node.data) {
	node.right = remove(node.right, value);
	}
	else {
	// Have left child only
	if(node.right == null) {
	BSTNode leftChild = node.left;
	node = null;
	return leftChild;
	}
	// Have right child only
	if(node.left == null) {
	BSTNode rightChild = node.right;
	node = null;
	return rightChild;
	}
	BSTNode temp = findMinNode(node.right);
	node.data = temp.data;
	node.right = remove(node.left, value);
	}
	return node;
	}
	/* === PRIMARY METHOD === */
	// Check if empty
	public static boolean bst_isEmpty(BST newBST) {
	return newBST.root == null;
	}
	// Find value in BST
	public static boolean bst_find(BST newBST, int value) {
	BSTNode temp = find(newBST.root, value);
	if(temp == null) {
	return false;
	}
	if(temp.data == value) {
	return true;
	}
	else {
	return false;
	}
	}
	// Add new value to BST
	public static void bst_insert(BST newBST, int value) {
	if(!bst_find(newBST, value)) {
	newBST.root = insert(newBST.root, value);
	}
	}
	// Remove value in BST
	public static void bst_remove(BST newBST, int value) {
	if(bst_find(newBST, value)) {
	newBST.root = remove(newBST.root, value);
	}
	}
	/* === TRAVERSAL METHODS === */
	/* UTILITY */
	public static void inorder(BSTNode node) {
	if(node != null) {
	inorder(node.left);
	System.out.print(node.data + " ");
	inorder(node.right);
	}
	}
	public static void preorder(BSTNode node) {
	if(node != null) {
	System.out.print(node.data + " ");
	preorder(node.left);
	preorder(node.right);
	}
	}
	public static void postorder(BSTNode node) {
	if(node != null) {
	postorder(node.left);
	postorder(node.right);
	System.out.print(node.data + " ");
	}
	}
	/* PRIMARY */
	public static void bst_inorder(BST newBST) {
	inorder(newBST.root);
	}
	public static void bst_preorder(BST newBST) {
	preorder(newBST.root);
	}
	public static void bst_postorder(BST newBST) {
	postorder(newBST.root);
	}
	public static void main(String[] args) {
	BST myBST = new BST();
	bst_insert(myBST, 5);
	bst_insert(myBST, 12);
	bst_insert(myBST, 2);
	bst_insert(myBST, 7);
	bst_remove(myBST, 7);
	System.out.println("In-order traversal: ");
	bst_inorder(myBST);
	System.out.println();
	System.out.println("Pre-order traversal: ");
	bst_preorder(myBST);
	System.out.println();
	System.out.println("Post-order traversal: ");
	bst_postorder(myBST);
	System.out.println();
	}
	}

view raw BST.java hosted with ❤ by GitHub

	/**
	* Node Class in BST
	*
	* @author Anggito Anju
	* @version ver 1.0 - 9 June 21
	*/
	public class BSTNode
	{
	int data;
	BSTNode left, right;
	BSTNode(int value) {
	this.data = value;
	this.left = this.right = null;
	}
	}

view raw BSTNode.java hosted with ❤ by GitHub

    Digunakan 2 class pada pengimplementasian pohon biner, seperti source code diatas.

1. Class BST - Digunakan sebagai penunjuk root, sehingga bisa mengakses data lainnya lewat root.
2. Class BSTNode - Digunakan sebagai class untuk setiap 1 node. Class ini digunakan sebagai tempat untuk menyimpan data dan pointer ke node selanjutnya.

    Setelah program dijalankan, didapatkan output sebagai berikut