[자료구조] BST(Binary Search Tree)

BST(Binary Search Tree)

• 트리 구조는 편리한 구조를 전시하는것 외에 효율 적인 탐색을 위해서도 사용한다.
• 효율 적인 탐색을 위한 트리 구조중 가장 대표적인 트리는, 이진 트리(binary tree)와 이진 탐색 트리(binary search tree)

이진 트리(binary tree)

• 자식 노드가 최대 2개인 트리
• 왼쪽 자식노드와 오른쪽 자식노드를 가진다. 
• 정 이진 트리, 포화 이진 트리, 완전 이진 트리로 나뉜다.

정 이진 트리

• 각 노드가 0개 or 2개의 자식 노드만 가진다.

완전 이진 트리

• 마지막 레벨을 제외한 모든 노드가 가득 차야하고 마지막 레벨 노드는 전부 차있지 않아도 되지만 왼쪽 노드는 차있어야 한다.

포화 이진 트리

• 모든 리프 노드의 레벨이 동일하고 , 모든 레벨이 가득 차 있는 이진 트리

 

이진 탐색 트리(binary search tree)

• 모든 왼쪽의 값이 부모나 root보다 작고, 모든 오른쪽의 값이 부모나 root보다 큰 값을 가진다.
• 이진 탐색트리는 입력되는 값의 순서의 따라 한쪽으로 노드들이 몰릴수가 있다.
  • 노드 균형이 잡히지 않으면 탐색 시간이 늘어 날 수 있고, 이를 해결하기위해 삽입과 삭제시 트리를 재구성하는 알고리즘을 추가 할 수 있다. 

 

이진 탐색 트리(binary search tree)를 JAVA로 구현

import java.util.*;

public static class Node {
    private int data;
    private Node left;
    private Node right;

    /* 생성자 */
    public Node(int data) {
        this.setData(data);
        this.setLeft(null);
        this.setRight(null);
    }

    public int getData() {
        return data;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

    public void setData(int data) {
        this.data = data;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

//이진 탐색 트리의 클래스
public static class binarySearchTree {
    public Node root;

    public binarySearchTree(){
        root = null;
    }

    // tree에 value를 추가합니다.
    public void insert(int data) {
        Node newNode = new Node(data); // 왼쪽, 오른쪽 자식 노드가 null 이며 data 의 값이 저장된 새 노드 생성
        if (root == null) {// 루트 노드가 없을때, 즉 트리가 비어있는 상태일 때,
            root = newNode;
            return;
        }
        if(root.data == data) return;   //중복일때 정지

        Node currentNode = root;
        Node parentNode = null;

        while (true) {
            parentNode = currentNode;

            if (data < currentNode.getData()) { // 해당 노드보다 작을 경우
                currentNode = currentNode.getLeft();
                if (currentNode == null) {
                    parentNode.setLeft(newNode);
                    return;
                }else if(currentNode.data == newNode.data) return;
            } else { // 해당 노드보다 클 경우
                currentNode = currentNode.getRight();
                if (currentNode == null) {
                    parentNode.setRight(newNode);
                    return;
                }else if(currentNode.data == newNode.data) return;
            }
        }
    }

    // tree의 value값을 탐색
    public boolean contains(int data) {
        Node currentNode = root;
        while (currentNode != null) {
            // 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
            if (currentNode.data == data) {
                return true;
            }

            if (currentNode.data > data) {
                // 찾는 value값이 노드의 value 보다 작다면, 현재 노드를 left로 변경후 다시 반복합니다.
                currentNode = currentNode.left;
            }else {
                // 찾는 value값이 노드의 value 보다 크다면, 현재 노드를 right로 변경후 다시 반복합니다.
                currentNode = currentNode.right;
            }
        }
        return false;
    }