Trees

Python Algorithm Study - Week 9, 10

Algorithmpython

2017-09-14


Problem Solving with Algorithms and Data Structures using Python ์ฑ…์„ ์ฝ์œผ๋ฉฐ ์Šคํ„ฐ๋””ํ•œ ๋‚ด์šฉ์„ ์ •๋ฆฌํ•˜์—ฌ ์—ฐ์žฌํ•ฉ๋‹ˆ๋‹ค.


1. Tree Data Structure

  • You can move entire sections of a tree (called a subtree) to a different position in the tree without affecting the lower levels of the hierarchy
  • Payload : In computing and telecommunications, the payload is the part of transmitted data that is the actual intended message. The payload excludes any headers or metadata sent solely to facilitate payload delivery
{  
   "data":{  
      "message":"Hello, world!"
   }
}

The string "Hello, world!" is the payload, while the rest is protocol overhead.

  1. List of Lists representation

    • ๋นˆ ๋ฆฌ์ŠคํŠธ๋“ค์ด ์žˆ๋Š” ์ด์œ ๋Š” insertRight, insertLeft ๊ฐ™์€ reference์˜ ์ž๋ฆฌ ์—ญํ• ์„ ํ•˜๊ธฐ ๋•Œ๋ฌธ.
myTree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]


2. Priority Queues with Binary Heaps

  1. Priority Queue

    • Queue๋Š” queue์ธ๋ฐ ์ •๋ ฌ์ด ๋˜์–ด ์žˆ๋Š” queue (์—ฌ๊ธฐ์„œ๋Š” ์˜ค๋ฆ„์ฐจ์ˆœ)
    • How to enqueue : sorting ์„ ํ•˜๋ฉด์„œ enqueue ๋œ๋‹ค. (the logical order of items inside a queue is determined by their priority)
    • ์›๋ž˜๋Š” insert(O(n)) & sort(O(nlogn)) ์„ ๊ฑฐ์ณ์•ผ ํ•˜์ง€๋งŒ binary heap์„ ์‚ฌ์šฉํ•˜๋ฉด O(logn)์œผ๋กœ ๊ฐ€๋Šฅํ•˜๋‹ค. ์™œ๋ƒ๋ฉด ๋ถ€๋ชจ๋ž‘๋งŒ ๋น„๊ตํ•˜๋ฉด๋˜๊ณ  sibling๊ณผ์˜ ๋Œ€์†Œ๋Š” ๋ฌด์‹œํ•ด๋„ ๋˜๊ธฐ ๋•Œ๋ฌธ์—. (height๊ฐ€ n์ธ tree์˜ size๋Š” 2^n+x)
  2. Heap

    • ์ตœ๋Œ“๊ฐ’ ๋˜๋Š” ์ตœ์†Ÿ๊ฐ’์„ ๋นจ๋ฆฌ ์ฐพ๊ธฐ ์œ„ํ•ด ๊ณ ์•ˆ๋œ Complete binary tree.
    • Binary tree : ๋ชจ๋“  ๋ ˆ๋ฒจ์˜ ๋…ธ๋“œ๊ฐ€ ์ตœ๋Œ€ ๋‘๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง„ ํŠธ๋ฆฌ. ์ž์‹๋…ธ๋“œ๋Š” left, right์˜ ์ž๋ฆฌ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค.
    • Complete binary tree : leaf node (๊ฐ€์žฅ ๋ง๋‹จ์˜ ๋…ธ๋“œ)๋ฅผ ์ œ์™ธํ•˜๊ณ ๋Š” ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ '์ฑ„์›Œ์ง„' binary tree / ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ subtree ๋นผ๊ณ ๋Š” left, right๊ฐ€ ๋ชจ๋‘ ์ฑ„์›Œ์ ธ ์žˆ์–ด์•ผํ•จ.
    • Tree representation ์ฒ˜๋Ÿผ ์“ฐ์ง€ ์•Š๊ณ  ๊ทธ๋ƒฅ ๋‹จ์ผ list๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค. ์ด๊ฒƒ์ด binary heapํ˜•ํƒœ๋กœ ๋˜์–ด์žˆ๋‹ค๊ณ  ๋จธ๋ฆฟ ์†์— ์ƒ-์ƒํ•˜๋ฉฐ ์—ฐ์‚ฐ์„ ๊ตฌํ˜„ํ•˜๋ฉด ๋œ๋‹ค.(When we diagram the heap it looks a lot like a tree, but when we implement it we use only a single list)
    • min Heap(์˜ค๋ฆ„์ฐจ์ˆœ) & max Heap(๋‚ด๋ฆผ์ฐจ์ˆœ)
    • Heap sort : O(nlogn)์˜ ์™„์ „ ํž™ํ•œ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค. ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ์ˆœํšŒํ•˜๊ณ (n) ๊ฐ ๋…ธ๋“œ๋ฅผ root์— ๋„์ฐฉํ•  ๋•Œ๊นŒ์ง€ ๋ถ€๋ชจ๋ž‘ ๋Œ€์†Œ๋น„๊ตํ•˜๊ธฐ ๋•Œ๋ฌธ. (* ์ฐธ๊ณ  : Quicksort ๊ฐ€ ํ‰๊ท  O(nlogn), ์ตœ๋Œ€ O(n^2)์ด๋‹ค.)

3. Binary Heap Operations

# Basic operations of binary min heap
BinaryHeap()
insert(k)
findMin()   # ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ๋ฆฌํ„ด๋งŒ ํ•œ๋‹ค.
delMin()    # ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ๋ฆฌํ„ดํ•˜๋ฉด์„œ ์‚ญ์ œํ•œ๋‹ค.
isEmpty()
size()
buildHeap(list) # key ๊ฐ’ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ฐ€์ง€๊ณ  ์ƒˆ๋กœ์šด heap์„ ๋งŒ๋“ ๋‹ค.

4. Binary Heap Implementation

  1. The Structure Property

    • Complete binary tree: leaf node (๊ฐ€์žฅ ๋ง๋‹จ์˜ ๋…ธ๋“œ)๋ฅผ ์ œ์™ธํ•˜๊ณ ๋Š” ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ '์ฑ„์›Œ์ง„' binary tree / ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ subtree ๋นผ๊ณ ๋Š” left, right๊ฐ€ ๋ชจ๋‘ ์ฑ„์›Œ์ ธ ์žˆ์–ด์•ผํ•จ.
      Complete binary tree
    • x // 2 ์˜ ์•„์ฃผ ๊ฐ„๋‹จํ•œ integer division ๋งŒ์œผ๋กœ๋„ ๋ชจ๋“  ๋…ธ๋“œ์˜ ์ž๋ฆฌ๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค(traversing nodes).
    • ์˜ˆ๋ฅผ ๋“ค์–ด, ์–ด๋–ค ๋…ธ๋“œ๊ฐ€ p์˜ ์ž๋ฆฌ์— ์žˆ๋‹ค๊ณ  ํ•  ๋•Œ, ์ด ๋…ธ๋“œ์˜ left child๋Š” 2p ์ž๋ฆฌ์— ์žˆ๋‹ค. right child ์˜ ์ž๋ฆฌ๋Š” 2p+1์ด๋‹ค. ๋‹น์—ฐํžˆ p์˜ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ์ž๋ฆฌ๋Š” p/2์ด๋‹ค.
  2. The Heap Order Property

    • In a heap, for every node x with parent p, the key in p is smaller than or equal to the key in x
  3. Heap Operations
  4. Insert()
    insert
class BinHeap:
    def __init__(self):
        self.heapList = [0] # this zero is not used, but is there so that simple integer division can be used in later methods.
        self.currentSize = 0

    def insert(self,k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def percUp(self,i): # i์—๋Š” currentSize๊ฐ€ ๋“ค์–ด๊ฐ
        while i // 2 > 0:
            if self.heapList[i] < self.heapList[i // 2]: # ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰์— ๋„ฃ์€ ๊ฐ’๋ณด๋‹ค ๋ถ€๋ชจ๋…ธ๋“œ๊ฐ€ ํด๋•Œ,
                self.heapList[i // 2], self.heapList[i] = self.heapList[i], self.heapList[i //2] # ๋ถ€๋ชจ๋ž‘ ์ž์‹์˜ ์ž๋ฆฌ๋ฅผ ๋ฐ”๊ฟ”์ฃผ๊ณ 
            i = i // 2 # root๊นŒ์ง€ ์˜ฌ๋ผ๊ฐ”๋‹ค ์˜จ๋‹ค. ์ด๊ฑฐ ๋•Œ๋ฌธ์— (O(logn))

        # ์ด ๊ณผ์ •์„ ๊ฑฐ์น˜๋Š” ๋™์•ˆ siblings์—๋Š” ์•„๋ฌด๋Ÿฐ ์˜ํ–ฅ์„ ๋ฏธ์น˜์ง€ ์•Š๋Š”๋‹ค!
  • delMin()
    delMin()
    ...

    def delMin(self):
        retval = self.heapList[1] # __init__์—์„œ ์ œ์ผ ์ฒซ ๋…ธ๋“œ๋Š” 0์ด๊ธฐ ๋•Œ๋ฌธ์— ์‹ค์งˆ์ ์œผ๋กœ heap์˜ root๋Š” self.heapList[1] ์ด๋‹ค.
        self.heapList[1] = self.heapList[self.currentSize] # ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ๊ฐ’์„ root์— ๋„ฃ์–ด์ค€๋‹ค.
        self.currentSize = self.currentSize - 1
        self.heapList.pop() # leaf node ์ž๋ฆฌ๋กœ ์˜ฎ๊ฒจ์˜จ ์ตœ์†Ÿ๊ฐ’์„ ์ œ๊ฑฐ
        self.percDown(1)
        return retval

    def percDown(self,i): # ์ค‘์š”!: i์ž๋ฆฌ์˜ ์žˆ๋Š” ๋…ธ๋“œ์˜ ์ž์‹์€ i*2๋˜๋Š” i*2+1์ด๋‹ค.
        while (i * 2) <= self.currentSize: # ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ๊นŒ์ง€ ๊ฒ€์‚ฌ (1, 2, 4 ๊นŒ์ง€ ๊ฐ)
            mc = self.minChild(i) # self.heapList[i]์˜ ์ž์‹ ์ค‘์— ์ž‘์€ ์ž์‹์˜ ์ž๋ฆฌ = mc
            if self.heapList[i] > self.heapList[mc]: # ์ž‘์€ ์ž์‹์ด ์ž๊ธฐ๋ณด๋‹ค ์ž‘๋‹ค๋ฉด...
                self.heapList[mc], self.heapList[i] = self.heapList[i], self.heapList[mc] # ๊ทธ ์ž์‹๊ณผ ์ž๋ฆฌ๋ฅผ ๋ฐ”๊พผ๋‹ค.
            i = mc # ์œ„์˜ ๊ณผ์ • ๋ฐ˜๋ณต

    def minChild(self,i): # right node์™€ left node ์ค‘ ๋” ์ž‘์€ ๊ฒƒ ์ฐพ๊ธฐ
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i*2] < self.heapList[i*2+1]:
                return i * 2
            else:
                return i * 2 + 1
  • buildHeap
    ...

    def buildHeap(self,alist):
        i = len(alist) // 2 # ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ ์ž๋ฆฌ
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.percDown(i) # ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ ์ค‘ ์ž‘์€ ๊ฒƒ๊ณผ ๋ถ€๋ชจ ๋…ธ๋“œ ๋น„๊ตํ•ด์„œ ๋ถ€๋ชจ๊ฐ€ ๋” ํฌ๋ฉด ์ž๋ฆฌ ๋ฐ”๊ฟˆ
            i = i - 1 # ์•„๊นŒ ๊ทธ ๋ถ€๋ชจ์˜ sibling ๋„ ๋˜‘๊ฐ™์ด ์ž๋ฆฌ๋ฐ”๊ฟˆ ํ•ด์ฃผ๊ธฐ