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

꾸준히·2023년 3월 4일

Java 자료구조

📌 이진탐색트리(Binary Search Tree) 란?

이진 트리의 일종으로, 데이터가 위치하는 규칙이 추가된 트리이다.
부모 노드 보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽에 위치하도록 한다.
규칙에 따라 데이터가 위치해 있으므로, 데이터가 삽입되면 정렬된 상태로 위치하게 된다. 그러므로 데이터의 탐색이 빠르다.
- 균형 상태에서는 O(logN)
- 어떤 데이터를 찾더라도, 최대 트리 높이 만큼의 탐색이 이루어진다.

📌 데이터 추가, 삭제

데이터 추가

루트 노드 부터 대소 비교로 데이터 저장 위치를 정한다.
추가된 데이터는 리프 노드의 아래 자식노드로 추가된다.

데이터 삭제

루트 노드 부터 대소 비교로 데이터 저장 위치를 정한다.
데이터 삭제의 로직은 두가지 경우의 수가 존재한다.
- 자식 노드가 하나일 경우
- 자식 노드가 둘 이상일 경우

자식 노드가 하나인 데이터의 삭제

해당 데이터(14번)를 삭제하고
자식 노드(13번)와 부모 노드(10번)를 연결시킨다.

자식 노드가 둘 이상인 데이터의 삭제

1. 삭제할 노드(8)의 왼쪽 서브 트리에서 가장 큰 노드(7) 선택
2. 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 노드 선택

1 or 2 에서 선택한 노드(7)를 삭제할 노드(8)의 위치로 옮겨 놓는다.
삭제할 대상과 연결되어 있던 링크(3, 10)를 옮겨진 링크와 연결시킴

📌 자바 코드 구현

노드 클래스

class Node {
    public int key;		// 노드의 값
    public Node left; 	// 왼쪽 자식 노드
    public Node right;	// 오른쪽 자식 노드

    Node(int key) {
        this.key = key;
    }
}

BinaryTree 클래스

class BinarySearchTree {
    Node head;  // 루트

    BinarySearchTree(int key) {
        head = new Node(key);
    }
}

데이터 추가

class BinarySearchTree {
    Node head;  // 루트

    BinarySearchTree(int key) {
        head = new Node(key);
    }

    public void addNode(int key) {
        if (head == null) {
            head = new Node(key, null, null);
            return;
        }

        Node cur = head;

        while (true) {
            Node pre = cur;

            if (key < cur.key) {
                cur = cur.left;
                if (cur == null) {  // 리프노드
                    pre.left = new Node(key, null, null);
                    break;
                }
            } else {
                cur = cur.right;
                if (cur == null) {  // 리프노드
                    pre.right = new Node(key, null, null);
                    break;
                }
            }
        }
    }
}

데이터 삭제

위 BinaryTree 클래스 내부에 포함됩니다.

public void removeNode(int key) {   // 삭제 하려는 값
        // 임시 변수들
        Node parent = null;
        Node successor = null;
        Node predecessor = null;
        Node child = null;

        // 삭제하려는 값 찾기
        Node cur = this.head;
        while (cur != null) {
            if (key == cur.key) {
                break;
            }

            parent = cur;       // 부모노드 저장해 두기
            if (key < cur.key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }

        if (cur == null) {
            System.out.println("key에 해당하는 노드가 없습니다.");
            return;
        }

        // 리프 노드인 경우
        if (cur.left == null && cur.right == null) { 
            if (parent == null) {   // 노드가 하나밖에 없는 경우
                this.head = null;
            } else {
                if (cur == parent.left) {
                    parent.left = null;  // 삭제
                } else {
                    parent.right = null;
                }
            }
            // 자식 노드가 하나인 경우
        }  else if (cur.left != null && cur.right == null || cur.left == null && cur.right != null) {
            if (cur.left != null) {
                child = cur.left;
            } else {
                child = cur.right;
            }

            if (parent == null) {   // 노드가 하나밖에 없는 경우
                this.head = child;
            } else {
                if (parent.left == cur) {
                    parent.left = child;    // 왼쪽 삭제
                } else {
                    parent.right = child;
                }
            }
            // 자식 노드가 둘인 경우
        } else {
            predecessor = cur;      // successor 부모
            successor = cur.left;   // 좌측 서브트리에서 가장 큰 노드 저쟝용

            while (successor.right != null) {
                predecessor = successor;
                successor = successor.right;
            }

            predecessor.right = successor.left; // **
            successor.left = cur.left;
            successor.right = cur.right;

            if (parent == null) {
                this.head = successor;
            } else {
                if (parent.left == cur) {
                    parent.left = successor;
                } else {
                    parent.right = successor;
                }
            }

        }
    }