C/C++/자료구조

내가 정리하는 자료구조 05 - 트리(Tree)

대표적인 데이터 구조7: 트리

1. 트리 (Tree) 구조

  • 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
    • 트리는 connected acyclic graph구조로 즉, 1개 이상의 노드로 이루어진 유한 집합이다.
    • 루트 노드(root)를 반드시 가진다.
    • 트리를 구성하는 노드 간에 단순 경로가 존재 또는 루트노드를 제외하고 나머지 노드들은 서로 연결 될 수 없는 분리집합 $T_{1}, T_{2}, \ldots, T_{n}$으로 분할 가능하다. $T_{1}, T_{2}, \ldots, T_{n}$등은 각각 하나의 트리(서브 트리)로 재귀적 정의로서 표현 할 수도 있다.
  • 실제로 어디에 많이 사용되나?
    • 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨

2. 알아둘 용어

  • Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
  • Degree : 어떤 노드의 자식 노드의 개수
  • Degree of a tree : 트리에 있는 노드의 최대 차수
  • Root Node: 트리 맨 위에 있는 노드
  • Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
  • Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
  • Child Node: 어떤 노드의 상위 레벨에 연결된 노드
  • Leaf Node (Terminal Node): Child Node가 하나도 없는 노드, 즉 Degree가 0인 노드
  • Sibling (Brother Node): 동일한 Parent Node를 가진 노드
  • Depth(Height): 트리에서 Node가 가질 수 있는 최대 Level
  • forest: 루트 노드를 없앤 후 얻은 서브 트리의 집합

트리의 구조

이진 트리(binary tree)

노드와 엣지의 관계

  • 이진 트리(binary tree)의 특징

    • 1) level i에서 최대 노드 수 : $2^{i-1}$
    • 2) 높이가 h인 이진 트리의 최대 노드 수 : $2^{h}-1$
    • 3) 높이가 h인 이진 트리의 최소 노드의 개수 : h

이진 트리의 예시

  • 이진 트리(binary tree)의 종류

이진 트리의 종류 - 포화 이진 트리

이진 트리의 종류 - 완전 이진 트리

이진 트리의 종류 - 편향 이진 트리

  • 이진 트리는 말 그대로 부모노드가 가질수 있는 자식노드가 최대 2개라는 의미이다. 그러한 이진 트리의 데이터를 탐색하는 방법을 설명하면 다음과 같은 방법들이 있다.

  • 전위 순회(preorder traversal)

    • 현재 노드가 처음 그리고 왼쪽 자식 노드 다음 오른쪽 자식노드를 탐색하게 하는 방식으로 노드에 값이 존재하지 않을 때까지 순회(재귀)하도록하는 탐색방식이다.

전위 순회(preorder traversal)

  • 중위 순회(inorder traversal)
    • 현재 노드의 왼쪽 자식노드부터 시작해서 현재 노드 그리고 마지막으로 오른쪽 자식 노드를 순회하는 방법이다.

중위 순회(inorder traversal)

  • 후위 순회(postorder traversal)
    • 현재 노드의 왼쪽 자식노드부터 시작해서 현재 노드의 오른쪽 자식노드 그리고 마지막으로 현재노드를 순회하는 방법이다.

후위 순회(postorder traversal)

  • 레벨 순회(level traversal)
    • level(depth)순으로 위에서 아래로 그리고 왼쪽부터 오른쪽으로 순회하는 방법이다.

레벨 순회(level traversal)

  • 위의 이진 트리의 순회를 반복적으로 하기 위해서 이전에 배웠던 자료구조인 스택과 큐를 활용할 것이다. 활용하기 위해서 다시 한번 기억을 떠올리며 만들어 본다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Node:
    def __init__(self, data=None):
        self.__data=data
        self.__next=None
    @property
    def data(self):
        return self.__data

    @data.setter
    def data(self, data):
        self.__data=data

    @property
    def next(self):
        return self.__next

    @next.setter
    def next(self, target):
        self.__next=target

class My_Queue:
    def __init__(self, head=None, tail=None):
        self.head=head
        self.tail=tail

    def is_empty(self):
        if self.head == None:
            return True

    def enqueue(self, data):
        new_node=Node(data)
        if self.is_empty():
            self.head=new_node
            self.tail=new_node
        else:
            self.tail.next=new_node
            self.tail=new_node

    def dequeue(self):
        if self.is_empty():
            print("현재 Queue에 노드가 존재하지 않습니다.")
        else:
            pop_data=self.head
            self.head=self.head.next
            return pop_data.data

class My_stack:
    def __init__(self, head=None, tail=None):
        self.head=head
        self.tail=tail

    def is_empty(self):
        if self.head:
            return False
        else:
            return True

    def push(self, data):
        new_node=Node(data)
        if self.is_empty():
            self.head=new_node
            self.tail=new_node
        else:
            new_node.next=self.head
            self.head=new_node

    def pop(self):
        if self.is_empty():
            return None
        pop_node=self.head
        self.head=self.head.next
#         print(pop_node.next)
        pop_node.next=None
        return pop_node.data

  • 정상적으로 작동하는지 확인하기 위해 테스트를 해본다.

  • Queue 테스트

1
2
3
4
5
6
7
8
9
q = My_Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)

while not q.is_empty():
    print(q.dequeue(), end='  ')
결과
1
1  2  3  4  5
  • Stack 테스트
1
2
3
4
5
6
7
8
9
10
s = My_stack()

s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.push(5)

while not s.is_empty():
    print(s.pop(), end="  ")

#

1
5  4  3  2  1

스택, 큐는 순회를 구현할때 사용

  • 위의 파일을 스택과 큐를 나누어서 각각 queue1, stack1이라는 python 파일로 저장하였다.

큐 : 레벨 순서 순회시 필요

스택 : 전위, 중위, 후위 순회를 반복문으로 구현할때 필요

1
2
from queue1 import My_Queue
from stack1 import My_Stack
  • 기본적으로 Tree의 노드를 먼저 만들어 본다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class TreeNode:
    def __init__(self, data=None):
        # 데이터 저장
        self.__data=data
        # 왼쪽 자식 노드
        self.__left=None
        # 오른쪽 자식 노드
        self.__right=None

    def __del__(self):
        print('data {} is deleted'.format(self.__data))

    @property
    def data(self):
        return self.__data

    @data.setter
    def data(self, data):
        self.__data=data

    @property
    def left(self):
        return self.__left

    @left.setter
    def left(self, left):
        self.__left=left

    @property
    def right(self):
        return self.__right

    @right.setter
    def right(self, right):
        self.__right=right

순회(traversal)

  • 순회(traversal)를 하는 코드를 작성하는 방법은 크게 2가지를 생각해 볼 수 있다.

    • 재귀 : 성능은 떨어지지만, 가독성이 높다.

    • 반복문 : 성능은 높지만, 가독성이 떨어진다.(실제로는 성능이 최우선이므로 반복문을 사용할 수 있다면, 반복문을 사용하는 것이 좋다.)

재귀함수를 통한 순회 코드 작성

  • 전위, 순위, 후위는 현재 노드의 데이터를 프린트해주는 순서에 의해서 결정될 것이다. 각 함수는공통된 코드를 갖으며, 우선 현재 노드의 왼쪽노드, 오른쪽 노드 순으로 각 함수를 재귀적으로 동작한다.

preorder(전위)

1
2
3
4
5
6
7
8
9
10
def preorder(cur):
    # base case
    if not cur: # cur가 empty node라면
        return
    # 방문 코드
    print(cur.data, end = " ")
    # 재귀
    preorder(cur.left) #여기서 실행이 끝났다는 얘기는 왼쪽은 다 순회를 했으므로 오른쪽으로 이동
    # 재귀
    preorder(cur.right)

inorder(중위)

1
2
3
4
5
6
7
8
9
10
def inorder(cur):
    # base case
    if not cur: # cur가 empty node라면
        return
    # 재귀
    inorder(cur.left) #여기서 실행이 끝났다는 얘기는 다 순회를 했으므로 오른쪽으로 이동
    # 방문 코드
    print(cur.data, end = " ")
    # 재귀
    inorder(cur.right)

postorder(후위)

1
2
3
4
5
6
7
8
9
10
def postorder(cur):
    # base case
    if not cur: # cur가 empty node라면
        return
    # 재귀
    postorder(cur.left) #여기서 실행이 끝났다는 얘기는 다 순회를 했으므로 오른쪽으로 이동
    # 재귀
    postorder(cur.right)
    # 방문 코드
    print(cur.data, end = " ")

반복문을 통한 순회 코드 작성

  • 1) 스택(Stack) : 재귀함수로 전위, 중위, 후위를 구현한다는 것은 각 함수가 계속쌓이는 것과 동일하므로 스택을 사용한 것이라고 할 수 있음.
  • 2) 큐(Queue) :

iter_preorder

1
2
3
4
5
6
7
8
9
10
11
12
def iter_preorder(cur):
    s=My_stack()
    while True:
        while cur: #cur가 있다면 왼쪽으로 계속 내려감.
            # 방문
            print(cur.data, end = "  ")
            s.push(cur)
            cur = cur.left
        cur=s.pop()
        if not cur:
            break
        cur=cur.right

iter_inorder

  • 2가지 방식으로 구현해보았다.
1
2
3
4
5
6
7
8
9
10
11
12
def iter_inorder(cur):
    s=My_stack()
    while True:
        while cur: #cur가 있다면 왼쪽으로 계속 내려감.
            s.push(cur)
            cur = cur.left
        cur=s.pop()
        if not cur:
            break
        # 방문
        print(cur.data, end = "  ")
        cur=cur.right
1
2
3
4
5
6
7
8
9
10
11
12
def iter_inorder(cur):
    stack_ls=My_stack()
    while True:
        while cur.left:
            stack_ls.push(cur)
            cur=cur.left
        print(cur.data, end = "  ")
        if stack_ls.is_empty():
            break
        cur=stack_ls.pop()
        print(cur.data, end = "  ")
        cur=cur.right

iter_postorder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def iter_postorder(cur):
    s1=My_stack()
    s2=My_stack()
    s1.push(cur)
    while s1.is_empty():
        cur=s1.pop()
        if not cur.left:
            s1.push(cur.left)
        if not cur.right:
            s1.push(cur.right)
        s2.push(cur)

    while not s2.is_empty():
        cur=s2.pop()
        print(cur.data, end="  ")

levelorder

1
2
3
4
5
6
7
8
9
10
11
def levelorder(cur):
    q = My_Queue()
    q.enqueue(cur)
    while not q.is_empty():
        cur = q.dequeue()
        #방문
        print(cur.data, end= "  ")
        if cur.left :
            q.enqueue(cur.left)
        if cur.right :
            q.enqueue(cur.right)
순회 테스트
1
2
3
4
5
6
7
8
9
10
11
n1=TreeNode(1)
n2=TreeNode(2)
n3=TreeNode(3)
n4=TreeNode(4)
n5=TreeNode(5)
n6=TreeNode(6)
n7=TreeNode(7)

n1.left=n2; n1.right=n3
n2.left=n4; n2.right=n5
n3.left=n6; n3.right=n7
1
preorder(n1)
결과
1
1 2 4 5 3 6 7
1
inorder(n1)
결과
1
4  2  5  1  6  3  7
1
postorder(n1)
결과
1
4  5  2  6  7  3  1
1
iter_preorder(n1)
결과
1
1  2  4  5  3  6  7
1
iter_inorder(n1)
결과
1
4  2  5  1  6  3  7
1
iter_postorder(n1)
결과
1
4  5  2  6  7  3  1
1
levelorder(n1)
결과
1
1  2  3  4  5  6  7

4. 자료 구조 이진 탐색 트리의 장점과 주요 용도

  • 주요 용도: 데이터 검색(탐색)
  • 장점: 탐색 속도를 개선할 수 있음

단점은 이진 탐색 트리 알고리즘 이해 후에 살펴보기로 함

  • 아래 이미에서 볼 수 있듯이 이진 탐색 트리 알고리즘은 3 step안에 27이라는 숫자를 찾아내지만, 배열(array)에서는 하나씩 비교하면 찾기 때문에 훨씬 많은 step을 거쳐야 한다.
  • 이와 같이 검색하기 위한 데이터를 저장해 놓을 때 이진 탐색 트리를 많이 사용한다.

이진트리와 정렬된 배열간의 탐색 비교

(출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

5. 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

5.1. 노드 클래스 만들기

1
2
3
4
5
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

5.2. 이진 탐색 트리에 데이터 넣기

  • 이진 탐색 트리 조건에 부합하게 데이터를 넣어야 함
    • 값이 같거나 크면 오른쪽에 위치하도록하고, 작으면 왼쪽에 위치하도록 코드를 작성함.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class NodeMgmt:
    def __init__(self, head):
        self.head = head

    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break

    def search(self, target):
        self.current_node = self.head
        while self.current_node:
            if self.currnet_node.value == target:
                return self.current_node
            elif self.current_node.value > target:
                self.current_node=self.current_node.left
            else:
                self.current_node=self.current_node.right
        return False
1
2
3
4
5
6
7
8
head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)
BST.insert(0)
BST.insert(4)
BST.insert(8)
BST.search(-1)
결과
1
False

5.4. 이진 탐색 트리 삭제

  • 매우 복잡함. 경우를 나누어서 이해하는 것이 좋음

5.4.1. Leaf Node 삭제

  • Leaf Node: Child Node 가 없는 Node
  • 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.

5.4.2. Child Node 가 하나인 Node 삭제

  • 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.

5.4.3. Child Node 가 두 개인 Node 삭제

  1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
  2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
5.4.3.1. 삭제할 Node의 오른쪽 자식중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키게 할 경우
  • 삭제할 Node의 오른쪽 자식 선택
  • 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
  • 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함
  • 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
  • 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
  • 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함

5.5. 이진 탐색 트리 삭제 코드 구현과 분석

5.5.1 삭제할 Node 탐색

  • 삭제할 Node가 없는 경우도 처리해야 함
    • 이를 위해 삭제할 Node가 없는 경우는 False를 리턴하고, 함수를 종료 시킴
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def delete(self, value):
    searched = False
    self.current_node = self.head
    self.parent = self.head
    while self.current_node:
        if self.current_node.value == value:
            searched = True
            break
        elif value < self.current_node.value:
            self.parent = self.current_node
            self.current_node = self.current_node.left
        else:
            self.parent = self.current_node
            self.current_node = self.current_node.right

    if searched == False:
        return False

### 이후부터 Case들을 분리해서, 코드 작성

5.5.2. Case1: 삭제할 Node가 Leaf Node인 경우

1
2
3
4
5
6
7
# self.current_node 가 삭제할 Node, self.parent는 삭제할 Node의 Parent Node인 상태
    if  self.current_node.left == None and self.current_node.right == None:
        if value < self.parent.value:
            self.parent.left = None
        else:
            self.parent.right = None
        del self.current_node

5.5.2. Case2: 삭제할 Node가 Child Node를 한 개 가지고 있을 경우

1
2
3
4
5
6
7
8
9
10
if self.current_node.left != None and self.current_node.right == None:
    if value < self.parent.value:
        self.parent.left = self.current_node.left
    else:
        self.parent.right = self.current_node.left
elif self.current_node.left == None and self.current_node.right != None:
    if value < self.parent.value:
        self.parent.left = self.current_node.right
    else:
        self.parent.right = self.current_node.right

5.5.3. Case3-1: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 왼쪽에 있을 때)

  • 기본 사용 가능 전략
    1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
    2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
  • 기본 사용 가능 전략 중, 1번 전략을 사용하여 코드를 구현하기로 함
    • 경우의 수가 또다시 두가지가 있음
      • Case3-1-1: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
      • Case3-1-2: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
        • 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문임

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if self.current_node.left != None and self.current_node.right != None: # case3
    if value < self.parent.value: # case3-1
        self.change_node = self.current_node.right
        self.change_node_parent = self.current_node.right
        while self.change_node.left != None:
            self.change_node_parent = self.change_node
            self.change_node = self.change_node.left
        if self.change_node.right != None:
            self.change_node_parent.left = self.change_node.right
        else:
            self.change_node_parent.left = None
        self.parent.left = self.change_node
        self.change_node.right = self.current_node.right
        self.change_node.left = self.current_node.left

5.5.4. Case3-2: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 오른쪽에 있을 때)

  • 기본 사용 가능 전략
    1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
    2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
  • 기본 사용 가능 전략 중, 1번 전략을 사용하여 코드를 구현하기로 함
    • 경우의 수가 또다시 두가지가 있음
      • Case3-2-1: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
      • Case3-2-2: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
        • 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문임

1
2
3
4
5
6
7
8
9
10
11
12
13
else:
    self.change_node = self.current_node.right
    self.change_node_parent = self.current_node.right
    while self.change_node.left != None:
        self.change_node_parent = self.change_node
        self.change_node = self.change_node.left
    if self.change_node.right != None:
        self.change_node_parent.left = self.change_node.right
    else:
        self.change_node_parent.left = None
    self.parent.right = self.change_node
    self.change_node.left = self.current_node.left
    self.change_node.right = self.current_node.right

5.5.5. 파이썬 전체 코드 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class NodeMgmt:
    def __init__(self, head):
        self.head = head

    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break

    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False        

    def delete(self, value):
        # 삭제할 노드 탐색
        searched = False
        self.current_node = self.head
        self.parent = self.head
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right

        if searched == False:
            return False    

        # case1
        if  self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None

        # case2
        elif self.current_node.left != None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right        

        # case 3
        elif self.current_node.left != None and self.current_node.right != None:
            # case3-1
            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left
            # case 3-2
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left

        return True

참고: http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html

5.5.6. 파이썬 전체 코드 테스트

  • random 라이브러리 활용
    • random.randint(첫번째 숫자, 마지막 숫자): 첫번째 숫자부터 마지막 숫자 사이에 있는 숫자를 랜덤하게 선택해서 리턴
      • 예: random.randint(0, 99): 0에서 99까지 숫자중 특정 숫자를 랜덤하게 선택해서 리턴해줌
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 0 ~ 999 숫자 중에서 임의로 100개를 추출해서, 이진 탐색 트리에 입력, 검색, 삭제
import random

# 0 ~ 999 중, 100 개의 숫자 랜덤 선택
# set 자료형을 사용하는 이유는 이진 탐색 트리(BST)에서 입력, 검색, 삭제할 경우 중복이있는 숫자의 경우
# 문제가 있을 수 있으므로 중복이 없도록 해서 100개를 뽑기 위해 아래와 같이 코드를 작성하였다.
bst_nums = set()
while len(bst_nums) != 100:
    bst_nums.add(random.randint(0, 999))
# print (bst_nums)

# 선택된 100개의 숫자를 이진 탐색 트리에 입력, 임의로 루트노드는 500을 넣기로 함
head = Node(500)
binary_tree = NodeMgmt(head)
for num in bst_nums:
    binary_tree.insert(num)

# 입력한 100개의 숫자 검색 (검색 기능 확인)
for num in bst_nums:
    if binary_tree.search(num) == False:
        print ('search failed', num)

# 입력한 100개의 숫자 중 10개의 숫자를 랜덤 선택
delete_nums = set()
bst_nums = list(bst_nums)
while len(delete_nums) != 10:
    delete_nums.add(bst_nums[random.randint(0, 99)])

# 선택한 10개의 숫자를 삭제 (삭제 기능 확인)
for del_num in delete_nums:
    if binary_tree.delete(del_num) == False:
        print('delete failed', del_num)
  • 위와 같은 방법과 다르게 아래 그림과 같은 BST를 구현해보고자 한다.

BST 구성

Binary Search Tree

    1. 모든 원소는 서로 다은 key를 가진다.
    1. 왼쪽 서브 트리에 있는 모든 키값들은 루트의 키값보다 작다.
    1. 오른쪽 서브 트리에 있는 모든 키값들은 루트의 키값보다 크다.

BST - 개념 01

    1. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.

BST - 개념 02

- binary_tree.py 파일

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
from queue1 import My_Queue
from stack1 import MY_stack

class TreeNode:
    def __init__(self, data=None):
        self.__data=data
        self.__left=None
        self.__right=None

    def __del__(self):
        print('data {} is deleted'.format(self.__data))

    @property
    def data(self):
        return self.__data

    @data.setter
    def data(self, data):
        self.__data=data

    @property
    def left(self):
        return self.__left

    @left.setter
    def left(self, left):
        self.__left=left

    @property
    def right(self):
        return self.__right

    @right.setter
    def right(self, right):
        self.__right=right

def preorder(cur):
    if not cur:
        return

    print(cur.data, end='  ')
    preorder(cur.left)
    preorder(cur.right)

def inorder(cur):
    if not cur:
        return

    inorder(cur.left)
    print(cur.data, end='  ')
    inorder(cur.right)

def postorder(cur):
    if not cur:
        return

    postorder(cur.left)
    postorder(cur.right)
    print(cur.data, end='  ')

def iter_preorder(cur):
    s=Stack()
    while True:
        while cur:
            print(cur.data, end='  ')
            s.push(cur)
            cur=cur.left
        cur=s.pop()
        if not cur:
            break
        cur=cur.right

def iter_inorder(cur):
    s=Stack()
    while True:
        while cur:
            s.push(cur)
            cur=cur.left
        cur=s.pop()
        if not cur:
            break
        print(cur.data, end='  ')
        cur=cur.right


def iter_postorder(cur):
    s1=Stack()
    s2=Stack()

    s1.push(cur)
    while not s1.empty():
        cur=s1.pop()
        s2.push(cur)

        if cur.left:
            s1.push(cur.left)

        if cur.right:
            s1.push(cur.right)

    while not s2.empty():
        cur=s2.pop()
        print(cur.data, end='  ')

def levelorder(cur):
    q=Queue()

    q.enqueue(cur)
    while not q.empty():
        cur=q.dequeue()
        print(cur.data, end='  ')
        if cur.left:
            q.enqueue(cur.left)
        if cur.right:
            q.enqueue(cur.right)

if __name__=="__main__":
    n1=TreeNode(1)
    n2=TreeNode(2)
    n3=TreeNode(3)
    n4=TreeNode(4)
    n5=TreeNode(5)
    n6=TreeNode(6)
    n7=TreeNode(7)

    n1.left=n2; n1.right=n3
    n2.left=n4; n2.right=n5
    n3.left=n6; n3.right=n7

    #preorder(n1)
    iter_preorder(n1)
    print()

    #inorder(n1)
    iter_inorder(n1)
    print()

    #postorder(n1)
    iter_postorder(n1)
    print()

    levelorder(n1)
    print()
  • 앞의 파일의 class를 활용하여 BST를 구현해 볼 것이다. 우선 각 기능을 분할하여 설명할 것이다.
    • 앞서 배웠던 순회의 개념 중 preorder 방식으로 노드가 갖고 있는 키값을 확인할 수 있도록 재귀(recursion)를 활용한 함수를 만든다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from binary_tree import TreeNode

class BST:
    def __init__(self):
        self.root=None

    def get_root(self):
        return self.root

    def preorder_traverse(self, cur, func, *args, **kwargs):
        if not cur:
            return

        func(cur, *args, **kwargs) #앞에서 했던 preorder 재귀함수의 print()대신 방문하는 것을 확인 하는 코드
        self.preorder_traverse(cur.left, func, *args, **kwargs)
        self.preorder_traverse(cur.right, func, *args, **kwargs)
  • insert 함수는 새로운 키값을 추가해주기 위한 함수로서 현재노드와 크기를 비교하여 작은 값은 왼쪽으로 큰 값은 오른쪽으로 이동하면서 빈 자리에 노드를 추가해 주면된다.

BST - insert 함수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def insert(self, data):
    new_node=TreeNode(data)

    cur=self.root
    # 아직 데이터가 하나도 없으면
    # 새로운 노드를 루트로 가져온다.
    if not cur:
        self.root=new_node
        return

    while True:
        parent=cur
        if data < cur.data:
            cur=cur.left
            if not cur:
                parent.left=new_node
                return
        else:
            cur=cur.right
            if not cur:
                parent.right=new_node
                return
  • 키값을 받아 현재 BST에 있는 노드들의 값과 일치하는 노드를 return한다.

BST - search

1
2
3
4
5
6
7
8
9
10
def search(self, target):
    cur=self.root
    while cur:
        if cur.data==target:
            return cur
        elif cur.data > target:
            cur=cur.left
        elif cur.data < target:
            cur=cur.right
    return cur
  • target값과 동일한 키값을 갖는 노드를 현재 BST 노드에서 제거하는 함수이다. 위에서 if-else 구문을 통해서 만든 BST와 동일한 기능을 하며, 위에서 만든 방식은 제거할 노드의 자식 노드가 2개인 경우 제거할 노드의 오른쪽 노드 서브트리에서 제일 작은 값으로 바꿔주었지만, 아래의 코드는 제거할 노드의 왼쪽 노드 서브트리 중에 가장 큰 값으로 바꿔주는 방법만 다르다.

BST - remove 함수

BST - remove 함수 리프노드제거하는 경우 - 01

BST - remove 함수 리프노드제거하는 경우 - 02

BST - remove 함수 리프노드제거하는 경우 - 03

BST - remove 함수 리프노드제거하는 경우 - 04

BST - remove 함수 제거하는 노드의 자식노드가 1개인 경우

BST - remove 함수 제거하는 노드의 자식노드가 1개인 경우 - 01

BST - remove 함수 제거하는 노드의 자식노드가 1개인 경우 - 02

BST - remove 함수 제거하는 노드의 자식노드가 1개인 경우 - 03

BST - remove 함수 제거하는 노드의 자식노드가 2개인 경우

BST - remove 함수 제거하는 노드의 자식노드가 2개인 경우 - 01

BST - remove 함수 제거하는 노드의 자식노드가 2개인 경우 - 02

BST - remove 함수 제거하는 노드의 자식노드가 2개인 경우 - 03

BST - remove 함수 제거하는 노드의 자식노드가 2개인 경우 - 04

BST - remove 함수 제거하는 노드의 자식노드가 2개인 경우 - 05

BST - remove 함수 제거하는 노드의 자식노드가 2개인 경우 - 06

BST - remove 함수 제거하는 노드의 자식노드가 2개인 경우 - 07

BST - remove 함수에서 root node를 업데이트 하는 이유 - 01

BST - remove 함수에서 root node를 업데이트 하는 이유 - 02

BST - remove 함수에서 root node를 업데이트 하는 이유 - 03

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def __remove_recursion(self, cur, target):
    if not cur:
        return None, None #recursion은 점화식이랑 기저조건이 필요한데, 기저조건은 탈출할때 필요하므로 기저조건1
    elif target < cur.data:
        cur.left, rem_node=self.__remove_recursion(cur.left, target)
    elif target > cur.data:
        cur.right, rem_node=self.__remove_recursion(cur.right, target)
    else: #기저조건(base case) 2
        if not cur.left and not cur.right:
            rem_node=cur
            cur=None
        elif not cur.right:
            rem_node=cur
            cur=cur.left
        elif not cur.left:
            rem_node=cur
            cur=cur.right
        else:
            replace=cur.left
            while replace.right:
                replace=replace.right
            cur.data, replace.data=replace.data, cur.data
            cur.left, rem_node=self.__remove_recursion(cur.left, replace.data)
    return cur, rem_node

def remove(self, target):
    self.root, removed_node=self.__remove_recursion(self.root, target)
    # self.root를 출력해주는 이유 루트를 삭제시 기존의 root에 계속 있어 꼬이므로!
    if removed_node:
        removed_node.left=removed_node.right=None
    return removed_node

테스트

1
bst=BST()
insert
1
2
3
4
5
6
7
8
9
bst.insert(6)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(5)
bst.insert(8)
bst.insert(10)
bst.insert(9)
bst.insert(11)
1
2
f=lambda x: print(x.data, end='  ')
bst.preorder_traverse(bst.get_root(), f)
결과
1
6  3  2  4  5  8  10  9  11
1
2
3
4
5
res=bst.search(8)
if res:
    print('searched data : {}'.format(res.data))
else:
    print('search failed')
결과
1
searched data : 8
delete
1
2
3
4
5
6
7
#지울 노드가 리프 노드일 때
#bst.remove(9)
#자식 노드가 하나일 때
#bst.remove(8)
#자식 노드가 둘일 때
bst.remove(6)
bst.preorder_traverse(bst.get_root(), f)
결과
1
2
data 6 is deleted
5  3  2  4  8  10  9  11

6. 이진 탐색 트리의 시간 복잡도와 단점

6.1. 시간 복잡도 (탐색시)

  • depth (트리의 높이) 를 h라고 표기한다면, O(h)
  • n개의 노드를 가진다면, $h = log_2{n} $ 에 가까우므로, 시간 복잡도는 $ O(log{n}) $
    • 참고: 빅오 표기법에서 $log{n}$ 에서의 log의 밑은 10이 아니라, 2입니다.
      • 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함

(출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

6.2. 이진 탐색 트리 단점

  • 평균 시간 복잡도는 $ O(log{n}) $ 이지만,
    • 이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며,
  • 다음 예와 같이 구성되어 있을 경우, 최악의 경우는 링크드 리스트등과 동일한 성능을 보여줌 ( $O(n)$ )
Share