Binary Search Tree - Tugas Struktur Data

Binary search tree merupakan salah satu struktur data dimana sekelompok data memiliki satu buah data yang berada di tingkat paling atas (root). Jika setiap data disebut node, maka setiap node memiliki anak yang disebut dengan child. Pada binary tree, jumlah anak dari masing-masing node maksimal berjumlah 2 buah. Node yang tidak memiliki anak disebut dengan leaf node.

Binary Search Tree (BST) adalah struktur data Binary Tree berbasis node yang memiliki properti berikut:

Subtree kiri dari sebuah node hanya berisi node dengan key lebih kecil dari key node.
Subtree kanan sebuah node hanya berisi node dengan key lebih besar dari key node.
Subtree kiri dan kanan masing-masing juga harus berupa BST.
Data atau key yang disimpan,
Referensi ke node kiri (left), dan
Referensi ke node kanan (right).

Preorder Traversal = Mengunjungi simpul akar (root), Melakukan traversal subpohon kiri (left subtree), Melakukan traversal subpohon kanan (right subtree).
Inorder Traversal = Melakukan traversal subpohon kiri (left subtree), Mengunjungi simpul akar (root), Melakukan traversal subpohon kanan (right subtree).
Postorder Traversal = Melakukan traversal subpohon kiri (left subtree), Melakukan traversal subpohon kanan (right subtree), Mengunjungi simpul akar (root).

	package BST;

	public class BST {

	Node root = null;

	public static Node find(Node 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 Node insert(Node node, int value) {
	if(node == null) {
	Node newNode = new Node(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 Node findMinNode(Node node) {
	Node curr = node;
	while(curr != null && curr.left != null) {
	curr = curr.left;
	}
	return curr;
	}

	public static Node remove(Node 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) {
	Node leftChild = node.left;
	node = null;
	return leftChild;
	}

	// Have right child only
	if(node.left == null) {
	Node rightChild = node.right;
	node = null;
	return rightChild;
	}

	Node 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) {
	Node 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(Node node) {
	if(node != null) {
	inorder(node.left);
	System.out.print(node.data + " ");
	inorder(node.right);
	}
	}

	public static void preorder(Node node) {
	if(node != null) {
	System.out.print(node.data + " ");
	preorder(node.left);
	preorder(node.right);
	}
	}

	public static void postorder(Node 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, 6);
	bst_insert(myBST, 14);
	bst_insert(myBST, 4);
	bst_insert(myBST, 9);

	bst_remove(myBST, 4);

	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();
	}
	}