[비선형 자료구조] - 이진 탐색 트리의 특징, 삽입, 삭제, 검색 과정

앞서 트리에 대한 기본 특징은 여기서 참고 

이진 트리는 트리 중에서도 최대 2개의 노드까지 가질 수 있는 트리이다. 

🔎  이진 탐색 트리란?

▪ 크기 순으로 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드로 작성된 트리

▪ 모든 트리의 구성은 위와 같은 규칙을 지키고 있으며, 중복된 키는 허용하지 않는다.  - 검색 목적의 자료구조이기 떄문

▪ 이진 탐색 트리를 순회할 경우, 중위순회 방법 사용 시, 정렬된 데이터를 얻을 수 있다. 

▪ 정렬되어 있다는 특징 때문에 균형이 유지되어 있을 경우, 이진 트리에 비해 탐색이 빠르다.

      ▪ 균형 상태 : O(logN)

      ▪ 불균형 상태 : O(N)

* 이진 트리 : 규칙이 없이, 정렬되지 않은채 저장된 트리

 

🤔 이진 탐색 트리는 왜 쓰는 걸까. ❓

☑ 탐색 속도 향상을 위해.  "이진 탐색"을 하면 시간복잡도면에서 효율이 높아서. (그러나 한쪽으로 치우쳐진 사향 트리에서는 O(N) 시간복잡도를 갖기 때문에 다른 자료구조를 써야 한다. 

☑ 이진 탐색 배열에 비해 삽입과 삭제가 용이하기 때문

 

🔎 이진 탐색 트리 - 검색 과정

타겟 데이터를 찾는 과정

 

▪ 찾고자 하는 데이터를 루트 노드부터 비교를 시작한다. 

▪ 대소 비교를 하여, 찾는 데이터가 현재 노드보다 작으면 왼쪽으로 이동, 크면 오른쪽 노드로 이동하는 과정을 타겟 노드를 찾을 때까지 반복한다.

▪ 최종 순회 후에도 찾는 데이터가 없으면 null을 반환한다. 

▪ 최대 탐색 횟수 : 어떠한 데이터를 찾더라도, 트리의 높이만큼만 최대로 탐색이 이루어진다. 

ex. 포화이진 탐색 트리의 노드 개수가 N개일 때, 트리의 높이 h와의 관계는 

N = 2^(h + 1) - 1

트리의 높이 h에 대해 정리하면, 

h = log2(N + 1) - 1

따라서 O(logN)이라는 시간복잡도를 갖게 된다. 

 

 

🔎 이진 탐색 트리 - 삽입 과정

원하는 데이터를 추가는 과정

 

▪ 루트 노트부터 비교를 시작한다. (이떄 중복된 키가 발견될 경우, 추가하지 않고 종료한다.)

▪ 대소 비교를 하여, 삽입할 데이터가 현재 노드보다 작으면 왼쪽으로 이동, 크면 오른쪽 노드로 이동하는 과정을 리프노드에 도달할 때까지 반복한다.

▪ 리프 노드 도달 후에 키를 비교해서, 리프 노드보다 작으면 왼쪽에, 크면 오른쪽에 삽입한다.  

 

 

🔎 이진 탐색 트리 - 삭제 과정

타겟 데이터를 삭제하는 과정으로, 케이스에 따라 방법이 조금씩 다르다. 

☑ case 1. 삭제 대상 노드가 Leaf 노드인 경우

▪ Leaf 노드이기 떄문에 연결된 노드가 부모  노드 밖에 없다.

➡️ 삭제 대상 노드 자체를 삭제

➡️ 삭제 대상 노드의 부모 노드에서, 해당 자식 노드 부분을 null로 변경 

 

☑ case 2. 삭제 대상 노드에 자식 노드가 1개 있는 경우

▪ 자식노드가 1개일 경우, 추가적인 비교 없이 부모 노드와 연결 후 삭제를 해주면 된다.

➡️ 삭제 대상 노드의 자식 노드를 삭제 대상 노드의 부모 노드에 연결

➡️ 삭제 대상 노드를 삭제

 

☑ case 3. 삭제 대상 노드에 자식 노드가 2개 있는 경우

▪ 둘 중 어느 노드를 삭제 노드 위치에 놓을지 정해야 하고, 이는 둘 중 어느 것이든 상관 X (방법은 유사)

➡️ 정하는 경우

      1. 삭제 대상 노드의 왼쪽 서브 트리(왼쪽 자식 노드에 노드가 더 붙어 있는 경우 고려)에서 가장 큰 노드를 선택해서 올리는 경우

      2. 삭제 대상 노드의 오른쪽 서브 트리(왼쪽 자식 노드에 노드가 더 붙어 있는 경우 고려)에서 가장 큰 노드를 선택해서 올리는 경우

➡️ 정한 노드를 삭제 대상 노드의 위치로 올림

➡️ 위로 올리면서 원래 삭제 노드가 갖고 있던 다른 자식 노드들과 연결 작업 진행 + 빈 곳 null 처

➡️ 삭제 대상 노드 삭제

 

🔎 이진 탐색 트리 구현 (코드)

▪ 트리는 노드와 링크로 구현되어 있다.

☑ 작성 시 기억할 것 : 노드에는 부모노드, 루트 노드, 왼쪽 자식 노드, 오른쪽 자식 노드가 있을 수 있고, 이들을 꼭 고려하면서 구현하자. 

 

➡️ 노드 구현

▪ 이진 탐색 트리의 노드에는 키 값과 왼쪽, 오른쪽 자식 노드 정보를 담고 있다. 

class Node {
    int key;
    Node left;
    Node right;
    
    Node(int key, Node left, Node right) {
    	this.key = key;
        this.left = left;
        this.right = right;
    }
}

 

➡️ 삽입, 삭제, 탐색 기능을 담은 BinarySearchTree 구현

▪ BinarySearchTree의 기본 구조 틀 : 루트 노드를 가리키는 head, 생성자, 각 기능별 메서드

      ▪ 루트 노드 

Node head;

 

      ▪ BinarySearchTree 생성자

BinarySearchTree(int key) {
	// 새 노드 생성 및 초기화
	this.head = new Node(key, null, null);
}

 

      ▪ 각 기능별 메서드 : 앞서 언급된 과정을 바탕으로 코드로 작성해본다.

🔎 삽입

    public void addNode(int key) {
        if(this.head == null) {	// 빈 트리인 경우
            this.head = new Node(key, null, null);
        } else {
            // head가 있을 경우, leaf 노드까지 찾아가서 삽입해줘야 한다.
            Node cur = this.head;
            // 빈 자리가 나올 때까지 조건에 맞춰 이동하는 것!
            while (true) {
                Node pre = cur; // pre가 필요한 이유 : cur가 null로 발견되면 (빈 자리가 발견되면) 그 이전의 자식노드에 연결해줘야 함.

                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;
                    }
                }
            }
        }
    }

 

🔎 탐색

        // 타켓 노드 찾기
        if(cur == null) {return;}

        while(true) {
            if(cur.key == key) break;

            pre = cur;
            if(cur.key < key) cur = cur.right;
            else cur = cur.left;
        }

 

🔎 삭제 1.  삭제 대상이 leaf 노드인 경우  (타겟 노드를 찾은 후의 과정)

        // case 1. leaf 노드일 경우
        if(cur.left == null && cur.right == null) {
            // 노드가 1개 밖에 없던 경우
            if(pre == cur) {
                this.head = null;
            } else {
                if(pre.left == cur) pre.left = null;
                else pre.right = null;
         }

 

🔎 삭제 2.  삭제 대상의 자식 노드가 1개인 경우

        // case 2. 삭제 노드에 자식 노드가 1개 있는 경우
        } else if (cur.left != null && cur.right == null || cur.left == null && cur.right != null) {
            // 좌우 자식 유무 찾는 과정 중복을 없애기 위해 child를 미리 탐색
            Node3 child = null;
            if(cur.left != null) child = cur.left;
            else child = cur.right;

            // 삭제 대상이 루트 노드일 경우
            if(pre == cur) this.head = child;
            else {
                if(pre.left == cur) {
                    pre.left = child;
                } else {
                    pre.right = child;
                }
            }
       }

🔎 삭제 3.  삭제 대상의 자식 노드가 2개인 경우

// case 3. 삭제 노드에 자식 노드가 2개 있는 경우
        } else {
            // 좌측 최대값으로 대체 하기로 한 경우
            Node3 leftMaxPar = cur;
            Node3 leftMax = cur.left;

            while(leftMax.right != null) {
                leftMaxPar = leftMax;
                leftMax = leftMax.right;
            }

            // leftMax.right가 null인 노드의 나머지 left부분을 leftMaxPar와 연결(null이여도 상관 X)
            leftMaxPar.right = leftMax.left;

            // leftMax를 삭제 대상 노드위치에 놓기
            leftMax.left = cur.left;
            leftMax.right = cur.right;

            // 부모 파트 연결
            if(pre == cur) {
                this.head = leftMax;
            } else {
                if(pre.left == cur) {
                    pre.left = leftMax;
                } else {
                    pre.right = leftMax;
                }
            }
        }