13-1. 이진 트리 용어와 구현 (Binary Tree Terms and Implementation): 파이썬 자료구조와 알고리즘

이진 트리 (binary tree) 는 노드가 최대 두 개의 자식 노드 (왼쪽, left 와 오른쪽, right) 를 갖는 자료구조이다. 자식 노드는 부모 노드에 대한 참조를 포함할 수 있다. 트리의 루트 노드 (root node) 는 모든 노드의 조상이다.

 

이진 트리에서 노드의 차수는 최대 2다. 트리에 m개의 내부 노드가 있으며, 각 내부 노드에 두 개의 자식 노드가 있다고 가정한다. 또한 트리에 n개의 말단 노드가 있다면, 트리의 차수는 n-1 이다.

 

즉, 2m = n + m -1 이며, 따라서 m = n - 1 이다. 여기서 m은 내부 노드의 개수, n은 말단 노드의 개수이다.

 

용어

그래프와 마찬가지로, 트리도 기본적인 용어를 먼저 살펴보자.

• 노드 차수 (degree): 자식 수
• 경로 (path): 한 노드 (부모) 에서 다른 노드 (자식) 에 이르는 노드들의 순서
• 경로 길이 (length): 한 노드에서 다른 노드로 가는 간선의 수. 시작 노드와 끝 노드가 같다면 길이는 0이다.
• 형제 노드 (sibling node): 부모가 같은 두 노드
• 외부 (external) 노드 (말단 노드): 자식이 없는 노드 (차수가 0인 노드)
• 내부 (internal) 노드 (가지 노드): 자식이 있는 노드 (차수가 0이 아닌 노드)
• 노드 깊이 (depth): 루트 노드에서 어떤 노드로 가는 경로의 길이. 루트 노드의 깊이는 0이다.
• 노드 레벨 (level): 노드 깊이 + 1. 즉 루트 노드의 레벨은 1이다.
• 노드 높이 (height): 한 노드와 단말 노드 사이의 최대 경로 길이
• 크기 (size): 모든 노드의 수

포화 이진 트리

포화 이진 트리 (perfect binary tree) 는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 말단 노드가 같은 깊이 또는 레벨을 가지는 이진 트리이다. 예를 들어 아래와 같은 이진 트리를 말한다.

 

포화 이진 트리의 높이 (h) 와 말단 노드 수 (n) 의 관계를 그림으로 나타내면 다음과 같다.

 

또한, 포화 이진 트리의 총 노드 수는 2^(h+1) - 1 이다.

 

완전 이진 트리

완전 이진 트리 (complete binary tree) 는 마지막 레벨은 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 말단 노드는 왼쪽에 있다.

 

이진 트리 구현

이진 트리를 구현하는 가장 단순한 방법은 리스트를 사용하는 것이다. 다음 코드는 루트 노드와 두 개의 빈 하위 리스트가 있는 리스트를 만든다. 루트 노드의 왼쪽에 서브 트리를 추가하려면 루트 노드의 리스트 두 번째 위치에 새 리스트를 삽입하면 된다. 그러나 이 코드는 리스트 중간에 노드를 삽입하거나 꺼낼 때 제한이 있어 매우 비효율적이다.

 

def BinaryTreeList(r):
    return [r, [], []]

def insertLeft(root, newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1, [newBranch, t, []])
    else:
        root.insert(1, [newBranch, [], []])
    return root

def insertRight(root, newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2, [newBranch, [], t])
    else:
        root.insert(2, [newBranch, [], []])
    return root

def getRootVal(root):
    return root[0]

def setRootVal(root, newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

r = BinaryTreeList(3)
insertLeft(r, 4)
insertLeft(r, 5)
insertRight(r, 6)
insertRight(r, 7)
print(getRootVal(r))
print(getLeftChild(r))
print(getRightChild(r))

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/13. 이진 트리/BT_lists.py"
3
[5, [4, [], []], []]
[7, [], [6, [], []]]

 

그러나 이 코드는 노드의 검색, 추가 등의 작업이 매우 비효율적이다.

 

다음 코드는 이진 트리를 클래스로 표현한다. 이진 트리의 노드는 왼쪽과 오른쪽 자식 노드에 대한 특성을 가진다. 노드의 두 자식 노드를 검사하여 값이 없을 경우 말단 노드인지 확인할 수 있다.

 

# 높이
class Height(object):
    def __init__(self):
        self.height = 0

# 노드 클래스
class NodeBT(object):
    def __init__(self, value=None, level=1):
        self.value = value
        self.level = level
        self.left = None
        self.right = None

    def __repr__(self):
        return "{}".format(self.value)
    
    def _add_next_node(self, value, level_here=2):
        new_node = NodeBT(value, level_here)
        if not self.value:
            self.value = new_node
        elif not self.left:
            self.left = new_node
        elif not self.right:
            self.right = new_node
        else:
            # 왼쪽 오른쪽 자식이 모두 있다면 왼쪽 자속 노드에 새 노드 추가
            self.left = self.left._add_next_node(value, level_here + 1)
        return self
    
    def _search_for_node(self, value):
        if self.value == value:
            return self
        else:
            found = None
            if self.left:
                found = self.left._search_for_node(value)
            if self.right:
                found = found or self.right._search_for_node(value)
            return found
    
    def _is_leaf(self):
        # 말단 노드라면 왼쪽 오른쪽 자식이 모두 없다.
        return not self.right and not self.left
    
    def _get_max_height(self):
        heightr, heightl = 0, 0
        if self.right:
            heightr = self.right._get_max_height() + 1
        if self.left:
            heightl = self.left._get_max_height() + 1
        return max(heightr, heightl)
    
    def _is_balanced(self, height=Height()):
        # 균형 트리인지 확인 - O(n)
        lh = Height()
        rh = Height()

        if self.value is None:
            return True
        
        l, r = True, True
        if self.left:
            l = self.left._is_balanced(lh)
        if self.right:
            r = self.right._is_balanced(rh)
        
        height.height = max(lh.height, rh.height) + 1

        if abs(lh.height - rh.height) <= 1:
            return l and r
        
        return False

    def _is_bst(self, left=None, right=None):
        # 이진 탐색 트리인지 확인 - O(n)
        if self.value:
            if left and self.value < left:
                return False
            if right and self.value > right:
                return False
            
            l, r = True, True
            if self.left:
                l = self.left._is_bst(left, self.value)
            if self.right:
                r = self.right._is_bst(self.value, right)
            return l and r
        else:
            return True

# 이진 트리 클래스
class BinaryTree(object):
    def __init__(self):
        self.root = None
    
    def add_node(self, value):
        if not self.root:
            self.root = NodeBT(value)
        else:
            self.root._add_next_node(value)
    
    def is_leaf(self, value):
        node = self.root._search_for_node(value)
        if node:
            return node._is_leaf()
        else:
            return False
    
    def get_node_level(self, value):
        node = self.root._search_for_node(value)
        if node:
            return node.level
        else:
            return False
    
    def is_root(self, value):
        return self.root.value == value
    
    def get_height(self):
        return self.root._get_max_height()
    
    def is_balanced(self):
        return self.root._is_balanced()
    
    def is_bst(self):
        return self.root._is_bst()

bt = BinaryTree()
for i in range(1, 10):
    bt.add_node(i)

print(bt.get_node_level(8))

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/13. 이진 트리/binary_tree.py"
5

 

 

출처

파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인