7강: 연결 리스트

각 원소들을 줄줄이 엮어서 관리하는 방식

선형 배열에 비해서 연결리스트가 가지는 장단점은?

• 장점
  • 중간 원소의 삽입/삭제가 쉽다
• 단점
  • 메모리 소요가 크다
  • $k$ 번째 원소를 찾아 가는 데에 시간이 오래 걸린다 → $O(n)$

기본적인 연결 리스트

여러 Node로 구성되어 있으며, Node는 Data와 Link(next)로 구성되어있음

class Node:
    def __init__(self, item):
        self.data = item
        self.next = None

class LinkedList:
    def __init__(self):
        self.node_count = 0
        self.head = None
        self.tail = None

단방향 연결 리스트 연산

1. 특정 원소 참조(k 번째)

   def get_at(self, pos): # 1부터 시작
       if pos <= 0 or pos > self.node_count:
           return None
       curr = self.head
       for _ in range(pos - 1):
           curr = curr.next
       return curr

2. 연결리스트 순회

   (아래 실습 에서 작성)

3. 길이 얻어내기

   def get_length(self):
       return self.node_count

🏃‍♂️실습: 연결 리스트 순회 구현하기

문제 설명

제 7 강에서 소개된 추상적 자료구조로 LinkedList 라는 이름의 클래스가 정의되어 있다고 가정하고, 이 리스트를 처음부터 끝까지 순회하는 메서드 traverse() 를 완성하세요.

제출

def traverse(self):
    result = []
    curr = self.head
    while curr:
        result.append(curr.data)
        curr = curr.next
    return result

8강: 연결리스트 (2)

단방향 연결 리스트 연산

1. 원소의 삽입

   💡주의사항

   1. 삽입하려는 위치가 리스트 맨 앞일때
      • prev 없음
      • Head 조정 필요
   2. 삽입하려는 위치가 리스트 맨 끝일 때
      • Tail 조정 필요

   def insert_at(self, pos, new_node):
       if pos < 1 or pos > self.node_count + 1:
           return False
   
       if pos == 1:
           new_node.next = self.head
           self.head = new_node
   
       else:
           if pos == self.node_count + 1:
               prev = self.tail
           else:
               prev = self.get_at(pos - 1)
           new_node.next = prev.next
           prev.next = new_node
   
       if pos == self.node_count + 1:
           self.tail = new_node
   
       self.node_count += 1
       return True

2. 원소의 삭제

   (아래 실습에서 작성)

3. 두 리스트 합치기(concatenation)

   def get_at(self, pos):
           if pos <= 0 or pos > self.node_count:
               return None
           curr = self.head
           for _ in range(pos):
               curr = curr.next
           return curr

🏃‍♂️실습: 연결 리스트 노드 삭제하기

문제 설명

제 8 강에서 소개된 추상적 자료구조 LinkedList 클래스의 메서드로서 popAt() 메서드를 강의 내용에 소개된 요구조건을 만족시키도록 구현하세요.

제출

def pop_at(self, pos):
        if pos < 1 or pos > self.node_count:
            raise IndexError

        prev_node = None
        if pos == 1:
            popped_node = self.head
            self.head = popped_node.next
        elif pos <= self.node_count:
            prev_node = self.get_at(pos - 1)
            popped_node = prev_node.next
            prev_node.next = popped_node.next

        if pos == self.node_count:
            self.tail = prev_node

        self.node_count -= 1
        return popped_node.data

9강: 연결 리스트 (3)

연결 리스트는 삽입과 삭제가 유연하다는 것이 가장 큰 장점

맨 앞에 dummy node를 추가한 연결 리스트

특정 원소의 바로 다음을 지정하여 원소를 삽입/삭제하는 연산을 정의하기 위해 맨 앞에 dummy node를 추가한다.

더미노드(dummy node):데이터 원소를 담고 있지 않은 노드

head와 tail을 더미 노드로 구현하면 좀더 깔끔하게 작성할 수 있다.

class Node:
	def __init__(self, item):
		self.data = item
		self.next = None

class LinkedList2:
	def __init__(self):
		self.nodeCount = 0
		self.head = Node(None)
		self.tail = None
		self.head.next = self.tail

	def get_at(self, pos):
    if pos <= 0 or pos > self.node_count:
        return None
    curr = self.head
    for _ in range(pos - 1):
        curr = curr.next
    return curr

	def insert_after(self, prev, new_node):
    new_node.next = prev.next
    if prev.next is None:
        self.tail = new_node
    prev.next = new_node
    self.node_count += 1
    return True

  def insert_at(self, pos, new_node):
    if pos < 1 or pos > self.node_count + 1:
        return False

    if pos != 1 and pos == self.node_count + 1:
        prev = self.tail
    else:
        prev = self.get_at(pos - 1)
    return self.insert_after(prev, new_node)

insert_at() 메서드에서 prev_node를 구하여 insert_after() 메서드를 호출한다

🏃‍♂️실습: dummy head 를 가지는 연결 리스트 노드 삭제

문제 설명

제 9 강에서 소개된 추상적 자료구조 LinkedList 는 dummy head node 를 가지는 연결 리스트입니다. 이 클래스의 아래와 같은 메서드들을, 강의 내용에 소개된 요구조건을 만족시키도록 구현하세요.

제출

def pop_after(self, prev):
    popped_node = prev.next
    if popped_node.next is None:
        self.tail = prev
    prev.next = popped_node.next
    self.node_count -= 1
	  return popped_node.data

def pop_at(self, pos):
    if pos < 1 or pos > self.node_count:
        raise IndexError

    prev = self.get_at(pos - 1)
    return self.pop_after(prev)

10강: 양방향 연결 리스트

단방향 연결 리스트는 링크가 한 방향으로, 즉 앞에서 뒤로 향하는 방향으로만 연결되어 있다.

양방향 연결 리스트는 앞 노드와 뒤 노드가 서로 연결되어 양방향으로 접근이 가능한 구조이다.

class Node:
    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None

class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

양방향 연결 리스트는 단방향 연결 리스트에 비해 링크를 나타내기 위한 메모리 사용량이 늘어나지만,

뒤에서 앞으로 이동할 수 있어서 앞뒤로 왔다갔다 하면서 작업을 행하는 일을 효율적으로 할 수 있으며

아래와 같이 코드를 깔끔하게 구현할 수 있다.

def insert_after(self, prev, new_node):
    next = prev.next
    new_node.prev = prev
    new_node.next = next
    prev.next = new_node
    next.prev = new_node
    self.node_count += 1
    return True

def insert_at(self, pos, new_node):
    if pos < 1 or pos > self.node_count + 1:
        return False

    prev = self.get_at(pos - 1)
    return self.insert_after(prev, new_node)

양방향으로 연결되어 있어 코드를 조금 개선할 수 있다 → 리스트를 반으로 나누어서 얻고자 하는 pos가 뒤 쪽에 있으면 tail부터 시작하여 시간을 줄일 수 있다.

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        return None

    if pos > self.nodeCount // 2:
        i = 0
        curr = self.tail
        while i < self.nodeCount - pos + 1:
            curr = curr.prev
            i += 1
    else:
        i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

    return curr

🏃‍♂️실습1: 양방향 연결 리스트 역방향 순회

def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result

🏃‍♂️실습2: 양방향 연결 리스트 노드 삽입

def insert_before(self, next, new_node):
        prev = next.prev
        new_node.prev = prev
        new_node.next = next
        prev.next = new_node
        next.prev = new_node
        self.node_count += 1
        return True

🏃‍♂️실습3: 양방향 연결 리스트 노드 삭제

def pop_after(self, prev):
    popped_node = prev.next
    if popped_node.next is None:
        self.tail.prev = prev

    next = popped_node.next
    prev.next = next
    next.prev = prev

    self.node_count -= 1
    return popped_node.data

def pop_before(self, next):
    popped_node = next.prev
    if popped_node.prev is None:
        self.head.next = next

    prev = popped_node.prev
    prev.next = next
    next.prev = prev

    self.node_count -= 1
    return popped_node.data

def pop_at(self, pos):
    if pos < 1 or pos > self.node_count:
        raise IndexError

    next = self.get_at(pos).next
    return self.pop_before(next)

🏃‍♂️실습4: 양방향 연결 리스트 노드 병합

def concat(self, L):
    left_last = self.tail.prev
    right_first = L.head.next

    left_last.next = right_first
    right_first.prev = left_last

    self.tail = L.tail
    self.node_count += L.node_count

11강: 스택

스택(Stack)

후입선출(LIFO) 구조

스택은 선형 배열과 연결 리스트 두 가지를 이용해서 구현할 수 있다.

class ArrayStack:
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def is_empty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

class LinkedListStack:
    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.get_length()

    def is_empty(self):
        return self.size() == 0

    def push(self, item):
        node = Node(item)
        self.data.insert_at(self.size() + 1, node)

    def pop(self):
        return self.data.pop_at(self.size())

    def peek(self):
        return self.data.get_at(self.size()).data

스택 연산

• size() : 현재 스택에 들어 있는 데이터 원소의 수를 구함
• is_empty() : 현재 스택이 비어 있는지를 판단
• push(x) : 원소 x를 스택에 추가
• pop() : 스택에 가장 나중에 저장된 데이터 원소를 제거하고 반환
• peek() : 스택에 가장 나중에 저장된 데이터 원소를 반환

🏃‍♂️실습: 수식의 괄호 검사 (스택) (빈칸)

소괄호(), 중괄호{}, 대괄호[]를 포함할 수 있는 수식을 표현한 문자열 expr 이 인자로 주어질 때, 이 수식의 괄호가 올바르게 여닫혀 있는지를 판단하는 함수 solution() 을 완성하세요.

def solution(expr):
    match = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    S = ArrayStack()
    for c in expr:
        if c in '({[':
            S.push(c)               # 빈칸
        elif c in match:
            if S.is_empty():        # 빈칸
                return False
            else:
                t = match[c]        # 빈칸
                if t != S.pop():    # 빈칸
                    return False
    return S.is_empty()             # 빈칸

12강: 수식의 후위 표기법

중위 표기법(Infix notation): 연산자가 피연산자 들의 사이에 위치

(A + B) * (C + D)

후위 표기법(postfix notation): 연산자가 피연산자들의 뒤에 위치

A B + C D + *

스택을 이용하면 중위 표현식을 후위 표현식으로 표현할 수 있다!

중위 표현식 → 후위 표현식

중위 표현식을 왼쪽부터 한 글자씩 읽어서

1. 피연산자이면 그냥 출력
2. ( 이면 스택에 push
3. ) 이면 ( 이 나올 때까지 스택에서 pop 후 출력
4. 연산자이면 스택에서 이보다 높거나 같은 우선순위의 연산자를 pop 후 출력, 그리고 이 연산자는 스택에 push

모두 읽은 후에 스택에 남아 있는 연산자를 모두 pop 후 출력

예시1) A * B + C → A B * C +

예시2) A + B * C → A B C * +

예시3) A + B + C → A B + C +

⚡괄호의 처리

여는 괄호 ( 는 스택에 push

닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop

여는 괄호의 우선순위는 가장 낮게 설정!

예시4) (A + B) * C → A B + C *

예시5) A * (B + C) → A B C + *

🔥연산자의 우선순위 설정

prec = {
    '*': 3, '/': 3,
    '+': 2, '-': 2,
    '(': 1,
}

🏃‍♂️실습: 중위표현 수식 → 후위표현 수식

class ArrayStack:
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def is_empty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

prec = {
    '*': 3, '/': 3,
    '+': 2, '-': 2,
    '(': 1
}

def solution(S):
    op_stack = ArrayStack()
    result = []
    for c in S:
        if c == '(':
            op_stack.push(c)
        elif c in prec:
            if not op_stack.is_empty():
                while not op_stack.is_empty() and prec[op_stack.peek()] >= prec[c]:
                    result.append(op_stack.pop())
                op_stack.push(c)
            else:
                op_stack.push(c)
        elif c == ')':
            while op_stack.peek() != '(':
                result.append(op_stack.pop())
            op_stack.pop()
        else:
            result.append(c)

    while op_stack.is_empty() is False:
        result.append(op_stack.pop())

    return ''.join(result)

13강: 후위 표기 수식 계산

후위 표기 수식 계산

후위 표기 수식을 왼쪽부터 한 글자씩 읽어서

1. 피연산자이면 스택에 push
2. 연산자이면 스택에 들어있는 피연산자 2개를 꺼내어 연산을 적용하고 결과를 다시 스택에 push

결과가 스택에 남아 있음

🏃‍♂️실습: 후위표현 수식 계산

class ArrayStack:
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def is_empty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

def split_tokens(expr_str):
    tokens = []
    val = 0
    val_processing = False
    for c in expr_str:
        if c == ' ':
            continue
        if c in '0123456789':
            val = val * 10 + int(c)
            val_processing = True
        else:
            if val_processing:
                tokens.append(val)
                val = 0
            val_processing = False
            tokens.append(c)
    if val_processing:
        tokens.append(val)

    return tokens

def infix_to_postfix(token_list):
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }

    op_stack = ArrayStack()
    postfix_list = []

    for c in token_list:
        if c == '(':
            op_stack.push(c)
        elif c in prec:
            if not op_stack.is_empty():
                while not op_stack.is_empty() and prec[op_stack.peek()] >= prec[c]:
                    postfix_list.append(op_stack.pop())
                op_stack.push(c)
            else:
                op_stack.push(c)
        elif c == ')':
            while op_stack.peek() != '(':
                postfix_list.append(op_stack.pop())
            op_stack.pop()
        else:
            postfix_list.append(c)

    while op_stack.is_empty() is False:
        postfix_list.append(op_stack.pop())

    return postfix_list

def postfix_eval(token_list):
    num_stack = ArrayStack()

    for t in token_list:
        if isinstance(t, int):
            num_stack.push(t)
        else:
            if t == '+':
                num_stack.push(num_stack.pop() + num_stack.pop())
            elif t == '-':
                num_stack.push(-num_stack.pop() + num_stack.pop())
            elif t == '*':
                num_stack.push(num_stack.pop() * num_stack.pop())
            elif t == '/':
                num_stack.push(1 / num_stack.pop() * num_stack.pop())

    return num_stack.pop()

def solution(expr):
    tokens = split_tokens(expr)
    postfix = infix_to_postfix(tokens)
    val = postfix_eval(postfix)
    return val

14강: 큐

선입선출(FIFO) 구조

큐는 스택과 동일하게 선형 배열과 연결 리스트 두 가지를 이용해서 구현할 수 있다.

class ArrayStack:
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def is_empty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)

    def peek(self):
        return self.data[0]

class LinkedListStack:
    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.get_length()

    def is_empty(self):
        return self.size() == 0

    def enqueue(self, item):
        node = Node(item)
        self.data.insert_at(self.size() + 1, node)

    def dequeue(self):
        return self.data.pop_at(1)

    def peek(self):
        return self.data.get_at(1).data

큐 연산

• size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함
• is_empty() : 현재 큐가 비어 있는지를 판단
• enqueue() : 데이터 원소를 큐에 넣는 동작
• dequeue() : 데이터 원소를 꺼내는 동작
• peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환

🏃‍♂️실습: 양방향 연결 리스트로 규현하는 큐 (빈칸)

from .DoublyLinkedList import DoublyLinkedList

class LinkedListQueue:
    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.getLength()                        # 빈칸

    def isEmpty(self):
        return self.data.getLength() == 0                   # 빈칸

    def enqueue(self, item):
        node = Node(item)
        return self.data.insertAt(self.size() + 1, node)    # 빈칸

    def dequeue(self):
        return self.data.popAt(1)                           # 빈칸

    def peek(self):
        return self.data.getAt(1).data                      # 빈칸

15강: 환형 큐

큐의 활용

• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적(Asynchronously)으로 일어나는 경우
• 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
• 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

환형 큐(Circular Queue)

정해진 개수의 저장 공간을 빙 돌려가며 이용

큐가 가득차면 더이상 원소를 넣을 수 없음

→ 큐 길이를 기억하고 있어야 함!

환형 큐 연산

큐 연산에서 is_full()(큐에 데이터 원소가 꽉 차 있는 지를 판단) 메서드 추가

🏃‍♂️실습: 환형 큐 구현 (빈칸)

class CircularQueue:
    def __init__(self, n):
        self.maxCount = n
        self.data = [None] * n
        self.count = 0
        self.front = -1
        self.rear = -1

    def size(self):
        return self.count

    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.count == self.maxCount

    def enqueue(self, x):
        if self.is_full():
            raise IndexError('Queue full')
        self.rear = (self.rear + 1) % self.maxCount         # 빈칸
        self.data[self.rear] = x
        self.count += 1

    def dequeue(self):
        if self.is_empty():                                 # 빈칸
            raise IndexError('Queue empty')

        self.front = (self.front + 1) % self.maxCount       # 빈칸
        x = self.data[self.front]                           # 빈칸
        self.count -= 1
        return x

    def peek(self):
        if self.is_empty():
            raise IndexError('Queue empty')
        return self.data[(self.front + 1) % self.maxCount]  # 빈칸

16강: 우선순위 큐

우선순위 큐(Priority Queues)

큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식

우선순위 큐의 구현은

• enqueue 할 때 우선순위 순서를 유지하도록 하는것이 복잡도와 구현의 편의성 측면에서 더 유리!
• 선형 배열 보다는 연결 리스트를 이용하는 것이 시간적으로 더 유리!

🏃‍♂️실습: 우선순위 큐의 enqueue 연산 구현

from DoublyLinkedList import DoublyLinkedList, Node

class PriorityQueue:
    def __init__(self):
        self.queue = DoublyLinkedList()

    def size(self):
        return self.queue.get_length()

    def is_empty(self):
        return self.size() == 0

    def enqueue(self, x):
        newNode = Node(x)
        curr = self.queue.head                                          # 빈칸
        while curr.next.data is not None and curr.next.data[0] > x[0]:  # 빈칸
            curr = curr.next
        self.queue.insert_after(curr, newNode)                          # 빈칸

    def dequeue(self):
        return self.queue.pop_at(self.queue.get_length())

    def peek(self):
        return self.queue.get_at(self.queue.get_length()).data

17강: 트리

트리(Tree)

정점(Node)과 간선(Edge)을 이용하여 데이터의 배치 형태를 추상화한 자료구조

트리 관련 용어

• 노드 (nodes)

• 간선 (edges)

• 루트 노드 (root node), 말단 노드 (leaf nodes), 내부 노드 (internal nodes)

• 부모 (parent) 노드와 자식 (child) 노드

• 노드의 수준 (level)

  root 노드로부터 거쳐야 하는 간선의 개수

  root 노드부터 0으로 시작

• 트리의 높이 (height) = 수준(level)의 최대값 + 1 (또는, 깊이 (depth)라고도 함)

• 부분 트리 (서브트리; subtrees)

  트리 내에서 root 노드를 제외한 다른 노드로부터 시작하는 트리

• 노드의 차수 (degree)

  자식 노드의 수

• 이진 트리 (binary trees)

  모든 노드의 차수가 2 이하인 트리

  재귀적으로 정의 가능 → 빈 트리이거나, 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리(단, 모든 서브트리 또한 이진 트리)

• 포화 이진 트리 (full binary trees)

  모든 레벨에서 노드들이 모두 채워져 있는 이진 트리

  (높이가 $k$이고 노드의 개수가 $2^k -1$ 인 이진 트리)

• 완전 이진 트리 (complete binary trees)

  높이가 $k$인 완전 이진 트리는 다음 조건을 만족하여야 함

  1. 레벨 $k-2$ 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
  2. 레벨 $k-1$ 에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리

18강: 이진 트리

이진 트리(Binary Tree)

모든 노드의 차수가 2 이하인 트리

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

    def size(self):
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1

class BinaryTree:
    def __init__(self, r):
        self.root = r

    def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0

이진 트리 연산

• size() : 현재 트리에 포함되어 있는 노드의 수를 구함
• depth() : 현재 트리의 깊이 (또는 높이) 를 구함

이진 트리 순회 (Traversal)

• 깊이 우선 순회(Depth First Traversal)
  • 중위 순회(In-order Traversal)
  • 전위 순회(Pre-order Traversal)
  • 후위 순회(Post-order Traversal)
• 너비 우선 순회(Breadth First Traversal)

깊이 우선 순회는 재귀적 방법이 적합하지만, 너비 우선 순회는 적합하지 않음!

🏃‍♂️실습1: 이진트리의 depth() 연산 구현

class Node:

		# ...

    def depth(self):
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return max(l, r) + 1

class BinaryTree:

		# ...

    def depth(self):
        return self.root.depth() if self.root else 0

🏃‍♂️실습2: 이진트리의 전위순회 연산 구현

class Node:

		# ...

    def preorder(self):
        traversal = []
        traversal.append(self.data)
        traversal += self.left.preorder() if self.left else []
        traversal += self.right.preorder() if self.right else []
        return traversal

class BinaryTree:

		# ...

    def preorder(self):
        return self.root.preorder() if self.root else []

🏃‍♂️실습3: 이진트리의 후위순회 연산 구현

class Node:

		# ...

    def postorder(self):
        traversal = []
        traversal += self.left.postorder() if self.left else []
        traversal += self.right.postorder() if self.right else []
        traversal.append(self.data)
        return traversal

class BinaryTree:

		# ...

    def postorder(self):
        return self.root.postorder() if self.root else []

19강: 이진 트리 - 너비 우선 순회

너비 우선 순회(Breath First Traversal)

• 수준(level)이 낮은 노드를 우선으로 방문
• 같은 수준의 노드들 사이에는
  • 부모 노드의 방문 순서에 따라 방문
  • 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문

너비 우선 순회는 재귀적 방법이 적합하지 않음!

→ 큐(queue)를 이용

너비 우선 순회 알고리즘 구현

1. 초기화: traversal ← 빈 리스트 / q ← 빈 큐
2. 트리가 비어 있지 않으면 root node를 q에 추가 (enqueue)
3. q가 비어 있지 않은 동안
   1. node ← q에서 원소를 추출 (dequeue)
   2. node를 방문
   3. node의 왼쪽, 오른쪽 자식이 존재하면 차례로 q에 추가 (enqueue)
4. q가 빈 큐가 되면 모든 노드 방문 완료

🏃‍♂️실습: 이진 트리의 너비 우선 순회

class ArrayQueue:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)

    def peek(self):
        return self.data[0]

class Node:

    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None

class BinaryTree:

    def __init__(self, r):
        self.root = r

    def bft(self):
        traversal, q = [], ArrayQueue()
        if self.root:
            q.enqueue(self.root)
        while q.isEmpty() is False:
            node = q.dequeue()
            traversal.append(node.data)
            if node.left:
                q.enqueue(node.left)
            if node.right:
                q.enqueue(node.right)
        return traversal

20강: 이진 탐색 트리

이진 탐색 트리(Binary Search Tree)

모든 노드에 대해서,

• 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 적고
• 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰

성질을 만족하는 이진 트리

class Node:

    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None

class BinSearchTree:

    def __init__(self):
        self.root = None

정렬된 배열을 이용한 이진 탐색과 비교했을때

이진 탐색 트리를 이용하면 데이터 원소의 추가와 삭제가 용이 (하지만 공간 소요가 큼)

이진 탐색 트리는 중복값을 삽입할 수 없음!

항상 시간 복잡도가 O(logn) 나오는 것이 아님. 그렇지 않은 경우가 존재!

계속 증가하는 값을 삽입하거나 감소하는 값을 삽입하여 한 쪽으로 치우쳐진 트리가 만들어지는 경우가 아닐까? 그래서 보완하기 위해 나온 게 AVL 트리, 레드-블랙 트리였던 것 같은데...🤔

이진 탐색 트리 연산

• insert(key, data) : 트리에 주어진 데이터 원소를 추가
• remove(key) : 특정 원소를 트리로부터 삭제
• lookup(key) : 특정 원소를 검색
• inorder() : 키의 순서대로 데이터 원소를 나열
• min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색

이진 탐색 트리에서의 원소 삽입

1. 키를 비교하여 작으면 왼쪽으로, 크면 오른쪽으로 이동하여 각 방향의 노드가 존재하는 지 검사
   1. 노드가 존재하지 않으면 새로운 노드 생성
   2. 노드가 존재하면 해당 노드로부터 다시 insert() 메서드 호출
2. 같은 키 값이 존재할 경우 오류 발생

🏃‍♂️실습: 이진 탐색 트리의 원소 삽입 연산 구현

class Node:

    # ...

    def insert(self, key, data):
        if self.key > key:
            if self.left is None:
                self.left = Node(key, data)
            else:
                return self.left.insert(key, data)
        elif self.key < key:
            if self.right is None:
                self.right = Node(key, data)
            else:
                return self.right.insert(key, data)
        else:
            raise KeyError
        return True

class BinSearchTree:

    # ...

    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)

21강: 이진 탐색 트리 (2)

이진 탐색 트리에서의 원소 삭제

1. 키를 이용해서 노드를 찾는다
   • 해당 키의 노드가 없으면, 삭제할 것도 없음
   • 찾은 노드의 부모 노드도 알고 있어야 함 (아래 2번을 진행하기 위해)
2. 찾은 노드를 제거하고도 이진 탐색 트리 구조를 유지하기 위해 트리의 구조를 정리

이진 탐색 트리 구조의 유지

삭제되는 노드가

1. 말단(leaf) 노드인 경우
   1. 그 노드를 삭제
   2. 부모 노드의 링크를 조정(left 혹은 right 값을 None 으로 설정)
2. 자식을 하나 가지고 있는 경우
   1. 삭제되는 노드 자리에 그 자식을 대신 배치하고 삭제
   2. 부모 노드의 링크를 조정(left 혹은 right 값을 배치된 자식 노드로 설정)
3. 자식을 둘 가지고 있는 경우
   1. 삭제되는 노드보다 바로 다음(작거나 큰) 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 배치하고 대신 삭제
   2. 부모 노드의 링크를 조정(left 혹은 right 값을 배치된 자식 노드로 설정)

*삭제되는 노드가 root node 인 경우 → 대신 들어오는 자식이 새로 root가 됨 (처리 필요)

이진 탐색 트리가 별로 효율적이지 못한 경우

트리가 한쪽으로 치우쳐진 경우 → O(n) 소요

높이의 균형을 유지함으로써 O(logn)의 시간 복잡도를 보장해주는 이진 탐색 트리는 다음과 같다.

• AVL Tree
• Red-Black Tree

하지만, 삽입/삭제가 보다 복잡함

🏃‍♂️실습: 이진 탐색 트리에서 노드의 삭제 연산 구현

def remove(self, key):
    node, parent = self.lookup(key)
        if node:
            nChildren = node.countChildren()
            # The simplest case of no children
            if nChildren == 0:
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # parent.left 또는 parent.right 를 None 으로 하여
                # leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
                if parent:
                    if node == parent.left:
                        parent.left = None
                    else:
                        parent.right = None
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 를 None 으로 하여 빈 트리로 만듭니다.
                else:
                    self.root = None
            # When the node has only one child
            elif nChildren == 1:
                # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
                # 그 자식을 어떤 변수가 가리키도록 합니다.
                chileNode = node.left if node.left else node.right

                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if parent.left == node:
                        parent.left = chileNode
                    else:
                        parent.right = chileNode
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = chileNode
            # When the node has both left and right children
            else:
                parent = node
                successor = node.right
                # parent 는 node 를 가리키고 있고,
                # successor 는 node 의 오른쪽 자식을 가리키고 있으므로
                # successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
                # 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
                # 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아냅니다.
                while successor.left:
                    parent, successor = successor, successor.left
                # 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입합니다.
                node.key = successor.key
                node.data = successor.data
                # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
                # 그에 따라 parent.left 또는 parent.right 를
                # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
                if parent.left == successor:
                    parent.left = successor.left
                else:
                    parent.right = successor.right
                    
            return True

        else:
            return False

22강: 힙

힙(Heap)

이진 트리의 한 종류

1. 완전 이진 트리 → (말단 노드가 왼쪽부터 차례로 채워져야 함)
2. 루트 노드가 언제나 최댓값 (또는 최솟값) 을 가짐
   • 최대 힙 (max heap) (또는 최소 힙(min heap))

모든 부모 노드는 자식 노드보다 작은 값 (또는 큰 값) 을 가짐

→ 재귀적으로도 정의됨 (힙 내의 모든 서브트리 또한 최대 힙)

힙은 중복값 삽입 가능!

🔥이진 탐색 트리 vs 힙

이진 탐색 트리는 특정 값을 검색하는 데에 사용

힙은 최대/최소값을 찾는 데에 사용

배열을 이용하여 구현하는 힙

(root 노드 번호를 1로 설정)

노드 번호 k를 기준으로

• 왼쪽 자식의 번호: 2 * k
• 오른쪽 자식의 번호: 2 * k + 1
• 부모 노드의 번호: k // 2

힙은 완전 이진 트리 성질을 가지기 때문에 배열로 구현해도 나쁘지 않다.

class MaxHeap:

    def __init__(self):
        self.data = [None]

최대 힙에 원소 삽입

1. 트리의 마지막 자리에 새로운 원소를 저장
2. 부모 노드와 키 값을 비교하여 서로 교환 (아래에서 위로)

🏃‍♂️실습: 최대 힙에 새로운 원소 삽입

def insert(self, item):
    k = len(self.data)
    self.data.append(item)

    while k // 2 > 0:
        if self.data[k // 2] < self.data[k]:
            self.data[k // 2], self.data[k] = self.data[k], self.data[k // 2]
        k //= 2

23강: 힙 (2)

최대 힙에서 원소 삭제

1. 루트 노드의 제거
2. 트리 마지막 자리 노드를 루트 노드의 자리에 배치
3. 자식 노드와 키 값을 비교하여 서로 교환 (위에서 아래로)

def remove(self):
    if len(self.data) > 1:
        self.data[1], self.data[-1] = self.data[-1], self.data[1]
        data = self.data.pop(-1)
        self.maxHeapify(1)
    else:
        data = None
    return data

최대/최소 힙의 응용

1. 우선순위 큐 (priority queue)
   • 16강 양방향 연결 리스트 이용 구현과 비교해서 시간적으로 더 효율적임 → $O(logn)$
2. 힙 정렬 (heap sort)
   • 원소들이 삭제된 순서가 원소들의 정렬 순서 → $O(nlogn)$

🏃‍♂️실습: 최대 힙에서의 원소 삭제

def remove(self):
    if len(self.data) > 1:
        self.data[1], self.data[-1] = self.data[-1], self.data[1]
        data = self.data.pop(-1)
        self.maxHeapify(1)
    else:
        data = None
    return data

def maxHeapify(self, i):
    smallest = i
    left = 2 * i
    right = 2 * i + 1

    if left < len(self.data) and self.data[left] > self.data[smallest]:
        smallest = left
    if right < len(self.data) and self.data[right] > self.data[smallest]:
        smallest = right

    if smallest != i:
        self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
        self.maxHeapify(smallest)