[Python Algorithms] 트리(Tree) 1

트리 구조는 연결 리스트와 비슷하게 노드와 링크를 이용하지만 동작 구조는 매우 다르다.

트리는 그래프의 일종이며 서로 다른 두 노드를 잇는 링크가 하나뿐인 그래프를 트리라고 표현한다.

 

basic tree structure

 

1. 트리 구조

트리구조에서 가장 상위에 있는 노드를 루트(root)노드라 한다.

또한 어떤 노드보다 상위에 있는 노드를 부모 노드(parent node)라 하고 하위에 있는 노드를 자식 노드(child node)라고 표현한다. 같은 부모를 두고 있는 경우에는 형제 노드(sibling node)라 부른다.

최하위에 있는 노드들은 리프 노드(leaf node)가 된다.

 

트리 구조에는 레벨(level)과 높이(height)가 존재하는데

레벨은 루트 노드에서부터 특정 노드까지 찾아오는데 방문한 총 노드의 수를 말하고

높이는 트리 구조에서 가장 큰 레벨을 트리의 높이라고 한다. (높이는 0 부터 시작)

하나의 노드에 연결된 서브트리의 갯수를 차수라고 부른다.

 

트리에는 루트노드가 반드시 존재하고 나머지 노드들도 여러 개의 노드 그룹으로 나뉠 수 있으며 노드 그룹 역시 또 하나의 트리가 될 수 있다.

 

 

2. 이진 트리(Binary Tree)

이진 트리는 자식 노드를 2개 이하로만 갖는 트리(트리 차수가 2 이하인 트리)를 말한다.

최대 2개의 자식 노드만 갖기 때문에 이진트리라고 부른다.

 

 

2-1. 이진 트리의 종류

1) 정 이진 트리(full binary tree): 모든 노드가 2개의 자식 노드를 가진 트리

2) 포화 이진 트리(perfect binary tree): 모든 노드의 깊이가 같은 정 이진 트리

3) 완전 이진 트리(complete binary tree): 마지막 레벨을 제외하고 모든 노드가 채워진 이진 트리

4) 균형 이진 트리(balanced binary tree): 모든 단말 노드의 깊이 차이가 많아야 1인 트리

 

 

3. 트리 구조 클래스

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        
    def init_tree():
        global root
        
        new_node = Node("A")
        root = new_node
        
        new_node = Node("B")
        root.left = new_node
        
        new_node = Node("C")
        root.right = new_node
        
        new_node_1 = Node("D")
        new_node_2 = Node("E")
        
        node = root.left
        node.left = new_node_1
        node.right = new_nodw_2
        
        new_node_1 = Node("F")
        new_node_2 = Node("G")
        node = root.right
        node.left = new_node_1
        node.right = new_node_2

root 변수를 글로벌 변수로 선언해주고 첫 노드 A를 root로 할당한다.

root 노드의 left에 노드 B를 선언해주고 right에 노드 C를 선언해준다.

 

node라는 변수에 root.left인 B 노드를 넣어주고 그 left에 노드 D, right에 노드 E를 할당해준다.

이후 다시 node라는 변수에 root.right인 C 노드를 넣어주고 그 left에 노드 F, right에 노드 G를 할당해준다.

 

---

[참고문헌]

1. "트리구조", ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

2. 박선주, 영진닷컴, "필수 알고리즘 with 파이썬"