이진 탐색 트리(Binary Search Tree)

이진 탐색 트리란?

• 저장할 데이터의 크기에 따라 노드의 위치를 정의한 이진 트리
• 효율적인 탐색을 위한 자료 구조

 

이진 탐색 트리의 조건

• 모든 원소는 서로 다른 유일한 키를 갖는다.
• 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다.
• 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다.
• 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리다.

 

이진 탐색 트리

그림 설명

• 루트 8의 왼쪽 자식노드인 3은 루트보다 작다. 오른쪽 자식노드인 10은 루트보다 크다.
• 레벨2에 위치한 부모노드 3의 왼쪽 자식노드인 1은 부모노드보다 작다. 오른쪽 자식 노드인 6은 부모노드보다 크다.

 

이진 탐색 트리 효율성

	이진 탐색 트리	정렬된 배열
검색	O(log N)	O(log N)
삽입	O(log N)	O(N)
삭제	O(log N)	O(N)

 

이진 탐색 트리 구현

public class BinarySearchTreeApp {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insertBST(5);
        bst.insertBST(7);
        bst.insertBST(6);
        bst.insertBST(3);
        bst.insertBST(2);
        bst.insertBST(1);
        bst.insertBST(4);
        bst.insertBST(8);

        System.out.println("PrintBST >>> ");
        bst.printBST();

        System.out.println("SearchBst >>> ");
        Tree_node searchBST1 = bst.searchBST(4);
        if (searchBST1 != null) {
            System.out.println("Searching Success! Searched Key: " + searchBST1.data);
        } else {
            System.out.println("Searching Fail! There is no " + searchBST1.data);
        }
    }
}

class Tree_node {
    int data;
    Tree_node left;
    Tree_node right;

    public Tree_node() {
    }

    public Tree_node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    private Tree_node root = new Tree_node();

    public Tree_node insertKey(Tree_node root, int key) {
        Tree_node p = root;
        Tree_node newNode = new Tree_node(key);

        if (p == null) {
            return newNode;
        } else if (p.data > newNode.data) {
            p.left = insertKey(p.left, key);
            return p;
        } else if (p.data < newNode.data) {
            p.right = insertKey(p.right, key);
            return p;
        } else return p;
    }

    public void insertBST(int key) {
        root = insertKey(root, key);
    }

    public Tree_node searchBST(int key) {
        Tree_node p = root;
        while (p != null) {
            if (p.data > key) {
                p = p.left;
            } else if (p.data < key) {
                p = p.right;
            } else if (p.data == key) {
                return p;
            }
        }
        return p;
    }

    public void inorder(Tree_node root) {
        if (root != null) {
            inorder(root.left);
            System.out.printf(Integer.toString(root.data) + " ");
            inorder(root.right);
        }
    }

    public void printBST() {
        inorder(root);
        System.out.println();
    }
}

 

 

 

학습 교재

자바로 배우는 쉬운 자료구조 - 이지영 지음

누구나 자료구조와 알고리즘 - 제이 웬그로우 지음