[자료구조] 이진 트리(Binary Tree)

📌 현재 게시글의 개념과 코드는 이 책을 참고하여 정리하였습니다.

이진 트리(Binary Tree)

회사에서는 위 그림과 같은 조직이 구성되어 있습니다. 이런 조직표의 구성을 트리 구조로 볼 수 있는데요.

이진 트리(Binary Tree)의 개념을 알아보겠습니다.

트리(Tree) 자료구조는 나무를 거꾸로 뒤집어 놓은 형태입니다.

그래서 트리의 맨 위를 뿌리(root)라고 합니다.

루트를 레벨 0으로 두고 나뭇잎에 해당하는 아래로 내려올 수록 레벨이 1씩 증가합니다.

트리에서 각 위치는 노드(Node)라고 하는데요. 위 조직표를 다시 살펴보면 노드가 모두 10개임을 알 수 있습니다.

그리고 각 노드는 선, 즉 에지(edge)로 연결되어 있습니다. 위 노드와 아래 노드의 관계를 부모-자식 관계라고 합니다.

대표 노드인 '대의원 총회'의 자식 노드는 '감사', '이사회', '이사장', '운영위원회'로 노드 4개를 갖고 있습니다.

여기서 '이사장'은 '사업본부'와 '개발본부'의 자식노드를 2개 갖고 있으며, '사업본부'도 3개의 자식 노드를 갖습니다.

여기서 자식 노드 개수를 차수(degree)라고 합니다.

대표 노드는 자식이 넷이므로 차수가 4, 이사장 노드는 자식이 둘이므로 차수가 2이고, 사업본부의 차수도 3이 됩니다.

개발본부처럼 자식 노드가 없는, 차수가 0인 노드를 리프(leaf)라고 합니다.

리프는 감사, 이사회, 운영위원회, 개발본부가 속하겠네요.

그럼 여기서 나온 용어를 정리해보겠습니다.

용어 정리

• 트리(Tree) 자료구조: 트리의 거꾸로 뒤집어 놓은 형태
• 뿌리(root): 트리의 맨 위
• 레벨: 트리에서 아래로 내려올수록 레벨이 1씩 증가함
• 노드(Node): 트리에서 각 위치를 노드라고 함
• 에지(edge): 노드끼리 연결되어 있는 선
• 차수(degree): 노드가 갖고 있는 자식 노드의 수
• 리프(leaf): 자식 노드가 없는 노드

개념 정리

트리의 맨 위를 뿌리라고 한다. 뿌리를 노드 0으로 두고 나뭇잎에 해당하는 아래로 내려올수록 레벨이 1씩 증가한다. 트리에서 각 위치를 노드라고 한다. 각 노드는 에지로 연결되어 있다.

이진 트리(Binary Tree) 종류

이진 트리는 포화 이진 트리(full binary tree), 완전 이진 트리(complete binary tree), 편향 이진 트리(skewed binary tree) 3개로 나뉩니다.

1. 포화 이진 트리(full binary tree)

포화 이진 트리는 모든 노드가 꽉 차 있는 상태의 트리입니다.

노드 개수가 $2^{높이+1}-1$ 공식으로 계산됩니다.

예를 들어 높이가 3인 포화 이진 트리는 노드 개수가 $2^{3+1}-1$ 로 15개입니다.

2. 완전 이진 트리(complete binary tree)

완전 이진 트리는 번호를 부여한 순서로 노드가 배치됩니다.

노드가 일부 비어 있어도 되지만 끝 번호의 노드는 비어 있어야 합니다.

그림을 보시면 어떤 잎 노드 두 개의 레벨 차이가 1 이하이며 왼쪽부터 오른쪽으로 채워지는 구조입니다.

왼쪽에서 오른쪽으로 가다가 어떤 잎 노드와 다른 잎 노드 사이에 하나라도 비어 있으면 완전 이진 트리가 아닙니다.

3. 편향 이진 트리(skewed binary tree)*

편향 이진 트리는 모든 노드가 오른쪽이나 왼쪽으로 연결된 트리입니다.

편향 이진 트리는 사향 이진 트리라고 불리기도 합니다.

모든 노드가 부모 노드의 왼쪽 자식 노드이거나 오른쪽 자식 노드인 경우와 같습니다.

이진 트리의 노드 구조

트리는 왼쪽 자식과 오른쪽 자식으로 구성됩니다.

(a)와 같이 왼쪽과 오른쪽 링크가 있는 이중 연결 리스트 구조로 만들 수 있습니다.

이 노드를 활용하여 트리를 구성한 예가 (b)와 (c)입니다.

루트 노드인 '가'부터 왼쪽과 오른쪽 링크를 가리키도록 구성하고,

가리킬 곳이 없는 링크는 그냥 비워두면 됩니다.

이진 트리 구현

1. 이진 트리 생성

class TreeNode():
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None
        
node1= TreeNode()
node1.data = '화사'

node2= TreeNode()
node2.data = '솔라'
node1.left = node2

node3= TreeNode()
node3.data = '문별'
node1.right = node3

node4= TreeNode()
node4.data = '휘인'
node2.left = node4

node5= TreeNode()
node5.data = '쯔위'
node2.right = node5

node6= TreeNode()
node6.data = '선미'
node3.left = node6

print(node1.data, end=' ')
print()
print(node1.left.data, node1.right.data, end=' ')
print()
print(node1.left.left.data, node1.left.right.data, node1.right.left.data, end=' ')

Out:

화사 
솔라 문별 
휘인 쯔위 선미

레벨이 2인 이진 트리가 생성되었다.

2. 이진 탐색 트리 삽입

## 함수 선언 부분 ##
class TreeNode():
    def __init__(self):
        self.left = None
        self.data = None
        self.right = None
        
## 전역 변수 선언 부분 ##
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스']

## 메인 코드 부분 ##
node = TreeNode()               # 이름의 배열의 첫 번째 데이터를 루트 노드로 생성하고 메모리 공간에 넣는다.
node.data = nameAry[0]
root = node
memory.append(node)

for name in nameAry[1:]:
    
    node = TreeNode()           # 새 노드 생성
    node.data = name
    
    current = root              # 항상 루트 노트부터 시작한다. 즉, 현재 작업 노드는 항상 루트 노드부터 진행한다.
    while True:
        if name < current.data:
            if current.left == None:
                current.left = node
                break
            current = current.left
        else:
            if current.right == None:
                current.right = node
                break
            current = current.right
    
    memory.append(node)
    
print("이진 탐색 트리 구성 완료!")

Out:

이진 탐색 트리 구성 완료!

3. 데이터 검색

## 함수 선언 부분 ##
class TreeNode():
    def __init__(self):
        self.left = None
        self.data = None
        self.right = None
        
## 전역 변수 선언 부분 ##
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스']

## 메인 코드 부분 ##
node = TreeNode()               # 이름의 배열의 첫 번째 데이터를 루트 노드로 생성하고 메모리 공간에 넣는다.
node.data = nameAry[0]
root = node
memory.append(node)

for name in nameAry[1:]:
    
    node = TreeNode()           # 새 노드 생성
    node.data = name
    
    current = root              # 항상 루트 노트부터 시작한다. 즉, 현재 작업 노드는 항상 루트 노드부터 진행한다.
    while True:
        if name < current.data:
            if current.left == None:
                current.left = node
                break
            current = current.left
        else:
            if current.right == None:
                current.right = node
                break
            current = current.right
    
    memory.append(node)
    
findName = '마마무'     # 찾고자 하는 데이터

current = root          # 루트 노드부터 검색 시작
while True:             # 데이터를 찾거나 못 찾을 때까지 반복
    if findName == current.data:
        print(findName, '을(를) 찾음')
        break
    elif findName < current.data:
        if current.left == None:
            print(findName, '이(가) 트리에 없음')
            break
        current = current.left
    else:
        if current.right == None:
            print(findName, '이(가) 트리에 없음')
            break
        current = current.right
    

Out:

마마무 을(를) 찾음

4. 데이터 삭제

## 함수 선언 부분 ##
class TreeNode():
    def __init__(self):
        self.left = None
        self.data = None
        self.right = None
        
## 전역 변수 선언 부분 ##
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스']

## 메인 코드 부분 ##
node = TreeNode()               # 이름의 배열의 첫 번째 데이터를 루트 노드로 생성하고 메모리 공간에 넣는다.
node.data = nameAry[0]
root = node
memory.append(node)

for name in nameAry[1:]:
    
    node = TreeNode()           # 새 노드 생성
    node.data = name
    
    current = root              # 항상 루트 노트부터 시작한다. 즉, 현재 작업 노드는 항상 루트 노드부터 진행한다.
    while True:
        if name < current.data:
            if current.left == None:
                current.left = node
                break
            current = current.left
        else:
            if current.right == None:
                current.right = node
                break
            current = current.right
    
    memory.append(node)
    
deleteName = '마마무'

current = root
parent = None
while True:
    if deleteName == current.data:
        
        if current.left == None and current.right == None:
            if parent.left == current:
                parent.left = None
            else:
                parent.right = None
            del(current)
            
        elif current.left != None and current.right == None:
            if parent.left == current:
                parent.left = current.left
            else:
                parent.right = current.left
            del(current)
            
        elif current.left == None and current.right != None:
            if parent.left == current:
                parent.left = current.right
            else:
                parent.right = current.right
            del(current)
            
        print(deleteName, '이(가) 삭제됨')
        break
    
    elif deleteName < current.data:
        if current.left == None:
            print(deleteName, '이(가) 트리에 없음')
            break
        parent = current
        current = current.left
    else:
        if current.right == None:
            print(deleteName, '이(가) 트리에 없음')
            break
        parent = current
        current = current.right

Out:

마마무 이(가) 삭제됨

여기까지

• 이진 트리 생성
• 이진 트리 삽입
• 데이터 검색
• 데이터 삭제

까지의 과정을 알아보았습니다!👏