Binary Search Tree (BST)

Binary Search Tree

- 각 node에 대해 (left subtree) < node < (right subtree) 의 성질을 만족하는 tree

- in order traversal을 기준으로 정렬된 상태

 

Example

 

Node class

class Node<E>{
    E data;
    Node<E> left, right;

    public Node(E obj) {
        data = obj;
        left = right = null;
    }
}

 

필요하다면 parent pointer 도 만들어 줄 수 있다.

 

 

BST class initialization

public class BST<E>{
    ...

    Node<E> root;
    int currentSize;

    public BinarySearchTree() {
        root = null;
        currentSize = 0;
    }

    ...
}

 

Add method

Add method (public)

public void add(E obj) {
    if (root == null)
        root = new Node<E>(obj);
    else
        add(obj, root);
    currentSize++;
}

 

Recursive add method (private)

void add(E obj, Node<E> node) {
    if (((Comparable<E>)obj).compareTo(node.data) > 0) {
        // go to the right
        if (node.right == null) {
            node.right = new Node<E>(obj);
            return;
        }

        add(obj, node.right);
        return;
    }

    // go to the left
    if (node.left == null) {
        node.left = new Node<E>(obj);
        return;
    }

    add(obj, node.left);
}

 

실제 BST를 사용할 때 호출하는 method는 public add method.

 

하지만, public add method를 호출하면 내부적으로 overloaded recursive add method를 사용해 적절한 위치를 찾아 BST에 추가한다.

 

탐색은 root 부터 시작한다.

 

Contains method

Contains method (public)

public boolean contains(E obj) {
    return contains(obj, root);
}

 

Recursive contains method (private)

boolean contains(E obj, Node<E> node) {
    if (node == null)
        return false;

    if (((Comparable<E>)obj).compareTo(node.data) == 0)
        return true;

    if (((Comparable<E>)obj).compareTo(node.data) > 0)
        return contains(obj, node.right);

    return contains(obj, node.left);
}

 

마찬가지로, 실제 BST를 사용할 때 호출하는 method는 public contains method.

 

null을 만났다는 건 원하는 값을 찾지 못했다는 것이므로 false를 반환한다.

 

 

Delete method

제거하려는 노드를 x라고 하자.

 

크게 2가지 방법이 있다. 

 

아래 설명에서 x가 root 노드인 경우 root pointer에 대한 처리를 해줘야 한다.

 

① delete by copying

1. x가 leaf node 인 경우

- 부모 노드의 x에 대한 pointer가 null을 가리키게 한다.

 

2. x가 자식을 하나만 갖는 경우

- 부모 노드의 x에 대한 pointer가 x의 자식을 가리키게 한다.

 

 

3. x가 자식을 둘 갖는 경우

- x와 x's in order predecessor (혹은 in order successor) 를 swap 한다.

- 바꾼 위치에서 다시 x를 제거한다. 이 때 x는 자식을 0개 또는 1개만 갖게 되므로 delete method를 다시 호출해 쉽게 제거할 수 있다.

참고

- x의 in order predecessor는 in order traversal에서 x 직전에 방문하는 노드를 의미한다.

- 다른 말로, x의 left subtree에서 오른쪽으로만 갔을 때 마지막으로 나오는 노드를 의미한다.

- 특히, BST에서는 x보다 값이 작거나 같으면서 가장 값이 큰 노드를 의미한다. 

 

② delete by merging

- x의 right subtree를 in order predecessor의 오른쪽에 붙여준다.

- x를 지우고 그 자리에 x의 left subtree를 위치시킨다.  

 

- 물론, left subtree가 없는 상황도 따로 생각해줘야 한다.