[자료구조] 트리(Tree), 검색과 재귀(Searching & Recursion)

검색(Searching)

• 특정 노드를 추가하거나 삭제를 위해서는 검색이 우선되야 한다.
• 다양한 알고리즘을 활용하는 경우, 최적 알고리즘 경로를 측정하는데 쓰인다.
• 검색하는 컬렉션이 무작위이고 정렬되지 않은 경우, 선형검색이 기본적인 검색방법이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

# 선형 검색 알고리즘 # 하나의 반복문과 리스트의 인덱스, 조건문을 활용하여 특정값을 검색할 때까지 반복한다. def linear_search(arr, target): # 입력 배열의 각 항목을 반복 for idx in range(len(arr)): # 현재 인덱스의 항목이 비교 대상과 같은지 확인 if arr[idx] == target: # 현재 인덱스를 일치 항목으로 반환 return idx # 전체 배열을 반복할 수 있다면, 비교 대상은 존재하지 않는다.(의미없는 -1 값 반환) return -1 print(linear_search([0,1,2], 2)) # case 1 - true print(linear_search([0,1,2], 3)) # case 2 - false

Recursion(재귀)

• 알고리즘과 방법론에서 자주 언급되고, 중요한 개념이므로 반복하여 익숙해진다.
• 재귀의 개념은 수학적 사고에 기반하고, 코드를 작성하기 전에 문제를 해결하는 재호출 로직을 발견해야한다.
• 재귀 호출은 스택의 개념이 적용되며, 함수의 내부는 스택처럼 관리된다.(LIFO, 후입선출)
  • 단점: 재귀를 사용하면 함수를 반복적으로 호출하는 상황이 벌어지므로, 메모리를 더 많이 사용한다.
  • 수학적으로 개념이 복잡한 경우, 시간과 공간(메모리)복잡도 측면에서 효율이 안 좋더라도 재귀를 사용하여 문제를 해결하는 것이 좋다.
• 하위 문제를 쉽게 해결할 수 있을 때까지 문제를 더 작은 하위 문제로 나누는 것을 의미한다.
• 재귀적으로 다양한 문제를 해결할 수 있는데, 하나의 문제를 분할하면서 해결하고 해결 후 하나로 다시 합치는 ‘분할정복법’이 대표적이다.
  • 재귀는 해결을 위한 특정 기능을 재호출한다는 측면이고, 분할 정복은 문제를 분할하고 해결하는 구체적인 방법론이다.
  • 분할정복법을 활용하기 위해 재귀개념(기능 재호출)이 필요하다.
• 재귀에서 중점적으로 생각해야될 부분은 조건에 따른 반복계산이다.

조건

1) 기본 케이스

• 알고리즘은 특성상 반복을 중지할 수 있다.

2) 추가 조건

• 추가 조건과 기본 케이스의 차이를 확인한다.

3) 자신 호출

• 알고리즘이 자신을 호출해야 한다.

예제

1부터 n까지의 합

1 2 3 4

def oneto100(num): if num < 2: return 1 return num + oneto100(num - 1)

최대공약수

1 2 3 4

def factor(num1, num2): if num2 < 1: return num1 return factor(num2, num1 % num2)

트리(Tree)

• 루트(Root): 가장 위쪽에 있는 노드, 트리 별 하나만 있다.
  • 루트는 부모와 다르다. 부모노드는 자식노드가 1개 이상 있는경우에만 존재할 수 있다.
• 서브트리: 자식노드이면서 부모노드역할을 하는 노드가 있는 트리이다.
• 차수: 노드가 갖고 있는 최대 자식노드 수이다.
  • 위의 경우 차수는 2개이다.
    • 10의 차수, 8의 차수, 9의 차수, 1의 차수
• 리프(Leaf): 레벨별로 가장 마지막에 있는 노드, 단말노드(terminal node), 외부노드(external node)라고도 한다. 리프는 트리별로 여러 개가 있을 수 있다.
• 레벨: 루트노드에서 얼마나 멀리 떨어져 있는지 각각 나타낸다. 루트노드의 레벨은 0이며, 아래로 내려갈 때마다 1씩 증가한다.
• 높이: 루트에서 가장 멀리 떨어진 리프노드까지의 거리이며, 리프 레벨의 최대값을 높이라고 한다.
• 형제(Sibling) 노드: 부모가 같은 두 개의 노드이다.

이진 트리(Binary Tree)

• 아래와 같이 각 노드별로, 최대 2개의 서브노드를 가질 수 있다.(left, right)
• 여러 트리종류 중 가장 기본이 되면서 많이 활용되는 트리이다.
• 두 가지 조건으로 구성되어 있다.
  • 루틴 노드를 중심으로 두 개의 서브트리로 나눠진다.
  • 나눠진 두 서브트리도 모두 두 개의 서브트리를 갖는다.
    • 서브트리의 노드가 반드시 값을 갖고 있을 필요는 없다.

포화 이진 트리

• 모든 리프노드들이 동일한 레벨을 갖고 있는 경우이다.

완전 이진 트리

• 노드가 위에서 아래로 채워져있다.
• 노드가 왼쪽에서 오른쪽 순서대로 채워져있다.

BST(Binary Search Trees, 이진검색트리)

• 이진검색트리는 노드를 정확하게 정렬해야하는 특정 유형의 이진트리다.
• BST의 목적은 단순 이진트리보다 빠른 노드탐색이다. 때문에 insert node에서 중복을 처리해주는 것이 아닌, 아래 ‘값 크기 조건’에 맞도록 값을 넣어주는 경우가 이진탐색트리가 되는 것이다.
• 만약 아래 값 크기 조건을 지키지 않고 값을 삽입하는 경우 이진트리탐색의 로직이 아닌 단순이진트리의 로직으로 탐색되기 때문에 느린 탐색이 진행된다.
  • 값 크기 조건: 오른쪽 서브노드의 값(right child) > 루트 노드의 값 > 왼쪽 서브노드의 값(left child)
    • 중복값을 가진 노드가 없어야 한다.
    • 왼쪽 서브트리노드들의 값은 루트노드 값보다 작아야한다.
    • 오른쪽 서브트리노드들의 값은 루트노드 값보다 커야한다.
  • 위에 대한 규칙이 정해진 이유는 왼쪽부터 오른쪽으로 검색을 하는 구조이기 때문이다.
    • 왼 -> 오 개념이 적용되는 이유: 트리와 같은 자료구조는 기본이 되는 연결리스트를 참조해서 만들어진 개념이기 때문이다.
  • 특징
    • 위와 같은 규칙에 따라 구조가 단순하다.
    • base node / 검색할 노드 / 자식노드 존재여부에 따라 검색되는 노드의 순서가 달라진다.
    • 검색이 일반 이진트리보다 빠르기 때문에 노드를 삽입하기 쉽다.

검색 성공 경우

• 위 그림처럼 6(루트)보다 작은 2(왼쪽 자식노드)를 검색한다.
• 다음으로 2를 기준으로 5(오른쪽 자식노드)가 크므로 검색된다.
• 5를 기준으로 4(왼쪽 자식노드)가 작으면서 검색도 완료된다.

검색 실패 경우

• 6(루트)보다 큰 7(오른족 자식노드)을 검색한다.
• 7보다 큰 오른쪽 자식노드는 존재하지 않기 때문에 검색에 실패한다.

파이썬 소스 코드

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

class node: def __init__(self, value): """ bst에서 사용할 수 있는 node 클래스 """ self.value = value self.left = None self.right = None class binary_search_tree: def __init__(self, head): """ 문제 2. bst의 생성자 메소드 """ self.head = head def insert_node(self, value): """ 문제 3. bst의 동작에 맞게 값을 집어넣을 수 있는 메소드 """ self.base_node = self.head while True: if value < self.base_node.value: if self.base_node.left != None: self.base_node = self.base_node.left else: self.base_node.left = node(value) break else: if self.base_node.right != None: self.base_node = self.base_node.right else: self.base_node.right = node(value) break def search_node(self, value): """ 문제 4. bst 내부에 value값이 있는지 True / False값을 반환하는 메소드 """ self.base_node = self.head while self.base_node: if self.base_node.value == value: return True elif self.base_node.value > value: self.base_node = self.base_node.left else: self.base_node = self.base_node.right return False if __name__ == "__main__": """ 아래 코드를 통해 문제의 예상 입출력 확인 [아래 코드의 트리 형태] 16 / \ 12 19 / \ / \ 11 13 18 20 / 9 / \ 8 10 """ head = node(16) bt = binary_search_tree(head) bt.insert_node(12) bt.insert_node(19) bt.insert_node(11) bt.insert_node(13) bt.insert_node(18) bt.insert_node(20) bt.insert_node(9) bt.insert_node(8) bt.insert_node(10) print(bt.search_node(5)) #False print(bt.search_node(-2)) #False print(bt.search_node(18)) #True

순회 탐색

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

# 전위순회 def preorder_traverse(self): if self.head is not None: self.__preorder(self.head) def __preorder(self, cur): self.preorder_list.append(cur.value) print(cur.value) if cur.left is not None: self.__preorder(cur.left) if cur.right is not None: self.__preorder(cur.right) bt.preorder_traverse() print(bt.preorder_list) ''' 16 12 11 9 8 10 13 19 18 20 [16, 12, 11, 9, 8, 10, 13, 19, 18, 20] '''

참조

• 이진 탐색 트리(BST)와 불균형 이진 트리 문제 해결
• 트리정리
• 재귀는 하나의 데이터활용방법이다.
• [자료구조 알고리즘] Tree의 종류