[TIL] 98. [자료구조] 트리

키워드

• 비선형 구조
• 이진트리
• 이진탐색트리
• 편향이진트리

[자료구조] 트리

• 루트(root) : 트리의 가장 위쪽에 있는 노드, 1개만 존재
• 리프(leaf) : 트리의 가장 아랫단에 있는 노드(가장 끝자락)
• 서브트리(sub tree) : 큰 트리에서 작은 트리를 쪼개서 보는 것(자식노드이면서 부모역할을 하는 노드가 있는 트리)
• 차수 : 노드가 갖고 있는 최대 자식 노드 수
• 레벨 : 루트 노드를 0으로, 아래로 한단계씩 +1
• 높이 : 제일 끝단 노드의 레벨과 루트 노트 레벨의 차이
• 형제 노드(sibling) : 부모가 같은 노드

[트리] 이진트리

• 각 노드 별로, 최대 2개의 서브노드를 가질 수 있음(left와 right)
• 트리 중 가장 기본이면서 가장 많이 활용

• 포화이진트리 : 모든 리프노드들이 동일한 레벨을 갖고 있는 경우(맨 마지막 레벨에 모든 리프노드가 차 있는 경우)
• 완전이진트리 : 노드가 왼쪽부터 차 있는 이진트리

[트리] 이진탐색트리

• 이진트리이지만, 반드시 반드시!!! 작은 값을 왼쪽에 두어야한다.(아주 중요)
• 위와 같은 조건을 값 크기 조건이라고 부르며 이진탐색트리는 '오른쪽 서브노드 값 > 부모 노드 값 > 왼쪽 서브노드 값'이 된다.
• 값 크기 조건을 만족하기 때문에 자료를 탐색 시 그냥 이진트리보다 훨씬 빠르다.

예시)

# 노드 클래스 생성(해당 클래스는 검색알고리즘에 필요한 기본클래스)

class node:
  def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None

# 이진탐색트리

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.node = self.head

    while True:
      if value < self.node.value:
          self.node = self.node.left
      elif value > self.node.value:
          self.node = self.node.right
      else:
          return True

      return False

---

편향이진트리 : 부모노드에 대해 계속 작은 값만 혹은 계속 큰 값만 insert한 경우(일반 연결리스트와 다를 게 없어진다.)