[Section 4] 노드 알고리즘 구현 _ 이진 트리(Binary Trees)

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

트리에 구성된 노드들이 각각 하나 이상의 아이(child) 노드를 가지거나, 없는 경우, 이진트리(Binary Trees)로 분류된다. 이진트리의 특성과 유형을 알아보고, 알고리즘을 구현해보자.

1.  이진트리의 특성과 유형

이진트리도 노드의 구성에 따라 크게 3가지 유형으로 나눌 수 있다. 이는 각각 완전 이진 트리(Complete Binary Tree), 가득찬 이진트리(Full Binary Tree) 그리고 엄격한 이진트리(Strict Binary Tree)로 불린다. 노드의 구성은 다음의 그림을 참고하도록 하자.

 

이진 트리의 세 가지 유형

먼저, 완전 이진 트리의 경우는 조금 복잡하다. 만약 어떤 이진트리의 높이가 h이고 잎 노드까지의 높이가 h이거나 h-1인 경우라면, 그 이진트리는 완전 이진트리가 된다. 이러한 설명은 간혹 혼란을 야기할 수 있는데, 완전 이진트리의 핵심은 노드가 차례대로 쌓이느냐 아니냐이다. 트리는 통상적으로 왼쪽에서 우측 순서로 노드를 탐색한다. 따라서 완전 이진트리는 왼쪽 노드서부터 차례대로 노드가 구성되어있는 경우를 말한다.

 

가득 찬 이진트리의 경우, 마지막 계층을 제외한 모든 노드가 정확히 2개의 노드로 구성된 트리를 말한다. 그리고 엄격한 이진트리의 경우는 각각의 노드들이 정확히 2개의 노드를 갖거나 없는 경우를 의미한다. 

 

이진트리의 용어를 알아보았으니, 이번에는 특성을 알아보자. 가장 중요한 노드의 구성은 두 개의 포인터 변수와 하나의 데이터로 구성되어야 한다. 다음의 그림을 참고하자.

 

트리 노드의 구성

위 구성을 보면, 이진트리의 특성을 알 수 있다. 바로 높이가 0이라는 것인데, 재미있는 것은 높이를 통해서 가득 찬 이진트리 유형일 때 이진트리의 노드 개수는 2^h라는 것을 유추 할 수 있다. 

2.  이진 트리의 주 ADT와 보조 ADT

이진트리의 개념을 바탕으로 주 ADT와 보조 ADT를 알아보자. 먼저 주 ADT에는 다음의 기능이 포함되어야 한다.

 

데이터의 삽입과 삭제 기능, 특정 데이터의 검색 기능, 트리 순회(Traversing) 기능

 

* 트리 순회 기능이란 트리에서 구현해야 하는 주 기능 중 하나로 자식 노드로 접근하는 방법에 따라 다른 노드로 접근된다. 따라서 정확히 한 번 씩 모든 데이터에 접근하는 체계적인 방법을 트리 순회 기능이라 한다.

 

보조 ADT 기능은 다음과 같다.

 

트리의 사이즈 계산, 트리의 높이 계산, 등등...

3.  기본 알고리즘의 구현 _ 데이터의 삽입과 삭제

순회 기능에도 여러 가지 종류가 존재하므로 이곳에서는 기본 알고리즘을 구현함으로써 이진트리를 구성하고자 한다. 가장 먼저 이진 노드 트리 구성을 위한 노드 알고리즘을 알아보자. 

 

노드 알고리즘 : 

class BNode:
    def __init__(self,data):
        self.data=data
        self.Lchild=None
        self.Rchild=None
    def setD(self,data):
        self.data=data
    def getD(self):
        return self.data
    def getLchild(self):
        return self.Lchild
    def getRchild(self):
        return self.Rchild

 

 

노드 생성 예시:

코드 결과

이제 가장 기본적인 노드 구성은 완성되었다. 노드는 자체적으로 데이터를 추가할 수도 제거할 수 있는 상태이다. 그렇다면, 다음 차례는 무엇인가? 바로 이진트리의 순회이다.