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

목차

트리 (Tree)

비-선형 자료 구조 (Non-Linear)

• 선형 자료 구조: 구조에 저장될 데이터들이 순차적으로 저장되는 형태
  • ArrayList, LinkedList, Map, Stack, Queue 등
• 비-선형 자료 구조: 복수의 데이터들이 복수의 데이터들과 연결될 수 있는 구조
  • Tree

검색 트리

내장 vs 외장 검색 트리

• 내장 검색 트리: 메인 메모리 내에 존재
• 외장 검색 트리: 검색 트리가 외부(주로 디스크)에 존재-검색 트리 전체를 메인 메모리에 올려놓고 쓸 수 없는 경우

이진 검색 트리(Binary Search Tree)

특성

1. 각 노드는 키값을 하나씩 갖는다. 이 키값은 모두 다르다.
2. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 갖는다.
3. 임의 노드의 키값은 자기 왼쪽 아래에 있는 모든 노드의 키값보다 크고, 오른쪽 아래에 있는 모든 노드의 키값보다 작다.
4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.

노드 객체의 구조

• item: 키 저장
• right: 오른쪽 자식
• left: 왼쪽 자식

public class Node {
    int item;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

이진 탐색 트리 알고리즘

검색

1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행한다.
4. 검색에 실패하면 null을 return

삽입

1. 원소를 삽입할 자리 찾기 (실패하는 검색 1회)
2. 임의의 리프 노드에서 더 이상 내려갈 곳이 없다는 것을 확인 → x를 그 리프 노드의 자식으로 매단다

 

 

구조적으로 검색 알고리즘과 동일함

삭제

case 1: 삭제할 노드(r)가 리프 노드 : r을 삭제

 

case 2: 삭제할 노드의 자식 노드가 1개인 경우 - r의 부모가 r의 자식을 직접 가리키도록 함

 

case 3: 삭제할 노드의 자식 노드가 2개인 경우

- r의 오른쪽 서브 트리의 최소 원소 노드 s를 찾는다.

- s를 r자리로 복사하고 s를 삭제한다.

 

 

 

삭제가 된 후에도 이진 트리의 성질을 유지하고 있다.

코드

package myds;

public class MyBinarySearchTree {
    private Node root; // 루트 노드

    public MyBinarySearchTree() {
        this.root = null;
    }

    // 검색, key는 int라고 가정
    public Node search(int key) {
        return searchItem(root, key);
    }

    private Node searchItem(Node tNode, int key) {
        if (tNode == null)
            return null; // 검색 실패
        else if (tNode.item == key)
            return tNode; // 검색 성공
        else if (key < tNode.item)
            return searchItem(tNode.left, key); // key가 더 작으면 왼쪽 서브 트리
        else
            return searchItem(tNode.right, key); // 오른쪽 서브트리
    }

    public void insert(int key) {
        root = insertItem(root, key);
    }

    private Node insertItem(Node tNode, int key) {
        if (tNode == null)
            tNode = new Node(key); // null일 때 노드 추가
        else if (key < tNode.item)
            tNode.left = insertItem(tNode.left, key);
        else
            tNode.right = insertItem(tNode.right, key);
        return tNode; // 재귀적으로 left 또는 right에 새로운 노드를 매달게 됨!
        // 기본적으로 검색과 동일

    }

    // 삭제
    public void delete(int key) {
        root = deleteItem(root, key);
    }

    private Node deleteItem(Node tNode, int key) {
        if (tNode == null)
            return null; // 삭제할 node 존재x
        else {
            if (tNode.item == key)
                tNode = deleteNode(tNode); // 자식의 유무에 따라 다른 노드가 반환
            else if (key < tNode.item)
                tNode.left = deleteItem(tNode.left, key);
            else {
                tNode.right = deleteItem(tNode.right, key);
            }
            return tNode;
        }
    }

    private Node deleteNode(Node tNode) {
        // case 1
        if (tNode.left == null && tNode.right == null)
            return null;
        // case 2
        else if (tNode.left == null)
            return tNode.right; // 오른쪽 자식만 o
        else if (tNode.right == null)
            return tNode.left; // 왼쪽 자식만 o
        else {
            MyPair pair = deleteMinItem(tNode.right); // r의 오른쪽에서 가장 작은 노드 찾기
            tNode.item = pair.item;
            tNode.right = pair.node; // tNode의 오른쪽에 pair node를 담음
            return tNode;

        }
    }

    private MyPair deleteMinItem(Node tNode) {
        if (tNode.left == null)
            return new MyPair(tNode.item, tNode.right); 
        // 자리를 바꿀 노드의 right를 기존 부모의 left로 연결해줘야 함!
        else {
            MyPair pair = deleteMinItem(tNode.left);
            tNode.left = pair.node; 
            pair.node = tNode; // pair의 노드는 기존 tNode
            return pair;
        }
    }

    private class MyPair {
        private int item; // key
        private Node node; // 반환할 node

        public MyPair(int item, Node node) {

            this.item = item;
            this.node = node;
        }

    }
}

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

    public Node(int item) {
        this.item = item;
        left = null;
        right = null;
    }

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

}

성질

1. 노드가 하나로 이루어진 이진 트리는 높이가 1
2. 높이가 h인 포화 이진 트리 리프 노드의 총 수는 2^(h-1)
3. 높이가 h인 포화 이진 트리의 총 노드 수는 2^h-1
4. 총 n개의 노드를 가진 이진 트리의 높이는 적어도 h≥log2(n+1)
5. 총 n개의 노드를 가진 이진 트리의 최대 높이 = n (일자형 이진 트리)
6. 노드가 n개인 이진 검색 트리의 점근적 평균 검색 시간: θ(logN)

순회

모든 노드를 방문하는 경우

전위 순회

루트 → 좌서브트리 → 우서브트리 방문

preOrder(r):
    if (r!=null)
        r.visited = true;
        preOrder(r.left)
        preOrder(r.right)

중위 순회

좌서브트리 → 루트 → 우서브트리

inOrder(r)
    if (r!=null)
        inOrder(r.left)
        r.visited=true
        inOrder(r.right)

후위 순회

좌서브트리 → 우서브트리 → 루트

poserOrder(r)
    if (r!=null)
        postOrder(r.left)
        poserOrder(r.right)
        r.visited=true