이진 트리(Binary Tree)

이론

이진 트리(Binary Tree)

진명_Kim 2024. 3. 14. 22:48

트리 구조 (Tree)

한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 자료 구조.

(출처 : https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0)

계층적인 자료를 나타내는데, 자주 사용되는 자료구조로써 비선형적인 구조를 가지고 있으며

대칭적인 구조를 가지고 있다.

부모 노드가 여러 자식 노드들을 가질 수 있는 1대 多(다) 구조이다.

[구성 요소]

뿌리 (root)	부모 노드가 없는 최상위 노드, 트리의 깊이 0 에 속하며 오직 하나만 존재한다.
부모 노드	루트 노드 방향으로 직접 연결된 노드
자식 노드	루트 노드 반대 방향으로 직접 연결된 노드
가지 (branch)	부모 노드와 자식 노드가 모두 있는 노드, 트리 구조의 중간을 의미한다.
잎 (Leaf)	자식 노드가 없는 노드, 트리의 끝에 존재한다.
길이 (Length)	출발 노드에서 도착 노드까지 거치는 수
깊이 (Depth)	루트 노드부터의 길이, 0에서부터 시작된다.
차수 (Degree)	자식 노드의 갯수

계층 구조를 가질 수 있는 대칭적인 자료 구조로 효율적인 검색에 용이한다.

[유의해야할 점]

자식 노드의 갯수가 정해져 있으면 배열로 구현하고

갯수가 정해져 있지 않으면 리스트로 구현한다.

(리스트가 동적 배열이기 때문)

이진 트리 (Binary Tree)

부모 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리.

(일반적으로 이진 트리를 사용한다.)

[이진 트리의 순회 방식]

트리 구조는 일반적으로 비선형 자료 구조이기 때문에 순서에 대하여 규칙이 있어야한다.

전위 : 노드 -> 왼쪽 -> 오른쪽

순서 : A - B - D - E - F- C -G

중위 : 왼쪽 -> 노드 -> 오른쪽

순서 : D - B - E - A - F - C - G

후위 : 왼쪽 -> 오른쪽 -> 노드

순서 : D - E - B - F - G - C - A

알아두어야 할 것

이진 트리를 구현할 때, 주로 재귀 함수를 사용하는 경우가 많다.
재귀 함수 (Recursive Function)
자기 자신을 호출하는 함수.
반드시 종료 조건이 호출되어야 하며, 만약 없으면 무한 루프가 발생하여 스택 오버 플로우가 발생한다.

간단한 예시

//0. 이진 트리의 노드 클래스를 선언
public class BinaryNode<T>
{                            
    //1. 데이터를 담을 배열 및 리스트 선언
    public T item;

    //2. 부모 노드 선언
    public BinaryNode<T> parent;

    //3. 자식 노드 2개를 선언.
    public BinaryNode<T> left;
    public BinaryNode<T> right;

    public BinaryNode(T item)
    {
        this.item = item;            
    }
}

//4. 이진 트리 클래스 선언
public class BinaryTree<T>
{
    //5. 루트 노드 선언
    private BinaryNode<T> root;
	
    //6. 재귀 함수로 반복
    public BinaryTree(BinaryNode<T> root)
    {
        this.root = root;
    }

    //전위 순회
    public void PreOrder(BinaryNode<T> node)
    {
        if (root != null)
        {
            Console.Write(node.item + " -> ");
            PreOrder(node.left);
            PreOrder(node.right);
        }
    }

    //중위 순회
    public void InOrder(BinaryNode<T> node)
    {
        if(root != null)
        {
            PreOrder(root.left);
            Console.WriteLine(node.item + " -> ");
            PreOrder(root.right);
        }
    }

    //하위 순회
    public void PostOrder(BinaryNode<T> node)
    {
        if (root != null)
        {
            PreOrder(root.left);
            PreOrder(root.right);
            Console.WriteLine(node.item + " -> ");
        }
    }
}

internal class Program
{
    static void Main(string[] args)
    {
    	//이진 트리 노드 root 선언 및 A 삽입
        BinaryNode<char> root = new BinaryNode<char>('A');
        //루트의 자식 노드(left, right) 값 넣기
        root.left = new BinaryNode<char>('B');
        root.right = new BinaryNode<char>('C');
        //루트의 자식 노드의 자식노드(left, right) 값 넣기
        root.left.left = new BinaryNode<char>('D');
        root.left.right = new BinaryNode<char>('E');
        root.right.left = new BinaryNode<char>('F');
        root.right.right = new BinaryNode<char>('G');

		//사용할 이진 트리 호출
        BinaryTree<char> tree = new BinaryTree<char>(root);

        Console.WriteLine("전위 순회");
        tree.PreOrder(root);
    }
}

이진 탐색 트리 (Binary Search Tree)

이진 속성, 탐색 속성을 적용한 트리.

[이진 속성 : 부모 노드는 최대 2개의 자식 노드들만 가질 수 있다.]

[탐색 속성 : 자신의 노드보다 작은 값은 왼쪽, 큰값은 오른쪽에 위치한다.]

이진 탐색을 통한 탐색영역을 절반으로 줄여가며 탐색한다.

균형을 잡은 트리에서 유용한다.

[탐색]
수행할 내용 : 17을 탐색
23 (↙)
┌──────┴──────┐
11 (↘)                     38
┌──┴──┐              ┌──┴──┐
3           19 (↙)         31          65
└─┐ ┌─┴─┐       ┌─┘          └─┐
6 [17]    22       24                  87

루트 노드부터 시작하여 탐색하는 값과 비교.
작은 경우 왼쪽 자식 노드로...
큰 경우 오른쪽 자식 노드로 감.

1. 23과 17을 비교 => (17 < 23) -> 왼쪽으로 감.
ㄴ이제 오른쪽 서브 트리는 탐색할 필요가 없음.
2. 11과 17을 비교 => (17 > 11) -> 오른쪽으로 감.
3. 19와 17을 비교 => (17 < 19) -> 왼쪽으로 감.
4. 17과 17을 비교 => (17 == 17) -> 탐색 완료.

[삽입]
수행할 내용 : 35를 삽입

[삽입 전]
23 (↘)
┌──────┴──────┐
11                          38 (↙)
┌──┴──┐              ┌──┴──┐
3           19              31(↘)      65
└─┐ ┌─┴─┐       ┌─┘          └─┐
6 17      22       24                  87

[삽입 후]
23
┌──────┴──────┐
11 38
┌──┴──┐ ┌──┴──┐
3           19 31 65
└─┐ ┌─┴─┐       ┌─┴─┐ └─┐
6 17      22       24      35 87
탐색과 동일하게 루트 노드부터 시작해서 삽입하는 값과 비교.
작은 경우는 왼쪽 자식 노드로..
큰 경우는 오른쪽 자식 노드로 이동.

1. 23과 35를 비교 => (35 > 25) -> 오른쪽으로 감
2. 38과 35를 비교 => (35 < 38) -> 왼쪽으로 감.
3. 31과 35를 비교 => (35 > 31) -> 오른쪽으로 감.
4. 비어있는 공간이면 삽입.

[삭제]
1. 자식이 1개인 노드의 삭제 : 삭제하는 노드의 부모와 자식을 연결 후 삭제

수행할 내용 : 22를 삭제
[삭제 전]
23
┌──────┴──────┐
11 38
┌──┴──┐ ┌──┴──┐
3           19 31 65
└─┐  ┌─┴─┐      ┌─┴─┐
6  17      22 24      35
[삭제 후]
23
┌──────┴──────┐
11 38
┌──┴──┐              ┌──┴──┐
3           19              31          65
└─┐  ┌─┘ ┌─┴─┐
6  17 24      35

2. 자식이 1개인 노드의 삭제 : 삭제하는 노드의 부모와 자식을 연결 후 삭제
수행할 내용 : 38을 삭제
[삭제 전]
23
┌──────┴──────┐
11 38
┌──┴──┐ ┌──┴──┐
3           19 31          65
└─┐  ┌─┴─┐       ┌─┴─┐
6  17      22 24      35

[삭제 후]
23
┌──────┴──────┐
11 31

┌──┴──┐ ┌──┴──┐
3 19 24          35
└─┐ ┌─┴─┐
6 17      22

2. 자식이 2개인 노드의 삭제 : 삭제하는 노드를 기준으로 오른쪽 자식중 가장 작은 값 노드와 교체 후 삭제
23을 삭제

1. 오른쪽 자식중 가장 작은 값 노드를 탐색
23
┌──────┴──────┐
11 38
┌──┴──┐ ┌──┴──┐
3 19 24 65
└─┐  ┌─┴─┐      ┌─┘
6  17      22      31

2. 가장 작은 값 노드와 교체
24
┌──────┴──────┐
11 38
┌──┴──┐ ┌──┴──┐
3 19 23          65
└─┐  ┌─┴─┐ ┌─┘
6  17      22 31

3. 삭제
24
┌──────┴──────┐
11 38
┌──┴──┐ ┌──┴──┐
3           19 31 65
└─┐  ┌─┴─┐
6  17      22