누런강냉이

수식의 중위 표기법과 후위 표기법

중위 표기법 (infix notation)

(A+B) * (C+D)

   1   3    2

연산자가 피연산자들 사이에 위치하는 것

후위 표기법 (postfix notation)

AB + CD + *

   1     2    3

연산자가 피연산자들 뒤에 위치. 괄호가 필요 없다.

스택을 이용해 중위 표기법을 후위 표기법으로 변경하기

괄호 처리

여는 괄호는 스택에 push

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

여는 괄호의 우선 순위는 가장 낮게 설정하도록 한다. 

알고리즘 설계

1. 연산자 우선순위 설정
   • prec = { '*':3, '/':3, '+':2, '-':2, '(':1 }
2. 중위 표현식을 왼쪽부터 한 글자씩 읽어
   • 피연산자면 그냥 출력
   • '('면 스택에 push
   • ')'면 '('가 나올 때까지 스택에서 pop
   • 출력 연산자이면 스택에서 이보다 높거나 같은 우선순위 것들을 pop, 출력 그리고 이 연산자는 스택에 push
   • 스택에 남아 있는 연산자는 모두 pop, 출력

코드 구현

class ArrayStack:

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

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

    def isEmpty(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):
    opStack = ArrayStack()
    answer=''

    for i in S:
        if i not in prec and i!=')': #비연산자면 바로 출력
            answer+=i
        else:
            if opStack.isEmpty() or i=='(': #스택이 비어있거나 '('연산자일 시 바로 스택에 push
                opStack.push(i)
            else:
                if i==')': #'('가 나올때까지 스택에서 pop
                    while opStack.peek()!='(':
                        answer+=opStack.pop()
                    opStack.pop() #'('빼기
                else:
                    while opStack.size()!=0 and prec[opStack.peek()]>=prec[i]:
                        answer+=opStack.pop()
                    opStack.push(i)

    for i in range(opStack.size()):
        answer+=opStack.pop()
                    
    return answer            

후위 표기 수식 계산

후위 표기된 수식을 계산하기

알고리즘 설계

1. 후위 표현식을 왼쪽부터 한 글자씩 읽는다
2. 피연산자면 스택에 push한다
3. 연산자를 만나면 스택에서 pop한다. =>(1)
4. 또 pop한다. =>(2)
5. (2) 연산 (1)을 계산한다. 이 결과를 스택에 push한다.
6. 수식의 끝에 도달하면 스택에서 pop한다. => 계산 결과

코드 구현

class ArrayStack:

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

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

    def isEmpty(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 splitTokens(exprStr):
    tokens = []
    val = 0
    valProcessing = False
    for c in exprStr:
        if c == ' ':
            continue
        if c in '0123456789':
            val = val * 10 + int(c)
            valProcessing = True
        else:
            if valProcessing:
                tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
    if valProcessing:
        tokens.append(val)

    return tokens


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

    opStack = ArrayStack()
    postfixList = []
    
    for token in tokenList:
        if type(token) is int:
            postfixList.append(token)
        elif token=='(':
            opStack.push(token)
        elif token==')':
            while opStack.peek()!='(':
                postfixList.append(opStack.pop())
            opStack.pop()
        else:
            while opStack.size()!=0 and prec[opStack.peek()]>=prec[token]:
                postfixList.append(opStack.pop())
            opStack.push(token)
    
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())

    return postfixList


def postfixEval(tokenList):
    valStack = ArrayStack()
    
    for token in tokenList:
        if type(token) is int:
            valStack.push(token)
        elif token=='*':
            a=valStack.pop()
            b=valStack.pop()
            valStack.push(b*a)
        elif token=='/':
            a=valStack.pop()
            b=valStack.pop()
            valStack.push(b/a)
        elif token=='+':
            a=valStack.pop()
            b=valStack.pop()
            valStack.push(b+a)
        elif token=='-':
            a=valStack.pop()
            b=valStack.pop()
            valStack.push(b-a)
            
    return valStack.pop()


def solution(expr):
    tokens = splitTokens(expr)
    postfix = infixToPostfix(tokens)
    val = postfixEval(postfix)
    return val

너무 지저분해 보인다..^^;

큐

큐란? 선입선출(FIFO : First In First Out)의 특징을 갖는 선형 자료구조 (ex : 영화관 입장 / 식당 입장 대기열)

큐의 동작

그림 출처 : https://velog.io/@junhok82/Queue

큐의 추상적 자료구조 구현

연산 정의

size() - 현재 큐에 들어 있는 데이터 원소의 수 - O(1)

isEmpty() - 현재 큐가 비어있는지 판단 - O(1)

enqueue(x) - 데이터 원소 x를 큐에 추가 - O(1)

dequeue() - 큐의 맨 앞에 저장된 데이터 원소 제거 및 반환 - O(n) 앞의 원소를 제거 후, 뒤의 원소들을 다 앞으로 한 칸씩 당겨주는 과정에서 n만큼의 시간이 소요된다.

peek() - 큐의 맨 앞에 저장된 데이터 원소 반환 (제거 X) - O(1)

배열을 이용해 구현

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.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 __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


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


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


    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


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError('Index out of range')

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)


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

        self.nodeCount += L.nodeCount


class LinkedListQueue:

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

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


    def isEmpty(self):
        return self.data.nodeCount==0


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


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


    def peek(self):
        return self.data.head.next.data

큐 활용

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

환형 큐

연산 정의

• size() - 현재 큐에 들어 있는 데이터 원소의 수
• isEmpty() - 현재 큐가 비어있는지 판단
• isFull() - 큐의 데이터 원소가 꽉 차 있는지 판단
• enqueue(x) - 데이터 원소 x를 큐에 추가
• dequeue() - 큐의 맨 앞에 저장된 데이터 원소 제거 및 반환
• peek() - 큐의 맨 앞에 저장된 데이터 원소 반환 (제거 X)

배열로 구현한 환형 큐

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 isEmpty(self):
        return self.count == 0

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

    def enqueue(self, x):
        if self.isFull():
            raise IndexError('Queue full')
        self.rear = self.rear + 1

        self.data[self.rear] = x
        self.count += 1

    def dequeue(self):
        if self.isEmpty():
            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.isEmpty():
            raise IndexError('Queue empty')
        return self.data[(self.front + 1) % self.maxCount]

우선순위 큐

우선순위 큐란? 큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식 (활용되는 ex : 운영체제의 CPU 스케쥴러)

우선순위 큐의 구현

두 가지 방식

1. Enqueue할 때 우선순위 순서를 유지하도록
   • 조금 더 유리하다. 시간 복잡도가 조금 더 짧다.
2. Dequeue할 때 우선순위 높은 것을 선택

두 가지 재료

1. 선형 배열 이용
2. 연결 리스트 이용
   • 중간에 데이터 삽입하는 일이 빈번히 발생해 연결 리스트가 더 유리

연결 리스트를 이용하여 우선순위 큐 구현

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 __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


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


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


    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


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)


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

        self.nodeCount += L.nodeCount


class PriorityQueue:

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


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

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

    def enqueue(self, x):
        newNode = Node(x)
        curr = self.queue.head.next

        while curr.next!=self.queue.tail and x<curr.next.data:
            curr = curr.next
        self.queue.insertAfter(curr, newNode)

    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())

    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data

트리

트리란? node와 edge를 이용해 데이터의 배치 형태를 추상화한 자료 구조

트리 구조

그림 출처 : https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

• 루트 노드 : 가장 위에 위치한 노드
• 리프 노드 : 가지를 치는 곳이 없는 노드
• 내부 노드 : 루트 노드도 리프 노드도 아닌 노드
• 부모 노드와 자식 노드
  • 노드 6은 노드 5와 11의 부모 노드이다.
  • 노드 5와 11은 노드 6의 자식 노드이다.
• 형제 노드(Sibling node)
  • 노드 5와 11은 형제 노드이다.
• 조상 노드(ancestor)와 후손 노드(descendant node)
  • 노드 5의 조상 노드는 2, 7, 6이다.
  • 루트 노드 2는 자기 자신을 제외하고 모든 노드가 후손 노드이다.
• 노드의 수준(Level) : 루트 노드로부터 해당 노드에 이를 때까지 지나치는 간선의 수
  • Level 0 : 2
  • Level 1 : 7, 5
  • Level 2 : 2, 6, 9
  • Level 3 : 5, 11, 4
• 트리의 높이 = 최대 수준(level) + 1 (깊이라고도 함)
• 부분트리 (서브트리 - Subtree) : 트리에서 노드 한 개로부터 후손들을 빼내면 그것을 서브트리라고 한다.
• 노드의 차수 (Degree) = 자식 (서브트리)의 수
  
  • 노드 6의 차수는 2이다.

이진 트리

이진 트리란? 모든 노드의 차수가 2 이하인 트리 (앞서 예시로 보여준 트리의 그림같은 경우에도 이진 트리이다.)

재귀적으로 정의할 수 있다. => 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리

이진 트리의 종류

• 포화 이진 트리 : 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
  • 높이가 k
  • 노드의 개수가 2^k-1
• 완전 이진 트리
  
  • 높이 k인 완전 이진 트리
  • 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
  • 레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리

그림 출처 : https://limkydev.tistory.com/134

연산 정의

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

이진 트리 순회

• 깊이 우선 순회 (재귀적 방식 적합)
  • 중위 순회
    • Left subtree
    • 자기 자신
    • Right subtree
  • 전위 순회
    • 자기 자신
    • Left subtree
    • Right subtree
  • 후위 순회
    • Left subtree
    • Right subtree
    • 자기 자신

• 넓이 우선 순회 (재귀적 방식 부적합. 큐 이용)
  • 수준이 낮은 노드 우선 방문
  • 같은 수준 노드들 사이에선 
    • 부모 노드 방문 순서에 따라 방문
    • 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
  • 알고리즘 설계
    • traversal은 빈 리스트로 q는 빈 큐로 초기화
    • 빈 트리가 아니면 root node에 q 추가
    • q가 비어 있지 않은 동안
      • node <- q에서 원소를 추출 (deque)
      • node 방문
      • node의 왼쪽, 오른쪽 자식들을 q에 추가
      • q가 빈 큐가 되면 모든 노드 방문 완료

깊이 우선 순회 코드 구현

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


    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
        
    def inorder(self): #중위 순회
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def preorder(self): #전위 순회
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal +=self.left.preorder()
        if self.right:
            traversal +=self.right.preorder()
        return traversal
    
    def postorder(self): #후위 순회 #후위 순회
        traversal = []
        if self.left:
            traversal += self.left.postorder()
        if self.right:
            traversal += self.right.postorder()
        traversal.append(self.data)
        return traversal


class BinaryTree:

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

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


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


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

넓이 우선 순회 코드 구현

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 not q.isEmpty():
            node = q.dequeue()
            traversal.append(node.data)
            
            if node.left:
                q.enqueue(node.left)
            if node.right:
                q.enqueue(node.right)
                
        return traversal

이진 탐색 트리

모든 노드에 대해 

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

그림 출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

정렬된 배열과 이진 탐색과 비교

(장점) 이진 탐색이 정렬된 배열보다 데이터 원소의 추가, 삭제가 더 용이하다.

(단점) 공간 소요가 크다.

연산 정의

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

이진 탐색 트리에서 원소 삭제 알고리즘

1. 키(key)를 이용해 노드를 찾는다.
   • 해당 키의 노드가 없으면 삭제할 것도 없다.
   • 찾은 노드의 부모 노드도 알고 있어야 한다.
2. 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리한다.
   • 삭제되는 노드가
     • 말단 노드인 경우
       • 그냥 그 노드를 없애면 된다. 
       • 부모 노드의 링크를 조정
     • 자식을 하나 가지고 있는 경우
       • 삭제되는 노드 자리에 그 자식을 대신 배치
       • 자식이 왼쪽에 있는지 오른쪽에 있는지를 알고 있어야 한다.
       • 부모 노드의 링크를 조정
     • 자식을 둘 가지고 있는 경우
       • 삭제되는 노드보다 바로 다음 키를 갖는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치

코드 구현

class Node:

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


    def insert(self, key, data):
        if key < self.key:
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif key > self.key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
        else:
            raise KeyError('Key %s already exists.' % key)


    def lookup(self, key, parent=None):
        if key < self.key:
            if self.left:
                return self.left.lookup(key, self)
            else:
                return None, None
        elif key > self.key:
            if self.right:
                return self.right.lookup(key, self)
            else:
                return None, None
        else:
            return self, parent


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


    def countChildren(self):
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count


class BinSearchTree:

    def __init__(self):
        self.root = None


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


    def lookup(self, key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None


    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 parent.left == node:
                        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:
                # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
                # 그 자식을 어떤 변수가 가리키도록 합니다.
                if node.left:
                    child = node.left
                else:
                    child = node.right
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if parent.left == node:
                        parent.left = child
                    else:
                        parent.right = child
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = child
            # 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
                if parent.left == successor:
                    parent.left =successor.right
                else:
                    parent.right = successor.right
                    
                # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
                # 그에 따라 parent.left 또는 parent.right 를
                # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
                

            return True

        else:
            return False


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

보다 좋은 성능의 이진 탐색 트리들

• AVL tree - https://ko.wikipedia.org/wiki/AVL_%ED%8A%B8%EB%A6%AC
• Red-black tree - https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

힙(heap)

힙이란? 이진 트리의 한 종류

1. 루트 노드가 언제나 최댓값 또는 최솟값을 가진다.
   • 최대 힙(max heap), 최소 힙(min heap)
2. 완전 이진 트리여야 한다.

그림 출처 : https://guides.codepath.com/compsci/Heaps

이진 탐색 트리와의 차이

1. 이진 탐색 트리는 완전히 크기 순으로 정렬되어 있으나, 최대힙/최소힙은 그렇지 않다.
2. 이진 탐색 트리는 특정 키 값을 가지는 원소를 빠르게 검색할 수 있으나, 힙은 특정한 키 값이 어느 트리에 들어있는가를 알아내는데 좋은 방법이 없다.
3. 힙은 이진 탐색 트리에 비해 완전 이진 트리여야 한다는 부가의 제약 조건이 있다.

연산 정의

• __init__() - 빈 최대 힙 생성
• insert(item) - 새로운 원소 삽입
• remove() - 최대 원소 (root node) 반환과 동시에 삭제

배열을 이용한 최대힙의 표현

노드 번호 m을 기준으로

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

완전 이진 트리이므로 노드의 추가 / 삭제는 마지막 노드에서만 이뤄진다.

최대 힙에 원소 삽입

1. 트리의 마지막 자리에 새로운 원소 임시 저장
2. 부모 노드와 키 값을 비교해 위로 이동

복잡도 = 부모 노드와의 대소 비교 최대 회수 => log₂n

∴ 최악 복잡도 O(logn)의 삽입 연산

최대 힙에 원소 삭제

1. 루트 노드 제거 - 이것이 원소들 중 최댓값
2. 트리 마지막 자리 노드를 임시로 루트 노드 자리에 배치
3. 자식 노드들과 값을 비교해 아래로 이동
   • 자식이 둘이 있다면 더 큰 값을 기준으로 아래로 이동하게 된다.

복잡도 = 자식 노드들과의 대소 비교 최대 회수 => 2log₂n

∴ 최악 복잡도 O(logn)의 삭제 연산

코드 구현

class MaxHeap:

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


    def insert(self, item):
        self.data.append(item)
        idx = len(self.data)-1
        
        while idx != 1:
            parent = idx//2
            
            if self.data[parent] < self.data[idx]:
                self.data[parent],self.data[idx] = self.data[idx], self.data[parent]
                idx = parent
            else:
                break
                
    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):
        # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        left = 2*i

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = 2*i+1

        greatest = i
        
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left<len(self.data) and self.data[left]>self.data[greatest]:            
        # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            greatest=left
        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right<len(self.data) and self.data[right]>self.data[smallest]:            
        # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.      
            greatest=right

        if greatest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[i],self.data[greatest]=self.data[greatest],self.data[i]

            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(greatest)

최대/최소 힙 응용

1. 우선 순위 큐
   • Enqueue할 때 '느슨한 정렬'을 이루도록 한다. - O(logn)
   • Dequeue할 때 최댓값을 순서대로 추출 - O(logn)
2. 힙 정렬
   • 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 - O(logn)
   • 삽입이 끝나면 힙이 비게 될 때까지 하나씩 삭제 : O(logn)
   • 원소들 삭제된 순서가 원소들의 정렬 순서
   • 정렬 알고리즘 복잡도 - O(nlogn)

그림 출처 : ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC

힙 정렬 코드 구현

def heapsort(unsorted):
    H = MaxHeap()
    for item in unsorted:
        H.insert(item)
    sorted = []
    d = H.remove()
    while d :
        sorted.append(d)
        d = H.remove()
    return sorted