[Data Structure (Java)] Tree (3) - Binary Search Tree

https://crane206265.tistory.com/82

[Data Structure (Java)] Tree (2) - Tree Traversal Algorithms

BST를 해봅시다. Tree 글은 이걸로 끝일거 같긴 한데, 사실 그렇다고 말하기도 애매한게 앞으로 다룰 내용이 전부 트리 바탕이긴 합니다.

---

Binary Search Tree (BST)

: binary tree s.t. satisfiy below 2 conditions

(1) elements in the left subtree : less than root of subtree

(2) elements in the right subtree : greater than root of subtree

---

Tree API

API of Tree<E>

methods	explanation
boolean isEmpty()	return if tree is empty
int getSize()	return the # of nodes of the tree
boolean search(E e)	return if the element E e exists
void insert(E e)	insert the element E e
void inorder()	excute and print inorder traversal
void preorder()	excute and print preorder traversal
void postorder()	excute and print postorder traversal

 

search a element : compare with node a few times (algorithm of binary search)

- if less -> go left

- if greater -> go right

- if equal : search hit

* running time : proportional to the height of the tree

 

insert : same process of search -> if null : insert

 

inorder traversal in BST : ascending order of keys

 

* BST class : reference to a rood Node

---

before implementation

public class BST<E extends Comparable<E>> implements Tree<E> {
	...
}

--> generic type E must be comparable -> "bounded type parameter"
* java initially provides java.lang.Comparable interface for String -> includes a single method compareTo()

Comparable Interface
: based on the natural ordering
- standard order for natural/real numbers
- alphabetical order for strings

v.compareTo(w)

: return integer
- v is less than w : return negative
- v equals to w : return 0
- v is greater than w : return positive

---

BST implementation

tree implementation : linked list + recursion

public class BST<E extends Comparable<E>> implements Tree<E> {
	//----- Nested Node Class -----
	private static class Node<E> {
    	private E element;
        private Node<E> left;
        private Node<E> right;
        private int n; //# of nodes in its subtree (include itself)
        
        public Node(E e, int n) {
        	element = e;
            this.n = n; //why use 'this'? : to distinguish instance var n and parameter n 
            // left & right : initialized to null
        }
    }
    
    //----- Construct BST Class -----
    private Node<E> root;
    
    public BST() {} //construct empty BST
    
    public BST(E[] objects) {
    	for(i = 0; i < objects.length; i++) {
        	insert(objects[i]);
        }
    } //construct BST with array
    
    //----- Methods Implementation -----
    public int getSize() {
    	getSize(root);
    }
    
    private int getSize(Node<E> x) {
    	if(x == null) return 0;
    	else return x.n;
    }
    
    public boolean isEmpty() {
    	return getSize() == 0;
    }
    
    public boolean search(E e) {
    	Node<E> current = root;
        while(current != null) {
            int cmp = e.compareTo(current.element);
            if(cmp == 0)
            	return true;
            else if(cmp > 0)
            	current = current.right;
            else if(cmp < 0)
            	current = current.left;
        }
        return false;
    }
    
    public void insert(E e) {
    	root = insert(root, e);
    }
    
    private Node insert(Node<E> x, E e) {
    	if(x == null)
        	return new Node(e, 1);
    	int cmp = e.compareTo(x.element);
        if(cmp > 0)
        	x.right = insert(x.right, e);
        else if(cmp < 0)
        	x.left = insert(x.left, e);
        x.n = 1 + getSize(x.left) + getSize(x.right);
        return x;
    }
    
    public void inorder() {
    	inorder(root);
    }
    
    private void inorder(Node<E> x) {
    	if(x == null) return;
        inorder(x.left);
        System.out.print(x.element + " ");
        inorder(x.right);
    }
    
    public void preorder() {
    	preorder(root);
    }
    
    private void preorder(Node<E> x) {
    	if(x == null) return;
        System.out.print(x.element + " ");
        preorder(x.left);
        preorder(x.right);
    }
    
    public void postorder() {
    	postorder(root);
    }
    
    private void postorder(Node<E> x) {
    	if(x == null) return;
        postorder(x.left);
        postorder(x.right);
        System.out.print(x.element + " ");
    }
}