이진 탐색 트리

1. 개념정리

1) 트리: 값을 가진 노드(node)가 엣지(edge)로 연결되어 있는 구조

- 상위 노드를 부모, 하위 노드를 자식이라 부른다.

- 최상위 노드는 루트(root)라고 부른다.

- 부모 노드에 자식 노드가 0~n개 연결되어 있는 구조

 

2) 이진 트리(binary tree): 자식 노드가 최대 2개인 트리

 

3) 이진 탐색 트리(binary search tree): 부모의 왼쪽에는 부모의 값보다 작거나 같은 값을 가진 노드가, 오른쪽에는 크거나 같은 값은 가진 노드가 있는 트리

 

2. 구현 코드

class Node{ // 정수 값을 담는 노드
    protected Node left;
    protected Node right;
    protected int value;

    Node(int value){
        this.value = value;
        left = null;
        right = null;
    }
}

class BinarySearchTree{ // 노드들이 연결된 이진 탐색 트리
    private Node root;  // 이진 탐색 트리의 루트
    private int size;   // 이진 탐색 트리에 저장된 노드의 개수
	
    BinarySearchTree(){
        root = null;
        size = 0;
    }
	
    void add(int value) { // 메인에서 사용할 추가 함수
        root = addRecursive(root, value);
        size++;
    }

    private Node addRecursive(Node current, int value) { // 내부에서만 사용 가능한 추가 함수
        if(current==null)
            current = new Node(value);
        else if(value<current.value)
            current.left = addRecursive(current.left, value);
        else
            current.right = addRecursive(current.right, value);
        return current;
    }
	
    boolean contains(int value) { // value가 트리에 있으면 true 반환
        return containsRecursive(root, value);
    }
	
    private boolean containsRecursive(Node current, int value) {
        boolean answer;
        if(current==null)
            answer = false;
        else if(value==current.value)
            answer = true;
        else
            answer = value<current.value ? containsRecursive(current.left, value) : containsRecursive(current.right, value);
        return answer;
    }
	
    void remove(int value) { // 메인에서 사용할 삭제 함수
        root = removeRecursive(root, value);
        size--;
    }

    private Node removeRecursive(Node current, int value) { // 내부에서만 사용 가능한 삭제 함수
        if(current!=null) {
            if(value==current.value){
                if(current.left==null && current.right==null)
                    current = null;
                else if(current.right==null)
                    current = current.left;
                else
                    current = current.right;
            }
            else if(value<current.value)
                current.left = removeRecursive(current.left, value);
            else
                current.right = removeRecursive(current.right, value);
        }
        return current;
    }
	
    void preorder() { // depth first search, 전위 순회
        preorderRecursive(this.root);
    }
	
    void preorderRecursive(Node o) {
        if(o != null) {
            System.out.print(o.value + " ");
            preorderRecursive(o.left);
            preorderRecursive(o.right);
        }
    }
	
    void inorder() { // depth first search, 중위 순회, 오름차순 출력
        inorderRecursive(this.root);
    }

    void inorderRecursive(Node o) {
        if(o != null) {
            inorderRecursive(o.left);
            System.out.print(o.value + " ");
            inorderRecursive(o.right);
        }
    }
	
    void postorder() { // depth first search, 후위 순회
        postorderRecursive(this.root);
    }
	
    void postorderRecursive(Node o) {
        if(o != null) {
            postorderRecursive(o.left);
            postorderRecursive(o.right);
            System.out.print(o.value + " ");			
        }
    }
	
    void levelorder() { // breadth first search, 레벨 순회
        if(root!=null) {
            Queue<Node> nodes = new LinkedList<>();
            nodes.add(root);
            while(!nodes.isEmpty()) {
                Node o = nodes.remove();
                System.out.print(o.value + " ");
                if(o.left!=null)
                    nodes.add(o.left);
                if(o.right!=null)
                    nodes.add(o.right);
            }
        }
    }
    	
    int size() { return size; } // 트리에 저장된 노드의 개수 반환
	
    boolean isEmpty() { return size==0; } // 빈 트리라면 true 반환
	
    void clear() { root = null; size = 0;} // 트리 초기화
                          // 남은 노드들은 가비지 컬렉터(garbage collector)에 의해 정리됨
}

 

3. 예제 코드

// 정수 값에 대한 이진 탐색트리를 다룰 것이며,
// 중복 값을 더하거나 없는 값을 제거하는 일은 없다고 가정한다.
    	
// 1) 생성
BinarySearchTree bst = new BinarySearchTree();
    	
// 2) 추가
bst.add(4); bst.add(8); bst.add(5); bst.add(3);
bst.add(6); bst.add(1); bst.add(2); bst.add(9);
System.out.println(bst.size()); // 8

bst에 8개의 노드가 모두 추가된 상태

// 3) 탐색
bst.levelorder(); // 4 3 8 1 5 9 2 6

bst.inorder(); // 1 2 3 4 5 6 8 9

bst.preorder(); // 4 3 1 2 8 5 6 9

bst.postorder(); // 2 1 3 6 5 9 8 4 

System.out.println(bst.contains(5)); // true
System.out.println(bst.contains(10)); // false
    	
// 4) 삭제
bst.remove(5);
bst.levelorder(); // 4 3 8 1 6 9 2 

bst.clear();
System.out.println(bst.isEmpty()); // true

bst.remove(5)를 수행한 후의 트리

---

[iterative로 구현한 pre/in/post-order]

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.add(p.val);  // Add before going to children
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            p = node.right;   
        }
    }
    return result;
}

static List<Integer> inorder(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode c = root;
    while(!stack.isEmpty() || c!=null) {
        if(c != null) {
            stack.push(c);
            c = c.left;
        } else {
            TreeNode node = stack.pop();
            ans.add(node.val);
            c = node.right;   
        }
    }
    return ans;
}

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.addFirst(p.val);  // Reverse the process of preorder
            p = p.right;             // Reverse the process of preorder
        } else {
            TreeNode node = stack.pop();
            p = node.left;           // Reverse the process of preorder
        }
    }
    return result;
}