[자료구조] 트리 & 이진 탐색 트리

트리구조형태

1. 트리구조란 무엇일까?

- 트리란 Node와 Branch를 이용해서 , 사이클을 이루지 않도록 구성한 데이터 구조이다. 

- 트리는 넓은 범위의 의미이고,  우리가 자주 볼 형태는 이진트리(Binary Tree) 형태의 구조이다.

- 이진트리는 검색, 탐색 알고리즘에 많이 사용된다. 

 

 

1-1.  익혀두어야 할 용어

- Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 branch 정보를 포함한다.)

- Root Node : 트리 맨 위에 있는 노드

- Level : 최상위 노드를 Level 0으로 하였을 때, 하위 branch로 연결된 노드의 깊이를 나타낸다.

- Leaf Node : Child Node 가 하나도 없는 노드 

 

 

 

2. 이진트리 & 이진 탐색 트리 (Binary Search Tree)

- 노드의 최대 Branch 가 2인 트리를 말한다.

- 이진 탐색 트리(BST) 란 : 이진 트리에 아래와 같은 추가 조건이 존재하는 트리구조

  - 왼쪽 노드는 해당 노드보다 작은 값이여야 한다.

  - 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있어야 한다.

 

- 이진 탐색 트리의 장점  

  - 배열과 비교를 해본다면 배열에서는 찾고 싶은 노드를 찾기 위해서 배열의 처음 index 부터 방문하여 찾아야 한다.

  - 하지만 이진 탐색 트리는 이진 탐색 트리의 조건에 의하여 빠르게 찾을 수 있다. 

  - 예를 들어 아래의 이진 탐색 트리 구조에서 32를 찾고자 한다면 해당 노드인 21 보다 32가 크기 때문에 

    오른쪽 노드에 존재할 것이고 오른쪽 노드의 값인 28 보다 32 가 더 크기 때문에 오른쪽 노드의 오른쪽에 존재할 것이다.

 

3. 이진 탐색 트리 소스 코드

- 삽입 기능 

public boolean insertNode(int data) {
        //CASE 1: Node 가 하나도 없을 경우
        if (this.head == null) {
            this.head = new Node(data);
        } else {
            //CASE 2: Node 가 하나 이상 들어 있을 경우
            Node findNode = this.head;
            while (true) {
                //CASE 2-1: 현재 Node의 왼쪽에 Node 가 들어가야 할 때
                if (data < findNode.value) {
                    if (findNode.left != null) {
                        findNode = findNode.left;
                    } else {
                        findNode.left = new Node(data);
                        break;
                    }
                    //CASE 2-2: 현재 Node의 오른쪽에 Node 가 들어가야 할 때
                } else {
                    if (findNode.right != null) {
                        findNode = findNode.right;
                    } else {
                        findNode.right = new Node(data);
                        break;
                    }
                }
            }
        }
        return true;
    }

 

• 탐색 기능 

public Node search(int data) {
        // CASE1 : Node 가 하나도 없는 경우
        if (this.head == null) {
            return null;
        } else {
            // CASE2 : Node 가 하나 이상일 경우
            Node findNode = this.head;
            while (findNode != null) {
                if (findNode.value == data) {
                    return findNode;
                } else if(data < findNode.value) {
                    findNode = findNode.left;
                } else {
                    findNode = findNode.right;
                }
            }
        }
        return null;
    }

 

- 삭제 기능

    - 삭제할 노드가 Leaf Node 인 경우

       - 부모 노드에서 삭제할 노드를 가리키지 않도록 한다.

// 1. 삭제할 Node가 Leaf Node 인 경우
        if (currNode.left == null && currNode.right == null) {
            if (value < currParentNode.value) {
                currParentNode.left = null;
                currNode = null;
            } else {
                currParentNode.right = null;
            }
        }
        return true;

- Child Node 가 하나인 Node 인 경우 

   - 삭제할 노드의 부모 노드가 삭제할 노드의 자식 노드를 가리키도록 한다. 

 // CASE2-1: 삭제할 Node 가 Child Node를 한 개 가지고 있을 경우 (왼쪽에 child Node가 있을 경우)
        } else if (currNode.left != null && currNode.right == null) {
            if (value < currParentNode.value) {
                currParentNode.left = currNode.left;
                currNode = null;
            } else {
                currParentNode.right = currNode.left;
                currNode = null;
            }
        } else if (currNode.left == null && currNode.right != null) {
            if (value < currParentNode.value) {
                currParentNode.left = currNode.right;
                currNode = null;
            } else {
                currParentNode.right = currNode.right;
                currNode = null;
            }
            return true;
        }

- Child Node 가 두 개인 Node 인 경우 (택 1) 

   - 삭제할 노드의 오른쪽 자식 중, 가장 작은 값을 삭제할 노드의 부모 노드가 가리키도록 한다.

   - 삭제할 노드의 왼쪽 자식 중, 가장 큰 값을 삭제할 노드의 부모 노드가 가리키도록 한다.