본문 바로가기
Algorithm/개념정리

[자료구조] 이진트리(Binary Tree) 생성 개념 정리

최원영 2021. 10. 25. 15:10

들어가며

사이버 대학교 특성 상 직장을 다니면서 자유롭게 학습할 수 있는 환경을 제공해준다. 그러나, 직장에서 야근, 주말 출근이 잦은 경우에는 출석체크 정도만 할 수 있고, 제대로 된 공부를 할 수 없다는 큰 단점이 있다. 필자 또한 약 2년 6개월 간의 직장생활을 하는 동안 잦은 야근, 거의 매주 출근으로 인해 시험을 보기 위한 벼락치기 외에는 제대로 된 학습을 수행하지 못했다. 현재는 퇴사하고 시간이 남아돌아서 토이 프로젝트를 하며, 공부하던 중 이진트리에 대해 제대로 학습하자는 취지로 본 글을 작성하였다.

 

1. 이진트리

이진트리에 대한 정의는 구글에 검색하면 긴 글과 다양한 전문 용어로 잘 나와있기 대문에 따로 언급하지 않겠으나, 쉽게 말하자면 아래 그림과 같이 크게 두 갈래로 나뉜 트리라고 할 수 있다.

이진트리를 구성하는 각각의 노드는 삼각형 형태로, 루트 노드(root), 왼쪽 노드(left), 오른쪽 노드(right)로 구성되어 있다.

 

2. 노드 생성

2.1. 노드 구조

이진트리를 구성하고 있는 각각의 노드를 실제 코드로 작성하기 위해 대부분 클래스(class)를 사용하지만, 직관적으로 결과를 확인하기 위하여 아래와 같이 딕셔너리(Dictionary)로 노드를 구현하였다.

{
    "data": null,
    "left": {
        "data": null,
        "left": { /* ... */ },
        "right": { /* ... */ },
    },
    "right": {
        "data": null,
        "left": { /* ... */ },,
        "right": { /* ... */ },
    }
}

노드를 나타내는 각각의 딕셔너리의 키(key)는 크게 data, left, right로 구성하였으며, left, right 키는 None 또는 data, left, right 키가 포함된 딕셔너리로 구성되도록 하였다.

2.2. 함수 정의

이진트리를 구성하는 데이터가 리스트로 구성되어 있을 때, 각각의 노드를 이진트리에 생성하는 초기 함수를 아래와 같이 나타낼 수 있다.

def insertNode(lst, root, idx):
    root = {
        "data": lst[idx],
    }

위 함수의 인자는 lst, root, idx이며, 이는 각각 이진트리를 구성하는 데이터가 담긴 리스트, 루트 노드, 인덱스를 나타낸다. 그리고 루트 노드는 또 다른 하위 노드를 나타내는 딕셔너리로 초기화해주었다. 위 함수를 재귀함수로 구성하여 루트 노드의 left, right 노드를 구성하도록 하였으며, 이를 적용한 코드는 아래와 같다.

def insertNode(lst, root, idx):
    root = {
        "data": lst[idx],
        "left": insertNode(lst, None, idx*2 + 1),
        "right": insertNode(lst, None, idx*2 + 2),
    }
    return root

재귀함수는 계속해서 자기 자신을 반복해서 호출하므로 반드시 반환 조건이 필요하다. 만약 반환 조건이 없을 경우 무한 루프에 빠지게 된다. 주어진 리스트의 모든 요소를 노드로 만들 것이기 때문에 인자로 받은 인덱스(index)가 리스트의 길이보다 작은 경우에만 노드를 생성하고, 그렇지 않은 경우에는 None을 반환하도록 하였다. 이를 코드로 나타내면 아래와 같다.

def createNode(arr, root, idx):
    if idx < len(lst):
        root = {
            "data": lst[idx],
            "left": insertNode(lst, None, idx*2 + 1),
            "right": insertNode(lst, None, idx*2 + 2),
        }
    return root

2.3. 생성 과정

위에서 작성한 코드는 아래와 같이 호출되어 이진트리를 생성한다. 그렇다면 트리를 이루는 노드는 어떻게 생성되는지 그 과정을 파해쳐보도록 하자.

tree = insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=None, 
    idx=0
)

2.3.1. 최초 노드 A 생성

최초 이진트리를 구성하는 노드는 아무것도 존재하지 않으므로, 루트 노드는 None이 되고, 인덱스는 0으로 한다. 그 결과, 아래 그림과 같이 트리의 첫 번째 노드 A가 생성된다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=None, 
    idx=0
)
{
    data: "A", // ✔
    left: null,
    right: null
}

2.3.2. 노드 A의 left 노드 B 생성

노드 A의 left 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 1(0 * 2 + 1)이 리스트의 유효한 인덱스 범위에 해당하므로 노드 A의 left인 노드 B를 생성한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=A.left, 
    idx=1
)
{
    data: "A",
    left: {
        data: "B", // ✔
        left: null,
        right: null
    },
    right: None
}

2.3.3. 노드 B의 left 노드 D 생성

노드 B의 left 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 3(1 * 2 + 1)이 리스트의 유효한 인덱스 범위에 해당하므로 노드 B의 left인 노드 D를 생성한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=B.left, 
    idx=3
)
{
    data: "A",
    left: {
        data: "B",
        left: {
            data: "D", // ✔
            left: null,
            right: null
        },
        right: null
    },
    right: None
}

2.3.4. 노드 D의 left 노드 H 생성

노드 D의 left 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 7(3 * 2 + 1)이 리스트의 유효한 인덱스 범위에 해당하므로 노드 D의 left인 노드 H를 생성한다.

< 그림 6 >

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=D.left, 
    idx=7
)
{
    data: "A",
    left: {
        data: "B",
        left: {
            data: "D",
            left: {
                data: "H", // ✔
                left: null,
                right: null
            },
            right: null
        },
        right: null
    },
    right: None
}

2.3.5. 노드 H의 left 노드 생성 종료

노드 H의 left 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 15(7 * 2 + 1)가 리스트의 유효한 인덱스 범위를 벗어나므로 None을 반환하며, 노드 H의 left 노드 생성을 종료한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=H.left, 
    idx=15
)
{
    data: "A",
    left: {
        data: "B",
        left: {
            data: "D",
            left: {
                data: "H",
                left: null, // ✔
                right: null
            },
            right: null
        },
        right: null
    },
    right: None
}

2.3.6. 노드 H의 right 노드 생성 종료

이어서 노드 H의 right 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 16(7 * 2 + 2)이 리스트의 유효한 인덱스 범위를 벗어나므로 None을 반환하며, 노드 H의 right 노드를 비롯한 하위 노드 생성을 종료한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=H.right, 
    idx=16
)
{
    data: "A",
    left: {
        data: "B",
        left: {
            data: "D",
            left: {
                data: "H",
                left: null,
                right: null // ✔
            },
            right: null
        },
        right: null
    },
    right: None
}

2.3.7. 노드 D의 right 노드 생성 종료

노드 H의 하위 노드 생성이 종료되어 상위 노드 D로 돌아온다. 노드 D의 right 노드 를 생성하기 위한 재귀함수는 인자로 받은 인덱스 8(3 * 2 + 2)이 리스트의 유효한 인덱스 범위를 벗어나므로 None을 반환하며, 노드 D의 right 노드를 비롯한 하위 노드 생성을 종료한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=D.right, 
    idx=8
)
{
    data: "A",
    left: {
        data: "B",
        left: {
            data: "D",
            left: { /* Node H */ },
            right: null // ✔
        },
        right: null
    },
    right: None
}

2.3.8. 노드 B의 right 노드 E 생성

노드 D의 하위 노드 생성이 종료되어 상위 노드 B로 돌아온다. 노드 B의 right 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 4(1 * 2 + 2)가 리스트의 유효한 인덱스 범위에 해당하므로 노드 B의 right 노드 E를 생성한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=B.right, 
    idx=4
)
{
    data: "A",
    left: {
        data: "B",
        left: { /* Node D */ },
        right: {
            data: "E", // ✔
            left: null,
            right: null
        }
    },
    right: None
}

2.3.9. 노드 E의 left 노드 생성 종료

노드 E의 left 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 9(4 * 2 + 1)가 리스트의 유효한 인덱스 범위를 벗어나므로 None을 반환하며, 노드 E의 left 노드 생성을 종료한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=E.left, 
    idx=9
)
{
    data: "A",
    left: {
        data: "B",
        left: { /* Node D */ },
        right: {
            data: "E", 
            left: null, // ✔
            right: null
        }
    },
    right: None
}

2.3.10. 노드 E의 right 노드 생성 종료

이어서 노드 E의 right 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 10(4 * 2 + 2)이 리스트의 유효한 인덱스 범위를 벗어나므로 None을 반환하며, 노드 E의 right 노드를 비롯한 하위 노드 생성을 종료한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=E.right, 
    idx=10
)
{
    data: "A",
    left: {
        data: "B",
        left: { /* Node D */ },
        right: {
            data: "E", 
            left: null, 
            right: null // ✔
        }
    },
    right: None
}

2.3.11. 노드 A의 right 노드 C 생성

노드 B의 하위 노드 생성이 종료되어 상위 노드 A로 돌아온다. 노드 A의 right 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 2(0 * 2 + 2)가 리스트의 유효한 인덱스 범위에 해당하므로 노드 A의 right 노드 C를 생성한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=A.right, 
    idx=2
)
{
    data: "A",
    left: {
        data: "B",
        left: { /* Node D */ },
        right: { /* Node E */ }
    },
    right: {
        data: "C", // ✔
        left: null,
        right: null
    }
}

2.3.12. 노드 C의 left 노드 F 생성

노드 C의 left 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 5(2 * 2 + 1)가 리스트의 유효한 인덱스 범위에 해당하므로 노드 C의 left 노드 F를 생성한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=C.left, 
    idx=5
)
{
    data: "A",
    left: { /* Node B */ },
    right: {
        data: "C",
        left: {
            data: "F", // ✔
            left: null,
            right: null
        },  
        right: null
    }
}

2.3.12. 노드 F의 left 노드 생성 종료

노드 F의 left 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 11(5 * 2 + 1)이 리스트의 유효한 인덱스 범위를 벗어나므로 None을 반환하며, 노드 F의 left 노드 생성을 종료한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=F.left, 
    idx=11
)
{
    data: "A",
    left: { /* Node B */ },
    right: {
        data: "C",
        left: {
            data: "F", 
            left: null, // ✔
            right: null
        },  
        right: null
    }
}

2.3.13. 노드 F의 right 노드 생성 종료

이어서 노드 F의 right 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 12(5 * 2 + 2)가 리스트의 유효한 인덱스 범위를 벗어나므로 None을 반환하며, 노드 F의 right 노드를 비롯한 하위 노드 생성을 종료한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=F.right, 
    idx=12
)
{
    data: "A",
    left: { /* Node B */ },
    right: {
        data: "C",
        left: {
            data: "F", 
            left: null, 
            right: null // ✔
        },  
        right: null
    }
}

2.3.14. 노드 C의 right 노드 G 생성

노드 F의 하위 노드 생성이 종료되어 상위 노드 C로 돌아온다. 노드 C의 right 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 6(2 * 2 + 2)이 리스트의 유효한 인덱스 범위에 해당하므로 노드 C의 right 노드 G를 생성한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=C.right, 
    idx=6
)
{
    data: "A",
    left: { /* Node B */ },
    right: {
        data: "C",
        left: { /* Node F */ },,  
        right: {
            data: "G", // ✔
            left: null,
            right: null
        }
    }
}

2.3.15. 노드 G의 left 노드 생성 종료

노드 G의 left 노드를 생성하기 위한 재귀함수는 인자로 받은 인덱스 13(6 * 2 + 1)이 리스트의 유효한 인덱스 범위를 벗어나므로 None을 반환하며, 노드 G의 left 노드 생성을 종료한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=G.left, 
    idx=13
)
{
    data: "A",
    left: { /* Node B */ },
    right: {
        data: "C",
        left: { /* Node F */ },,  
        right: {
            data: "G", 
            left: null, // ✔
            right: null
        }
    }
}

2.3.16. 노드 G의 right 노드 생성 종료

이어서 노드 G의 right를 생성하기 위한 재귀함수는 인자로 받은 인덱스 14(6 * 2 + 2)가 리스트의 유효한 인덱스 범위를 벗어나므로 None을 반환하며, 노드 G의 right 노드를 비롯한 하위 노드 생성을 종료한다.

insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=G.right, 
    idx=14
)
{
    data: "A",
    left: { /* Node B */ },
    right: {
        data: "C",
        left: { /* Node F */ },,  
        right: {
            data: "G", 
            left: null, 
            right: null // ✔
        }
    }
}

2.3.17. 노드 A 반환

노드 G의 하위 노드 생성이 종료되어 최상위 노드 A의 모든 하위 노드 생성이 완료되었다. insertNode 함수는 최종적으로 root인 노드 A를 반환함으로써 이를 이진트리로 생성한다.

def insertNode(lst, root, idx):
    root = {
        "data": lst[idx],
        "left": insertNode(lst, None, idx*2 + 1),
        "right": insertNode(lst, None, idx*2 + 2),
    }
    return root

tree = insertNode(
    arr=["A", "B", "C", "D", "E", "F", "G", "H"],
    root=None, 
    idx=0
)

 

마치며

글이 너무 길어진 탓에 잠시 쉬어가려고 한다. 다음 글에는 이어서 이진트리를 순회하는 방법과 그 개념에 대해서 정리하겠다.

'Algorithm > 개념정리' 카테고리의 다른 글

정렬 알고리즘(Sort Algorithm)의 퀵 정렬(Quick Sort) 개념 정리  (0) 2022.03.28
자료 구조(Data Structure)의 큐(Queue) 개념 정리  (0) 2022.01.15
자료 구조(Data Structure)의 스택(Stack) 개념 정리  (0) 2022.01.14
검색 알고리즘(Search Algorithm)의 해시법(체인법과 오픈 주소법) 개념 정리  (0) 2022.01.13
검색 알고리즘(Search Algorithm)의 선형 검색과 이진 검색 개념 정리  (0) 2022.01.12

티스토리툴바