[자료구조] Tree 기본 개념 알아보기

[자료구조] Tree 기본 개념 알아보기

 

 

살펴볼 주요 개념:

- 트리의 개념

- 트리의 표현법(python)

1. 트리의 개념

 

트리(tree)는 부모 - 자식 간의 관계의 노드로 구성되어 있다.

한 방향 연결리스트와 비슷하다. 한 방향 연결리스트의 경우, 한 부모에 한 자식 밖에 없는 트리구조인 것이다.

트리는 두 개 이상의 자식 노드를 가질 수 있다. 세 개 이상의 자식을 가지는 2, 3, 4 트리와 같은 것도 존재한다.

 

각각의 노드에는 key값이 들어가 있다.

 

 

각각의 용어 설명을 해보자면 다음과 같다.

루트 노드 : 맨 꼭대기에 위치한 조상과 같은 노드

링크 or 에지 : 부모 노드와 자식 노드 사이를 이어주는 선

리프 노드 : 더 이상의 자식 노드가 없는 노드

형제 노드 : level이 같고 부모 노드가 같은 노드 (위의 그림에서는 (2, 3 / 11, 13)이 형제 노드이다)

 

level : 0부터 시작하며, 각각의 노드가 루트노드로부터 얼마나 떨어져있는지 층수를 알려준다.

트리의 높이 : 루트노드부터 가장 아래 level에 있는 리프노드까지 갈 때의 링크 길이(여기서는 4)

경로(path) : 노드 v에서 노드 w까지 가는 경로

(ex. 노드 1에서 -1로 갈 때, 1->3->9->-1을 거친다.)

 

2. 트리의 표현법

위와 같은 리스트가 있다고 생각해보자.

 

(1) 표현법 1. 리스트

 

leve 2까지 있다고 가정할 경우 다음과 같이 표현이 가능하다.

A = [a, b, c, None, d, e, f, None]

 

그러나 level 3까지 전체를 표현하기 위해서는 이렇게 표현해야 한다.

A = [a, b, c, None, d, e, f, None, None, h, i, j, None, None, None]

 

이런 식으로 None을 계속해서 표기해줘야 하는 문제가 발생한다.

 

 

(2) 표현법 2. 재귀적 리스트

 

A = [a(루트노드), [a의 왼쪽 부트리], [a의 오른쪽 부트리]]

이런 식으로 표현이 가능하다.

A = [a, [b, [], [d, [], []]], [c, [e, [], []],[f, [], []]]

 

재귀적 표현이 복잡하여 알아보기 쉽지는 않다.

 

 

(3) 표현법 3. 노드 class 정의

 

노드 클래스를 정의해서 연결 리스트를 만들었던 것을 활용하면 쉽게 해결할 수 있다.

key, left child, right child, parent 라는 4개의 멤버 변수를 만들어서 각각의 노드를 이어준다면, 연결 리스트로 트리를 구현할 수 있다.

class Node:
    def __init__(self, key):
    	self.parent = None
        self.left = None
        self.right = None
        self.key = key
        
        
root = Node(a)

root.left = Node(b)
root.left.parent = root
root.right = Node(c)
root.right.parent = root

...