재귀, 트리

seongyong·2021년 8월 1일
0

컴퓨터 공학 기본

목록 보기
6/8

학습내용

재귀

재귀는 말 그대로 재호출 로직을 의미한다.

  • 특징

    • 스택의 개념이 적용되며, 후입선출 방식으로 실해왼다.
    • 단점 : 메모리를 더 많이 사용한다.
    • 장점 : 수학적으로 개념이 복잡한 경우에 하위 문제를 구성하여 쉽게 해결가능.
  • 조건

    • base case가 있어야한다.
    • 추가 조건과 기본 케이스의 차이를 확인한다.
    • 반드시 자기 자신을 호출해야 한다.
    def sum_list(items):
        if len(items) == 1: # Base Case
            return items[0]
        elif:
            return items[0] + sum_list(items[1:]) # 반복적으로 자기자신을 호출한다.

트리

  • 용어정리
    • 루트 : 가장 위쪽에 있는 노드
    • 서브트리 : 자식노드이면서 부모노드역할을 하는 노드가 있는 트리
    • 차수 : 노드가 갖고 있는 최대 자식노드 수
    • 리프 : 가장 마지막에 있는 노드, 여러개가 존재
    • 레벨 : 루트노드에서 얼마나 멀리 떨어져 있는지를 나타내는 값. 루트노드의 레벨은 0이다.
    • 높이 : 리프 레벨의 최대값
    • 형제 노드 : 부모가 같은 노드
이진 트리

각 노드별로, 최대 2개의 서브노드를 갖는 트리를 이진 트리라 한다.

  • 특징

    • 루트노드를 중심으로 두 개의 서브트리로 나눠진다.
    • 나눠진 두 서브트리도 모두 두 개의 서브트리를 갖는데, 서브트리의 노드가 반드시 값을 갖고 있을 필요는 없다.
  • 포화 이진 트리

    • 모든 리프노드들이 동일한 레벨을 갖는 경우
  • 완전 이진 트리

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

  • 이진 검색트리

    • 노드를 정확하게 정렬해야하는 이진 트리

    • 노드 탐색을 목적으로 하는 이진 트리이다.

    • 조건

      • 오른쪽 서브노드의 값 > 루트 노드의 값 > 왼쪽 서브노드의 값
      • 중복값이 없어야한다.
      • 왼쪽부터 오른쪽으로 검색을 하는 구조
      #이진검색트리 삽입 및 검색
      
      class binary_search_tree:
        def __init__(self, head):
          self.head = head
      
        def insert_node(self, value):
          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):
          self.base_node = self.head
      
          while self.base_node:
              if self.base_node.value == value:
                  return True
      
              if self.base_node.value > value:
                  self.base_node = self.base_node.left
              else:
                  self.base_node = self.base_node.right
            
          return False

0개의 댓글