이진 탐색 트리(Binary Search Tree)개념 및 Java 구현

이진 탐색 트리(Binary Search Tree)

다음과 같은 조건을 충족하는 이진 트리를 이진 탐색 트리라고 한다. 

① 트리의 각 노드들은 반드시 키 값을 가지고 있다. 키 값은 모두 달라야 한다. 

② 노드 N의 왼쪽 서브트리 모든 노드의 키 값은 노드 N의 키 값보다 작아야 한다. 

③ 노드 N의 오른쪽 서브트리 모든 노드의 키 값은 노드 N의 키 값보다 커야 한다.

---

이진 탐색 트리 구현

이진 탐색 트리는 자료 구조 연결리스트를 활용한다. 

 

✅ 준비단계. 노드 클래스 만들기

이진 탐색트리의 개별 노드를 나타내는 클래스이다. 다음과 같이 3개의 필드로 구성된다. 

① Data: 실제 데이터가 들어가는 필드 

② Left: 노드의 왼쪽 서브 트리 

③ Right: 노드의 오른쪽 서브 트리 

 

[Java code]

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

        /* 생성자 */
        public Node(int data) {
            this.setData(data);
            setLeft(null);
            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;
        }
    }

 

1) 탐색 연산 

• 탐색연산에서 중요한 점: 왼쪽 서브트리의 모든 노드의 키 값은 현재 노드의 키 값보다 작다. 
                                       오른쪽 서브트리의 모든 노드의 키 값은 현재 노드의 키 값보다 크다. 

[Java code]

public static Node root;

    BinarySearchTree(){
        root = null;
    }
    
    public static boolean find(int data) {
        Node currentNode = root;
        while (currentNode != null) {
            if (currentNode.data == data) {
                return true;
            }
            
            if (currentNode.data > data) {
                currentNode = currentNode.left;
            }else {
                currentNode = currentNode.right;
            }
        }
        return false;
    }

 

2) 삽입 연산 

• 삽입 연산을 통해 트리를 만든다. 
• ex)
  

[Java code]

/*삽입 연산*/
    public static void insert(int data) {
        Node newNode = new Node(data); // 왼쪽, 오른쪽 자식 노드가 null 이며 data 의 값이 저장된 새 노드 생성
        if(root == null){// 루트 노드가 없을때, 즉 트리가 비어있는 상태일 때,
            root = newNode;
            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 { // 해당 노드보다 작을 때.
                currentNode = currentNode.getRight();
                if(currentNode == null){
                    parentNode.setRight(newNode);
                    return ;
                }
            }
        }
    }

---

전체 코드

package com.algorithm.tree;

public class BinarySearchTree {
    public static void main(String[] args) {
        root = new Node(30);

        insert(20);
        insert(40);
        insert(10);
        insert(25);
        insert(35);
        insert(45);

        preOrder(root);
    }

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

        /* 생성자 */
        public Node(int data) {
            this.setData(data);
            setLeft(null);
            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 Node root;

    BinarySearchTree(){
        root = null;
    }

	/*탐색 연산*/
    public static boolean find(int data) {
        Node currentNode = root;
        while (currentNode != null) {
            if (currentNode.data == data) {
                return true;
            }

            if (currentNode.data > data) {
                currentNode = currentNode.left;
            }else {
                currentNode = currentNode.right;
            }
        }
        return false;
    }

    /*삽입 연산*/
    public static void insert(int data) {
        Node newNode = new Node(data); // 왼쪽, 오른쪽 자식 노드가 null 이며 data 의 값이 저장된 새 노드 생성
        if(root == null){// 루트 노드가 없을때, 즉 트리가 비어있는 상태일 때,
            root = newNode;
            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 { // 해당 노드보다 작을 때.
                currentNode = currentNode.getRight();
                if(currentNode == null){
                    parentNode.setRight(newNode);
                    return ;
                }
            }
        }
    }