[자료구조] 이진 탐색 트리(Binary Search Tree) 구현

이진 탐색 트리

이진 탐색 트리는

노드의 왼쪽 하위 트리엔 노드 값보다 작은 노드들만 있다.

노드의 오른쪽 하위 트리엔 노드 값보다 큰 값들만 있다.

=> 즉 데이터를 삽입할 때 거치는 노드보다 작으면 왼쪽, 크면 오른쪽으로 간다는 뜻이다.

---

Node

public class Node implements TreePrinter.PrintableNode{
    private int data;
    private Node leftNode;
    private Node rightNode;

// 생성자. 노드 생성 시 오른쪽, 왼쪽 노드 비어있게.
    public Node(int data) {
        this.data = data;
        this.leftNode = null;
        this.rightNode = null;
    }

    @Override
    public TreePrinter.PrintableNode getLeft() {
        return leftNode;
    }

    @Override
    public TreePrinter.PrintableNode getRight() {
        return rightNode;
    }

    @Override
    public String getText() {
        return "["+data+"]";
    }
 	//... Getter, Setter 생략...   
}

Node 클래스이다.

Node는 데이터와 해당 노드의 왼쪽 자식, 오른쪽 자식으로 구성되어있다.

Node의 생성자는 데이터를 받아 생성하며 노드 생성 시에는 해당 노드의 왼쪽 자식, 오른쪽 자식은 비어있게 Null로 설정하였다.

 

BST - insert() 메소드

public class Bst {
    private Node root;
// 숫자 하나 전달받아서 데이터를 추가하는 기능
    public void insert(int data) {
        Node newNode = new Node(data);
        if (root == null) {
            root = newNode;
        }
        else {
            Node current = root;
            while (current != null) {
                if (current.getData() > data) {
                    if(current.getLeftNode() == null){
                        current.setLeftNode(newNode);
                        break;
                    } else {
                        current = current.getLeftNode();
                    }
                } else {
                    if(current.getRightNode() == null){
                        current.setRightNode(newNode);
                        break;
                    } else {
                        current = current.getRightNode();
                    }
                }
            }
        }
    }
}

노드를 삽입할 때는 삽입할 노드의 데이터를 전달받아서 노드를 생성한다.

root == null 즉 아무 노드도 생성되어있지 않은 상태이면 root에 노드를 삽입한다.

그렇지 않으면 (노드가 하나라도 생성되어있다면) root부터 값을 비교하며 해당 노드보다 삽입할 노드의 값이 작으면 왼쪽 크면 오른쪽으로 반복을 진행하며 끝에다가 노드를 삽입한다.

BST - delete() 메소드

public class Bst {
    private Node root;
    public void delete(int data) {
            Node parentNode = null;
            Node deleteNode = root;
            // 삭제할 노드를 찾고, 삭제할 노드의 부모 노드 찾기
            while(deleteNode.getData() != data) {
                parentNode = deleteNode;
                if(deleteNode.getData() > data) {
                    deleteNode = deleteNode.getLeftNode();
                }  else{
                    deleteNode = deleteNode.getRightNode();
                }
                //
            }
            // 삭제할 노드의 왼쪽 = 비어있음, 오른쪽 = 비어있음
            if (deleteNode.getLeftNode() == null && deleteNode.getRightNode() == null) {
                if (deleteNode.getData() > parentNode.getData()){
                    parentNode.setRightNode(null);
                } else {
                    parentNode.setLeftNode(null);
                }
            }
            // 삭제할 노드의 왼쪽 = 안 비어있음, 오른쪽 = 비어있음
            else if (deleteNode.getLeftNode() != null && deleteNode.getRightNode() == null) {
                if (deleteNode.getData() > parentNode.getData()){
                    parentNode.setRightNode(deleteNode.getLeftNode());
                } else {
                    parentNode.setLeftNode(deleteNode.getLeftNode());
                }
                deleteNode.setLeftNode(null);
            }
            // 삭제할 노드의 왼쪽 = 비어있음, 오른쪽 = 안 비어있음
            else if (deleteNode.getLeftNode() == null && deleteNode.getRightNode() != null) {
                if (deleteNode.getData() > parentNode.getData()){
                    parentNode.setRightNode(deleteNode.getRightNode());
                } else {
                    parentNode.setLeftNode(deleteNode.getRightNode());
                }
                deleteNode.setRightNode(null);
            }
            // 삭제할 노드가 자식을 둘 다 가지고 있을 때
            else {
                Node maximumParents;
                maximumParents = deleteNode;
                // 왼쪽 서브트리 중 가장 큰 값을 저장할 maximum 변수
                Node maximum;
                maximum = deleteNode.getLeftNode();

                // 왼쪽 서브트리 중 가장 큰 값(오른쪽 자식 노드가 없는 것)을 저장하는 과정
                while (maximum.getRightNode() != null) {
                    maximumParents = maximum;
                    maximum = maximum.getRightNode();
                }

                // 왼쪽 서브트리 구조 조정
                if(maximumParents != deleteNode){
                    maximumParents.setRightNode(maximum.getLeftNode());
                }
                if(deleteNode.getLeftNode() != maximum){
                    maximum.setLeftNode(deleteNode.getLeftNode());
                }
                maximum.setRightNode(deleteNode.getRightNode());


                if(parentNode == null){
                    root = maximum;
                } else {
                    if(deleteNode.getData() > parentNode.getData()){
                        parentNode.setRightNode(maximum);
                    }
                    if (deleteNode.getData() < parentNode.getData()){
                        parentNode.setLeftNode(maximum);
                    }
                }
            }
        }
}

delete 메소드는 삭제하고 싶은 노드가 자식이 없는 경우, 왼쪽 자식만 존재하는 경우, 오른쪽 자식이 존재하는 경우, 왼쪽/오른쪽 자식이 둘 다 존재하는 경우에 따라 삭제를 진행할 수 있도록 하였다.

위의 삭제 방식에서 어려운 부분은 삭제되는 노드가 두 개의 자식을 가질 때, 해당 노드를 대체하기 위해 왼쪽 서브트리의 가장 큰 값을 찾는 방식으로 구현하였다.