[자료구조/Java] 이진탐색트리 - 탐색/삽입/삭제

트리는 Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 자료구조를 말합니다. 탐색에서 주로 사용됩니다.

 

• Binary Tree: 한 노드가 최대로 가질 수 있는 자식 노드가 2개인 트리
• Binary Search Tree: Binary Tree 중 왼쪽 자식 노드가 부모노드보다 작은 값, 오른쪽 자식 노드가 부모노드보다 큰 값을 가지는 트리

 

Terminology 용어정리

• 노드(Node): 데이터를 저장하는 기본 단위. 연결된 다른 Branch에 대한 정보 + 데이터로 구성됨.
• 루트 노드(Root node): 트리 최상단 노드
• 레벨, 층 (Level): 최상위 노드를 level 0, 하위로 연결된 branch의 깊이를 표현함
• 부모 노드(parent node): 특정 노드의 상위에 연결된 노드
• 자식 노드(child node): 특정 노드의 하위에 연결된 노드
• 리프 노드 (leaf(terminal) node): 자식 노드가 없는 끝단 노드
• 형제 노드 (sibiling/brother node): 동일한 부모 노드를 가진 자식 노드들
• 깊이 (depth): 트리의 최대 레벨

 

Node의 구조

public class Node {
	Node left;
	Node right;
	Integer value;

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

}

Node는 값을 지니는 value, 다른 Node를 가리키는 left, right 필드로 구성됩니다.

 

 

 

이진 탐색 트리 Binary Search Tree

이진 탐색트리는 한 노드가 최대 2개의 자식을 가질 수 있는 이진 트리 중 부모보다 작은 노드는 왼쪽, 큰 노드는 오른쪽에 위치하는 규칙을 따르는 트리입니다.

 

삽입 Insert

public boolean insert(Integer data) {
    MyNode newNode = new MyNode(data);
    MyNode cursor = this.root;
    // case 1 : 트리가 비어있는 경우
    if (root == null) {
        this.root = newNode;
        size++;
    } else {
        // case 2 : 최소 1개 이상의 노드가 트리에 존재하는 경우
        while (true) {
            // case 2-1 : 커서가 가리키고 있는 노드가 새로운 노드보다 큰 경우
            // 				커서를 트리의 왼쪽 방향으로 이동한다
            if (cursor.value > data) {
                if (cursor.left == null) {
                    cursor.left = newNode;
                    return true;
                } else {
                    cursor = cursor.left;
                }
                // case 2-2 : 커서가 가리키고 있는 노드가 새로운 노드보다 작거나 같은 경우
                //				커서를 트리의 오른쪽 방향으로 이동한다
            } else {
                if (cursor.right == null) {
                    cursor.right = newNode;
                    return true;
                } else {
                    cursor = cursor.right;
                }
            }
        }
    }
    return false;
}

1. 최소 1개 이상의 노드가 트리에 존재 하는가?
   존재하지 않는다면 root에 노드 삽입. 존재한다면 ②으로,
2. 새 데이터와 커서노드를 비교하여 left,right방향 탐색
3. 커서노드의 해당 방향에 노드가 없다면 삽입.
   있다면 커서노드를 해당 방향의 노드로 변경 2~3의 과정을 노드를 삽입할 수 있을때까지 반복

 

탐색 search

조회의 논리흐름과 유사합니다.

public MyNode search(Integer data) {
    

    MyNode cursor = this.head;

    while(true) {
        if(cursor == null) {
            System.out.println(data+" not exists");
            return null;
        }

        if(cursor.value == data) {
            return cursor;
        } else {
            if(data > cursor.value) {
                cursor = cursor.right;
            } else {
                cursor = cursor.left;
            }
        }
    }
}

 

 

삭제 Delete

삭제의 경우, 3가지의 경우로 나누어 동작합니다.

1. 삭제해야 하는 노드가 자식이 없는 리프 노드인 경우
2. 삭제해야 하는 노드가 자식이 2개인 경우
3. 삭제해야 하는 노드가 자식이 1개인 경우

 

 

 

1) 삭제해야 하는 노드가 자식이 없는 리프 노드인 경우

if(cursor.left == null && cursor.right == null) {
    if(cursor != root) {
        if(parent.left == cursor) {
            parent.left = null;
        } else {
            parent.right = null;
        }
    } else {
        root = null;
    }
}

 

 

 

 

 

 

2) 삭제해야 하는 노드가 자식이 2개인 경우

 

 

 

1. 삭제할 노드를 찾는다

 

2. 삭제할 노드는 cursor, 삭제할 노드의 부모노드는 parent

 

3. parent, cursor 사이의 값 중 최소값을 찾는다.

 

4. 최소값을 지닌 노드의 값을 temp노드에 임시 저장한다.

 

 

 

5. 최소값을 지닌 노드를 삭제한다.

6. 임시 저장한 노드의 최소값을 삭제할 노드에 삽입한다.

7. 결과적으로 BST가 규칙을 따르면서 노드가 변경되었다.

 

// 삭제될 노드가 두개의 자식 노드를 지닌 경우
else if (cursor.left != null && cursor.right != null) {
    // 삭제될 노드와 그 부모노드 사이의 최소 값을 지닌 노드를 찾는다.
    MyNode temp = findMinNode(cursor.right);
    int tempValue = temp.value;

    // 최소값 노드를 삭제 후, 삭제될 노드에 최소값을 삽입한다.
    remove(root, temp.value);
    cursor.value = tempValue;
}

 

 

 

 

 

3) 삭제해야 하는 노드가 자식이 1개인 경우

1. 삭제할 노드를 찾는다.

 

2. 삭제할 노드를 cursor, 해당 노드의 부모노드를 parent로 지정

 

3. cursor노드의 자식 노드를 child로 지정.

 

parent의 cursor노드 방향에 child노드 삽입

 

// 삭제될 노드가 한개의 자식만 지닌 경우
else {
    MyNode child = (cursor.left != null) ? cursor.left : cursor.right;

    if(cursor != root) {
        if(cursor == parent.left) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    } else {
        root = child;
    }
}

 

참조 레퍼런스(이곳)
전체 코드는 깃허브에서 확인할 수 있습니다.