트리(Tree)

1. 트리 (Tree) 구조

• 트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
• 실제로 어디에 많이 사용되나?
  • 트리 중 이진 트리(Binary Tree)형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨

2. 알아둘 용어

• Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• Root Node : 트리 맨 위에 있는 노드
• Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
• Child Node : 어떤 노드의 상위 레벨에 연결된 노드
• Leaf Node : (Terminal Node) : Child Node가 하나도 없는 노드
• Sibling (Brother Node) : 동일한 Parent Node를 가진 노드
• Depth : 트리에서 Node가 가질 수 있는 최대 Level

트리 Image

3. 이진 트리와 이진 탐색 트리 ( Binary Search Tree)

• 이진 트리 : 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리 (Binary Search Tree, BST) : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
  • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음

이진 탐색

4. 자료 구조 이진 탐색 트리의 장점과 주요 용도

• 주요 용도 : 데이터 검색(탐색)
• 장점 : 탐색 속도를 개선할 수 있음

이진트리와 정렬된 배열간의 탐색 비교

5. 구현해보기

5.1 노드 클래스 만들기

5.2 이진 탐색 트리에 데이터 넣기

public class NodeMgmt {
		Node head = null;
		public class Node{
			Node left;
			Node right;
			int value;
			
			public Node(int data) {
				this.value = data;
				this.left = null;
				this.right = null;
			}
		}
		
		public boolean insertNode(int data) {
			// CASE1 : Node가 하나도 없을 때
			if(this.head == null) {
				this.head = new Node(data);
			}else {
				// CASE2 : Node가 하나 이상 들어가 있을 때
				Node findNode = this.head;
				while(true) {
					// CASE2-1 : 현재 Node의 왼쪽에 Node가 들어가야 할 때
					if(data < findNode.value) {
						if(findNode.left != null) {
							// 그 다음 Dept로 들어가는 코드
							findNode = findNode.left;
						}else {
							findNode.left = new Node(data);
							break;
						}
					}else {
						// CASE2-2 : 현재 Node의 오른쪽에 Node가 들어가야 할 때
						if(findNode.right != null) {
							findNode = findNode.right;
						}else {
							findNode.right = new Node(data);
							break;
						}
					}
				}
			}
			return true;
		}
		
	}

5.3 이진 탐색 트리 탐색

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

}

5.4 이진 탐색 트리 삭제

5.4.1 Leaf Node 삭제

• Leaf Node : Child Node가 없는 Node
• 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.

5.4.2 Child Node가 하나인 Node 삭제

• 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.

5.4.3 Child Node가 두개인 Node 삭제

1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

5.4.3.1 삭제할 Node의 오른쪽 자식중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키게 할 경우

• 삭제할 Node의 오른쪽 자식 선택
• 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
• 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가키리게 함
• 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
• 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
• 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함

5.5. 이진 탐색 트리 삭제 코드 구현과 분석

5.5.1 삭제할 Node 탐색

• 삭제할 Node가 없는 경우도 처리해야 함
  • 이를 위해 삭제할 Node가 없는 경우는 False를 리턴하고 함수를 종료 시킴

5.5.3 삭제할 Node 탐색

• Case3-1-1 : 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
  • 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜나햐면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문이다.
  •