Binary Search Tree

Binary Search Tree (BST)

데이터 탐색 알고리즘으로 이진 탐색 알고리즘이 있다. 탐색 범위를 반으로 줄이면서 탐색하는 알고리즘이다. 정렬된 배열에서 이진 탐색 알고리즘을 적용해 O(log N)의 시간복잡도로 탐색할 수 있지만 배열의 원소를 추가, 삭제하는데 O(N)의 시간복잡도가 든다는 단점이 있다. 이를 극복하기 위해 BST를 사용한다. 균형 잡힌 BST(BBST)라면 탐색, 삽입, 삭제의 시간 복잡도를 O(log N)으로 만들 수 있다. 

 

BST는 이진 트리에 속하며 이진 탐색을 목적으로 하는 트리다. BST의 모든 노드는 아래의 규칙을 갖는다.

• 각 노드의 왼쪽 서브 트리에는 해당 노드의 원소보다 작은 원소를 가진 노드들이, 오른쪽 서브 트리에는 해당 노드의 원소보다 큰 원소를 가진 노드들만 존재한다.

BST는 위 규칙을 가지기에 루트 노드부터 탐색을 시작해, 탐색 범위를 반으로 줄이면서 탐색한다. Java에서는 TreeSet와 TreeMap으로 레드 블랙 트리로 구현한 BBST를 제공하고 있다.

이진 탐색 트리

순회

BST를 중위 순회하면 정렬된 원소의 목록을 얻을 수 있다. 왼쪽 서브 트리에는 루트보다 작은 원소를 가진 노드들만 존재하고, 오른쪽 서브 트리에는 루트보다 큰 원소를 가진 노드들만 존재하기 때문이다. 이 점을 이용하면 최대 원소와 최소 원소를 쉽게 얻을 수 있다. 왼쪽 연결을 쭉 내려가면 최소 원소를 얻을 수 있으며, 오른쪽 연결을 쭉 내려가면 최대 원소를 얻을 수 있다.

시간 복잡도

BST의 탐색, 삽입, 삭제의 시간 복잡도는 트리의 높이에 의해 좌우된다. 만약 BST가 한쪽으로 치우친 편향 트리라면 사실상 연결 리스트에서 탐색, 삽입, 삭제하는 것과 다를바 없다. 이 경우 시간 복잡도는 O(N)이 된다. BST가 제 성능을 발휘하려면 좌, 우 서브트리의 높이가 균등한 형태를 가져야 한다. 그래야 트리의 높이를 최대한 낮춰 탐색, 삽입, 삭제 연산을 O(log N)의 시간 복잡도로 수행할 수 있다. 때문에 BST는 그 자체로 잘 안쓰이며 기존 BST에, 트리의 균형을 맟추는 연산을 추가한 BBST가 주로 사용된다. BBST를 사용하면 삽입 순서에 상관없이 트리의 균형을 맟춰준다.

Treap

BBST가 필요할 때, 라이브러리를 쓰면 되지만 k번째 원소의 수 찾는 연산, X보다 작은 원소의 수 계산 등 라이브러리가 제공하지 않는 연산이 필요할 때는 BBST를 직접 구현해야한다. 하지만 시험 중 BBST를 직접 구현하기는 매우 까다롭다. 이때 간단히 구현할만한 트리가 Treap이다.

 

Treap은 임의의 순서로 노드 삽입, 삭제 시 편향 트리가 되는 문제를 막기 위해 고안된 랜덤 이진 검색 트리이다. 기존 BST에 힙의 규칙을 추가하고 우선 순위를 랜덤으로 정한다. 트리 노드가 BST 규칙을 만족하면서 우선 순위에 따라 배치되기 때문에 삽입, 삭제 시 트리의 균형을 맟출 수 있다. (편향 트리가 될 수도 있지만 그 확률은 지극히 낮다.) 트립은 BST와 힙을 합쳐놓았기 때문에 아래 두 가지 규칙을 갖는다.

• BST 규칙 : 각 노드의 왼쪽 서브 트리에는 해당 노드의 원소보다 작은 원소를 가진 노드들이, 오른쪽 서브 트리에는 해당 노드의 원소보다 큰 원소를 가진 노드들만 존재한다.
• 힙 규칙 : 부모 노드의 우선 순위는 자식 노드의 우선 순위보다 크거나 같다.

 

1. 노드 생성

아래와 같이 트립의 노드를 생성할 때 우선 순위를 랜덤으로 정한다. size 변수는 자신을 루트로 하는 서브 트리의 노드 개수를 저장한다. size 변수를 통해 k 번째 원소의 수를 찾거나, X보다 작은 원소의 수를 계산하는 연산을 쉽게 구현할 수 있다. setLeft, setRight로 자식 노드를 만들면 size가 갱신된다.

public class Node {
    int key;
    int priority;
    int size;
    Node left, right;

    Node(int key) {
        this.key = key;
        priority = (int) (Math.random()*100000); // 0 ~ 90000 사이의 난수
        size = 1;
        left = null;
        right = null;
    }

    public void setLeft(Node newLeft) {
        left = newLeft;
        calSize();
    }

    public void setRight(Node newRight) {
        right = newRight;
        calSize();
    }

    private void calSize() {
        size = 1;
        if(left != null) size += left.size;
        if(right != null) size += right.size;
    }
}

 

2. 노드 삽입

root를 루트로 하는 트립에 새 노드 node를 삽입한다고 하자. 이때 root의 우선 순위가 node의 우선 순위보다 높다면 root와 node의 key 값 대소 관계에 따라 node를 왼쪽 서브 트리 또는 오른쪽 서브 트리로 이동시킨다.

 

문제가 되는 건 root의 우선 순위가 새 노드의 우선 순위보다 낮은 경우다. 이때는 node가 root를 밀어내고 이 트리의 루트가 되어야 한다. 이를 구현하기 위해 쪼개기 연산을 구현한다. 쪼개기 연산은 트리를 node의 key 값을 기준으로 두 개의 트리(a, b)로 쪼개는 연산이다. a는 node의 key 값보다 작은 원소들이 있는 트리이며, b는 node의 key 값보다 큰 원소들이 있는 트리이다. root에 쪼개기 연산을 적용한 후 만들어진 a, b를 node의 양쪽 서브 트리로 두면 된다.

class NodePair {
    Node left;
    Node right;
    NodePair(Node left, Node right) {
        this.left = left;
        this.right = right;
    }
}

public class Treap {
    public Node treeRoot;

    private NodePair split(Node root, int key) {
        if(root == null) return new NodePair(null, null);

        if(root.key < key) {
            NodePair nodePair = split(root.right, key);
            root.setRight(nodePair.left);
            return new NodePair(root, nodePair.right);
        }

        NodePair nodePair = split(root.left, key);
        root.setLeft(nodePair.right);
        return new NodePair(nodePair.left, root);
    }

    private Node insert(Node root, Node newNode) {
        if(root == null) return newNode;

        if(root.priority < newNode.priority) {
            NodePair nodePair = split(root, newNode.key);
            newNode.setLeft(nodePair.left);
            newNode.setRight(nodePair.right);
            return newNode;
        }
        else if(newNode.key < root.key) root.setLeft(insert(root.left, newNode));
        else root.setRight(insert(root.right, newNode));
        return root;
    }

    public void insertNode(int key) {
        treeRoot = insert(treeRoot, new Node(key));
    }
}

  

3. 노드 삭제

root를 루트로 하는 트립에 주어진 key와 같은 노드를 삭제한다고 하자. root의 key가 key와 같다면 합치기 연산으로 root의 두 서브트리를 합친 다음, 합쳐진 트리의 루트 노드가 root를 대신한다. 다르다면 root의 key와 key의 대소 관계에 따라 왼쪽 서브 트리 또는 오른쪽 서브 트리를 대상으로 삭제 연산을 수행한다. 합치기 연산은 두개의 트리를 하나의 트리로 합치는 연산이다. 힙 조건을 유지하기 위해 우선 순위에 따라 어느 쪽이 루트가 될지 결정된다는 점을 제외하면 일반적인 합치기 연산과 같다.

public class Treap {
    public Node treeRoot;

    private Node merge(Node a, Node b) {
        if(a == null) return b;
        if(b == null) return a;

        if(a.priority < b.priority) {
            b.setLeft(merge(a, b.left));
            return b;
        }
        a.setRight(merge(a.right, b));
        return a;
    }

    private Node delete(Node root, int key) {
        if(root == null) return root;

        if(root.key == key) return merge(root.left, root.right);
        else if(key < root.key) root.setLeft(delete(root.left, key));
        else root.setRight(delete(root.right, key));
        return root;
    }

    public void deleteNode(int key) {
        treeRoot = delete(treeRoot, key);
    }
}

 

4. k번째 원소 찾기

n개의 노드를 가진 BST에서, k번째 노드를 찾는 연산이다. (1 ≤ k ≤ n) 서브 트리의 크기를 알고 있다면 k번째 노드가 어디에 속해 있는지 쉽게 알 수 있다. 왼쪽 서브 트리의 크기가 l이라고 할때, 다음과 같이 3가지 경우로 나눌 수 있다.

• k ≤ l이면 k번째 노드는 왼쪽 서브 트리에 있으므로 왼쪽 서브 트리로 이동한다.
• k = l이면 root가 k번째 노드이다. 루트를 반환한다.
• k > l이면 k번째 노드는 오른쪽 서브 트리에 있으므로 오른쪽 서브 트리로 이동한다. 이때 k는 오른쪽 서브 트리에서 k - l - 1번째 노드가 된다.

public class Trip {
    public Node treeRoot;

    public Node kth(Node root, int k) {
        int leftSize = 0;
        if(root.left != null) leftSize = root.left.size;

        if(k <= leftSize) return kth(root.left, k);
        else if(k == leftSize + 1) return root;
        return kth(root.right, k - leftSize - 1);
    }
}

 

5. X보다 작은 원소의 수 찾기

n개의 노드를 가진 BST에서, X보다 작은 노드의 개수를 계산하는 연산이다. 서브 트리의 크기를 알고 있다면 이를 쉽게 구현할 수 있다.

public class Treap {
    public Node treeRoot;
    
    int countLessThen(Node root, int x) {
        if(root == null) return 0;
                   
	    if(root.key >= x) return countLessThen(root.left, x);
	    int leftSize = (root.left != null) ? root.left.size : 0;
	    return leftSize + 1 + countLessThen(root.right, x);
    }	
}