[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 22

* 수업은 JS 기반이지만 Python으로 구현

Section 22

트리 소개

• 비선형 구조
• 트리의 구성 요소
  • root: 트리의 가장 높은 노드
  • chlld: 다른 노드에 직접적으로 연결된 노드
  • parent: child의 반대 개념
  • siblings: 같은 parent를 가진 노드 그룹
  • leaf: children이 없는 노드
  • edge: 노드와 노드 사이를 연결하는 것

트리 사용하는 경우

• HTML DOM(문서 객체 모델)
• 네트워크 라우팅
• 추상 구문 트리: 프로그래밍 언어의 구문을 보여주는 방법 중 하나
• 인공지능: 결정과 분화의 반복
• 운영체제에서 폴더시스템 설계 방식
• 컴퓨터 파일 시스템

이진 트리 소개

• 최대 노드당 두 개의 자식을 갖는 트리, 0~2개까지 가능하다.
• 데이터를 비교하여 정렬 가능하게 저장한다.
  • 부모 노드를 기준으로 그보다 작은 것은 왼쪽으로, 큰 것은 오른쪽으로 가른다. 이 작업을 다시 자식 노드에서 반복되어 수행한다.

이진 검색 트리 소개

• 찾고자 하는 값과 노드를 비교하여 더 크다면 오른쪽을, 더 작다면 왼쪽으로 가서 비교를 한다.
• 이진 트리와 같은 규칙을 따른다.
  • 모든 부모 노드는 최대 두 개의 자식을 갖는다.
  • 부모 노드보다 왼쪽에 있는 모드 노드는 항상 부모 노드보다 작고, 오른쪽에 있는 노드는 부모보다 항상 크다.

 

class 소개

• 노드와 이진탐색트리 클래스를 각각 만들어 활용한다.
  • 노드 클래스에서는 left와 right 포인터의 초기값을 Null로 둔다.
  • 이진탐색트리 클래스에서는 root의 초기값을 Null로 둔다.

insert method 소개

• 새로운 노드를 만든다.
• 루트가 존재하는지 확인한다.
  • 존재하지 않다면, 새로운 노드가 루트가 된다.
  • 존재한다면, 새로운 노드가 루트값보다 큰지 작은지 비교한다.
    • 만약 크다면, 비교 노드값(초기에는 루트값)에 오른쪽 값이 있나 확인한다.
      • 만약 존재한다면 그 노드로 이동해 비교하는 단계부터 다시 반복한다.
      • 만약 존재하지 않다면 그 위치에 새로운 노드 값을 넣는다.
    • 만약 작다면, 비교 노드값(초기에는 루트값)에 왼쪽 값이 있나 확인한다.
      • 만약 존재한다면 그 노드로 이동해 비교하는 단계부터 다시 반복한다.
      • 만약 존재하지 않다면 그 위치에 새로운 노드 값을 넣는다.
• 삽입 이후에 전체 트리의 출력을 반환한다.

find method 소개

• 루트가 존재하는지 확인한다.
  • 존재하지 않다면, False를 반환한다.
  • 존재한다면, 새로운 노드가 루트값과 동일하다면 True를 반환한다.
  • 만약 동일하지 않다면 큰지 작은지 비교한다.
    • 만약 크다면, 비교 노드값(초기에는 루트값)에 오른쪽 값이 있나 확인한다.
      • 만약 존재한다면 그 노드로 이동해 비교하는 단계부터 다시 반복한다.
      • 만약 존재하지 않다면 False를 반환한다.
    • 만약 작다면, 비교 노드값(초기에는 루트값)에 왼쪽 값이 있나 확인한다.
      • 만약 존재한다면 그 노드로 이동해 비교하는 단계부터 다시 반복한다.
      • 만약 존재하지 않다면 False를 반환한다.
• 삽입 이후에 전체 트리의 출력을 반환한다.

 

 

method 구현

# 이진탐색트리 구현

class Node:
    # construcotr
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


class BinarySearchTree:
    # constructor
    def __init__(self):
        self.root = None

    # instance method
    def insert(self, val):
        newNode = Node(val)

        if self.root is None:
            self.root = newNode
            return self
        else:
            current = self.root
            while(True):
                if val is current.val:
                    return 'Undefined'
                if val < current.val:
                    if current.left is None:
                        current.left = newNode
                        return self
                    current = current.left
                    
                if val > current.val:
                    if current.right is None:
                        current.right = newNode
                        return self
                    current = current.right
    
    # instance method
    def find(self, val):
        if self.root is None:
            return False

        current = self.root
        found = False

        while(current and not found):
            if val < current.val:
                current = current.left
            elif val > current.val:
                current = current.right

            else:
                found = True
        if not found:
            return 'Undefined'
        return current
   

#  선언
tree = BinarySearchTree()

print('\n--- insert fcn---')
# insert 수행
print(tree.insert(0))
print(tree.insert(1))
print(tree.insert(5))
print(tree.insert(8))
print(tree.insert(13))
print(tree.insert(11))
print(tree.insert(0))

print('\n--- find fcn---')
# find 수행
print(tree.find(0))
print(tree.find(3))
print(tree.find(11))

 

트리: 빅오 복잡도

• Insertion: O(log N)
• Searching: O(log N)