트리

트리(Tree)란?

트리는 계층적인 구조를 표현할 때, 사용하는 자료구조이다.

제일 위쪽(최상단) 노드가 뿌리 노드(Root node)이다. 트리 자료구조를 보면 마치 나무를 뒤집었을 때, 뿌리가 하늘을 향하는 모습으로 생각할 수 있다.

트리 구조의 대표적인 예시: 가계도
예를 들어, 단군 신화에 따르면 가계도의 최상단 루트 노드는 단군이 될 것이다.

주요 용어

• 루트 노드(Root node): 부모가 없는 최상위 노드
• 단말 노드(Leaf node): 자식이 없는 노드 (최하단이 아니라도 단말 노드가 될 수 있다.)
• 크기(Size): 트리에 포함되는 모든 노드의 개수`
• 깊이(Depth) : 루트 노드로부터의 거리
• 높이(Height): 트리의 깊이 중 최댓값
• 차수(Degree): 각 노드의 자식 방향 간선의 개수. 자식 노드의 수.

트리의 크기가 N일 때, 전체 간선의 개수는 N - 1개

이진 탐색 트리, BST

이진 탐색이 동작할 수 있도록 고안된 효율적 탐색 트리

왼쪽 자식 노드 값 < 부모 노드 값 < 오른쪽 자식 노드 값

탐색 절차:

1. 현재 노드와 찾는 값 비교
2. 대소 비교 결과에 따라 왼쪽 노드 또는 오른쪽 노드로 진입.

위 과정을 반복하며 찾고하는 값 발견 시 탐색 종료.

탐색 과정에서 대소 비교 결과에 따라 왼쪽/오른쪽 서브 트리 하나를 선택하므로 선택되지 않은 서브 트리는 탐색 범위에서 제외된다.

결국 이상적인 경우 매 비교마다 탐색 범위가 절반씩 줄어든다.
-> O(logN) (N은 트리의 크기)

트리 순회, Tree Traversal

트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방식.

• 전위 순회 pre order : 부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 순서
• 중위 순회 in order : 왼쪽 노드 -> 부모 노드 -> 오른쪽 노드 순서
• 후위 순회 post order : 왼쪽 노드 -> 오른쪽 노드 -> 부모 노드 순서

BST 구현 - Go

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

type Node struct {
	data int
	left,right *Node
}

func insert(root **Node, x int) {
	// root가 없는 경우
	if *root == nil {
		*root = &Node{data: x}
		return
	}

	cur := *root
	for {
		if x < cur.data {
			if cur.left == nil {
				cur.left = &Node{data: x}
				return
			}
			cur = cur.left
		} else if x > cur.data {
			if cur.right == nil {
				cur.right = &Node{data: x}
				return
			}
			cur = cur.right
		} else {
			// x == cur.data
			return
		}
	}
}

func inorder(n *Node) {
	if n == nil {
		return 
	}
	inorder(n.left)
	fmt.Printf("%d ", n.data)
	inorder(n.right)
}

func main() {
	fmt.Print("트리의 원소를 입력하세요: ")

	in :=bufio.NewReader(os.Stdin)
	var root *Node
	for {
		var v int
		_, err := fmt.Fscan(in, &v)
		if err != nil {
			if err == io.EOF {
				break
			}
			fmt.Println(os.Stderr, "입력 오류: ", err.Error())
			os.Exit(1)
		}
		insert(&root, v)
	}
	inorder(root)
}