이진 탐색 트리 자료구조

이진 탐색 트리(Binary Search Tree)

- 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음

- 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼

- 각각의 서브 트리도 이진 탐색 트리를 유지

- 중복된 키는 허용하지 않음

- 이진 탐색 트리 규칙에 의해 데이터가 정렬됨

- 이진 트리에 비해 탐색 빠름(균형 유지 필요)

- 균형 상태 : O(logN)

- 불균형 상태 : O(N)

 

 

---

이진 탐색 트리 - 탐색

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

대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동

찾는 데이터가 없으면 null 반환

어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어짐

---

 

 

이진 탐색 트리 - 삽입

Root부터 비교 시작(중복 키 발견 시 노드 추가하지 않고 종료)

삽입할 키가 현재 노드의 키보다 작으면 왼쪽으로 이동

삽입할 키가 현재 노드의 키보다 크면 오른쪽으로 이동

Leaf노드에 도달 후 키 비교하여 작으면 왼쪽, 크면 오른쪽에 삽입

---

이진 탐색 트리 - 삭제(1)

삭제 대상 노드가 Leaf 노드인 경우

- 삭제 대상 노드 삭제

- 부모 노드의 해당 자식 링크 null로 변경

 

 

 

이진 탐색 트리 - 삭제(2)

삭제 대상 노드에 자식 노드가 하나 있는 경우

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

- 삭제 대상 노드 삭제

 

 

이진 탐색 트리 - 삭제(3)

삭제 대상 노드에 자식 노드가 둘인 경우

- solution1) 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 선택

- solution2) 삭제 대상 노드의 오른쪽 서브 트리에서 가장 작은 노드 선택

- solution1 또는 2에서 선택한 노드를 삭제 대상 노드 위치로 올림

- 위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업 진행

- 삭제 대상 노드 삭제  

 

---

구현

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int key;
    Node left;
    Node right;

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

데이터 추가

class BinarySearchTree {
    Node head;
    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 {
            Node cur = this.head; // 순회를 하기위한 녀석
            while (true){
                Node pre = cur; // 뒤에서 따라올 녀석
                if(key < cur.key){ // 들어오는 key가 현재 key 보다 작다면
                    cur = cur.left; // 좌측으로 이동!
                    if(cur == null) { // 이동 했는데 null이면 바로 데이터 삽입
                        pre.left = new Node(key,null, null); // pre는 이전의 cur 이였으니 현재위치에서 왼쪽에 추가해주기
                        break;
                    }
                }else {
                    cur = cur.right;
                    if (cur == null){
                        pre.right = new Node(key,null,null); // pre는 이전의 cur 이였으니 현재위치에서 오른쪽에 추가해주기
                        break;
                    }
                }
            }
        }
    }

데이터 제거

 public void removeNode(int key) {
        Node parent = null; // 부모 노드
        Node successor = null; // 제거하려는 대상(왼쪽 or 오른쪽에서 제일 작거나 큰 녀석)
        Node predecessor = null; // 제거하려는 녀석의 부모
        Node child = null; // 제거하려는 녀석의 자식 여부 확인용

        Node cur = this.head;
        while (cur != null){ // 해당 key 값을 가진 node를 찾았을 때 break를 시켜서 cur가 해당 노드를 잡고 있음
            if(key == cur.key){
                break;
            }
            parent = cur;
            if(key < cur.key){
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }

        if(cur == null){
            System.out.println("Can't find key");
            return;
        }

        if(cur.left == null && cur.right == null){ // LeafNode 인 경우
            if(parent == null){ // node가 한 개인 경우
                this.head = null;
            }else {
                if(parent.left == cur){ // 자식 node가 2개인 경우
                    parent.left = null;
                }else {
                    parent.right = null;
                }
            }
        } else if (cur.left != null && cur.right == null || cur.right != null && cur.left == null) { // 자식 node가 하나인 경우
            if(cur.left != null){
                child = cur.left;
            }else {
                child = cur.right;
            }
            if(parent == null){ // 자식 node가 하나 밖에 없는 tree
                this.head = child;
            }else{
                if(parent.left == cur){ // parent의 왼쪽이 삭제 하려고 하는 node라면, 삭제 시키고 해당 노드에 자식을 할당
                    parent.left = child;
                }else{
                    parent.right = child;
                }
            }
        }else { // 자식 node가 둘인 경우
                predecessor = cur;
                successor = cur.left; // 좌측 subTree에서 가장 큰 값을 가르키는 녀석

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