[Algorithm] 이진트리 1

출처

• 본 내용은 알고리즘 공부 내용이며 책과 강의 를 정리한 내용입니다

| 이번 강의 목표

• 이진 탐색 트리

| 이진 트리

• 현재보다 작은 값은 왼쪽 큰값은 오른쪽

| 노드

• 트리는 노드들의 구성체
• 노드가 서로 연결된것이 트리

• 노드 클래스

  세개의 멤버를 가지고 있음

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

| 삽입 ADD

#헤당 이진트리에 21을 넣으려면?

          27
         /  \
       20    30
        \
        22

def add(self, item):
    if self.head.val is None:
        self.head.val =item
    else :
        self.__add_node(self.head, item)

def __add_node(self, cur, item):
    if cur.val >= item:
        if cur.left is not None:
            self.__add_node(cur.left, item)
        else:
            cur.left = Node(item)
    else:
        if cur.right is not None:
            self.__add_node(cur.right,item)
        else:
            cur.right = Node(item)

| 탐색 SEARCH

#해당 이진트리에 22있나요?
          27
         /  \
       14    35
      / \   / \
   10  19  31 42

def search(self, item):
    if self.head.val is None:
        return  False
    else:
        return self.__search_node(self.head, item)

def __search_node(self, cur, item):
    if cur.val == item:
        return True
    else: 
        if  cur.val >= item:
            if cur.left is not None:
                return self.__search_node(cur.left,item)
            else:
                return False
        else:
            if cur.right is not None:
                return  self.__search_node(cur.right, item)
            else:
                return False

| 삭제 REMOVE

• 삭제는 세 가지 경우를 생각해야한다
  1. 지우고자하는 노드가 없을 때
  2. 지우고자하는 노드에 한쪽만 자식이 있을 때 - 부모를 죽이고 자식을 할아버지한테 붙여주면 됩니다
  3. 지우고자 하는 노드에 양쪽 모두에 자식이 있을 때 - 지우고자하는 노드의 서브트리에서 가장 왼쪽의 노드를 지우고자하는 노드의 자리에 옮겨준다

     #해당 이진트리에 10을 삭제
          27
         /  \
       14    35
      / \   / \
     9  19  31 42
     

자세한 코드 출처