재귀, 트리

학습내용

재귀

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

• 특징

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

• 조건

  • 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