트리 level 2 (이진 트리, Binary Tree)

1) 이진 트리(Binary Tree)

① 기본 이진 트리

  - 모든 노드의 차수(degree)가 2 이하인 트리

  - 트리는 child노드를 갖고 그 child 노드들로부터 부분트리를 가질 수 있기 때문에 본질적으로 재귀적인 성질이 있다.

    → 추가적으로 재귀적인 성질을 완성하기 위해 '빈트리도 이진트리이다'(터미널 조건)라는 정의도 필요하다.

  - 왼쪽 그림과 같이 한쪽으로 치우쳐진 트리도 이진 트리이다 (이진 트리 조건 충족)

  - 다만, 우리가 접하는 이진 트리는 한쪽으로 치우쳐진 트리보단 보통, 균형을 이룬(한쪽으로 치우쳐지지 않은) 트리가 더 많다.

 

② 포화 이진 트리 (Full Binary Tree)

  - 모든 리프 노드를 제외한 모든 레벨에서 노드들이 2개의 자식을 갖는 트리

  - 높이가 n → 노드의 개수 = 2ⁿ - 1

 

③ 완전 이진 트리(Complete Binary Tree)

  - 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨에서 노드들이 왼쪽 부터 순차적으로 채워져 있는 트리

 

 

2) 이진 트리의 추상적 자료구조

① 연산의 정의

  - node : data item  뿐만 아니라, left child, right child 포터를 가짐

  - tree : root 노드를 요소로 가진다

  - size() : 현재 트리에 포함되어 있는 노드의 수를 구함

  - depth() : 현재 트리의 깊이 (또는 높이)를 구함

  - traversal(순회) : 정해진 순서대로 노드를 방문해서 정해 연산 처리

class Node:

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


    def size(self):					# 재귀적인 방식으로 size 도출				
        l = self.left.size() if self.left else 0	# left(또는 right) child가 있으면 재귀 호출 없으면 0		 
        r = self.right.size() if self.right else 0
        return l + r + 1				# left subtree + right subtree + 1(root) = 전체 이진 트리의 size


    def depth(self):					# 재귀적인 방식으로 depth 도출	
        l = self.left.depth() if self.left else 0	# left(또는 right) child가 있으면 재귀 호출 없으면 0
        r = self.right.depth() if self.right else 0
        
        return 1 + max(l, r)				# left subtree 와 right subtree 중 더 큰 것+ 1(root X) = 전체 이진 트리의 depth


class BinaryTree:

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

    def size(self):					# 트리 전체 크기
        if self.root:
            return self.root.size()	
        else:
            return 0					# 루트 노드부터 시작하며, 루트 노드 없을 시 0 반환


    def depth(self):					# 트리 전체 depth
        if self.root:
            return self.root.depth()
        else :
            return 0					# 루트 노드부터 시작하며, 루트 노드 없을 시 0 반환

 

② 이진트리의 순회(Traversal)

  - 순회

• 깊이 우선 순회 (Depth First Traversal)

      1. 중위 순회 (in-order traversal)

def inorder(self) :				# 순회 순서
	traversal = []
    if self.left :				# (1) Left subtree
    	traversal += self.left.inorder()
    traversal.append(self.data)			# (2) 자기 자신
    if self.right :				# (3) Right subtree
    	traversal += self.left.inorder()
    return traversal

      2. 전 순회 (pre-order traversal)

def preorder(self):				# 순회 순서
	traversal = []
	traversal.append(self.data)		# (1) 자기 자신
	if self.left:				# (2) Left subtree
		traversal += self.left.preorder()
	if self.right:				# (3) Right subtree
		traversal += self.right.preorder()
	return traversal

      3. 후위 순회 (post-order traversal) 

def postorder(self):				# 순회 순서
	traversal = []
	if self.left:				# (1) Left subtree
		traversal += self.left.preorder()
	if self.right:				# (2) Right subtree
		traversal += self.right.preorder()
	traversal.append(self.data)		# (3) 자기 자신
	return traversal

• 넓이 우선 순회 (Breadth First Traversal)

      1. 원칙

        - 수준(level)이 낮은 노드를 우선으로 방문 (root에서 leaf 순으로)

        - 같은 수준의 노드들 사이에는 부모 노드의 방문 순서에 따라 방문

        - 왼쪽 자식 먼저 방문 후 오른쪽 자식 방문

 

      2. BFS 알고리즘 설계

        - DFS와 달리 재귀적 방법은 적합하지 않다

        - 한 노드를 방문 시, 나중에 방문할 노드들을 순서대로 기록해 두어야 한다 → 큐(Queue) 활용

        - 루트 노드 먼저 인큐(enqueue)

        - 다음 노드 방문 시 방문한 노드 디큐(dequeue) 후 자식 노드 인큐(enqueue)

 

      3. 넓이 우선 순회 알고리즘 구현

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 = []					# (1) (초기화) traversal ← 빈 리스트, q ← 빈 큐
        q = ArrayQueue()
        if self.root :					# (2) 빈 트리가 아니면, root node를 q에 추가 (enqueue)
            q.enqueue(self.root)
            while q.isEmpty() == False :		# (3) q가 비어 있지 않은 동안
                node = q.dequeue()			# (3) - 1. node ← q에서 원소를 추출 (dequeue)
                traversal.append(node.data)		# (3) - 2. node를 방문				
                if node.left : q.enqueue(node.left)	# (3) - 3. node의 ¹왼쪽, ²오른쪽 자식(있으면)들을 q에 추가(enqueue)
                if node.right : q.enqueue(node.right)
            return traversal				# (4) q가 빈 큐가 되면 모든 노드 방문 완료
        else :
            return []

 

 

3) 이진 탐색 트리 (Binary Search Tree)

① 이진 탐색 트리 (Binary Search Tree)

  - 모든 노드에 대해서 다음과 같은 성질을 만족 하는 이진 트리

    1. 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작다

    2. 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 크다

      ※ 중복되는 데이터 원소는 없는 것으로 가정

  - 이진 탐색 트리는 데이터 검색에 유용하다

 

② 이진 탐색 트리의 추상적 자료구조

  - 각 노드는 (key, value)의 쌍으로 데이터를 표현한다 → 키를 이용해서 검색이 가능함에 따라 보다 복잡한 데이터 레코드로 확장이 가능하다

    ※ Key : 노드의 고유한 숫자로 탐색의 기준이 됨 / value : 해당 노드가 가진 실질적 데이터

 

③ - 1. 연산의 정의

  - insert(key, data) - 트리에 주어진 데이터 원소를 추가

  - remove(key) - 특정 원소를 key를 통해 트리로부터 삭제

  - lookup(key) - 특정 원소를 key로 검색

  - inorder() - key의 순서대로 데이터 원소를 나열

  - min(), max() - 최소 key, 최대 key를 가지는 원소를 각각 탐색

class Node:

    def __init__(self, key, data):				# key, value 초기화
        self.key = key
        self.data = data
        self.left = None
        self.right = None


    def insert(self, key, data):
        if self.key > key :					# 입력값과 해당 노드 키 비교를 통해 좌/우 움직임 결정
            if self.left : self.left.insert(key, data)		# 자식 노드가 있으므로 insert메소드 재귀 호출
            else :
                self.left = Node(key, data)			# 자식 노드가 없는 leaf 노드이므로 현재 노드의 왼쪽 자식 노드로 key, data 삽입 
        if self.key < key :
            if self.right : self.right.insert(key, data)
            else :
                self.right = Node(key, data)
           	return True
        else :
        	raise KeyError('Key %s already exists.' % key)
  
  
	def lookup(self, key, parent=None):			# root(default) 노드 부터 찾고자하는 data를 key을 통해 찾음
        if key < self.key:					# 찾고자 하는 data의 key 값을 현재 node의 key값과 비교를 통해 좌/우 결정
            if self.left:					# 비교 후 자식 노드 유무를 통해 lookup 메소드 재귀 호출 또는 해당 key값 없음을 return
                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
        

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 inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []

③ - 2. 이진 탐색 트리의 remove 연산

  - 삭제는 두 가지 프로세스로 구성됨

    1) 키(key)를 이용해서 노드를 찾아 삭제하며, 해당 노드가 없을 경우 삭제할 것도 없음 

    2) 찾은 노드를 제거한 후에도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리해야한다

  - 노드를 삭제할 경우 다음 세가지 사항을 고려해야함

•  삭제되는 노드가 말단(leaf) 노드인 경우
•  삭제되는 노드가 자식을 하나 가지고 있는 경우
•  삭제되는 노드가 자식을 둘 가지고 있는 겨우

    1. 삭제되는 노드가 말단(leaf) 노드인 경우

       → 해당 노드가 부모 노드의 어느 쪽 자식인지 찾은 후 삭제

         ※ 삭제되는 노드가 root 노드인 경우 트리 자체가 없어진다.

  2. 삭제되는 노드가 자식을 하나 가지고 있는 경우

       → 삭제되는 노드의 자식 노드는 어느 쪽에 붙은 노드인지, 해당 노드는 부모 노드의 어느 쪽 노드인지 알아낸 후 해당 노드를 삭제하고 해당 노드의 부모 노드와 자식 노드를 이어주어야 한다.(해당 노드의 자식 노드가 해당 노드 자리를 대신함) 

         ※ 삭제되는 노드가 root 노드인 경우 대신 들어오는 자식 노드가 root가 됨

  3. 삭제되는 노드가 자식을 둘 가지고 있는 경우

 

       → 삭제되는 노드보다 바로 다음 큰 키를 가진 노드를 successor로 설정한다. (sccessor = 오른쪽 자식의 서브 트리 중 가장 작은 노드) 이 successor를 찾아 해당 노드를 대체하고 successor의 원래 위치의 노드는 삭제한다. 

class Node:

    def __init__(self, key, data):				# key, value 초기화
        self.key = key
        self.data = data
        self.left = None
        self.right = None

        
    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 remove(self, key):
        node, parent = self.lookup(key)
        if node:
            nChildren = node.countChildren()
            # The simplest case of no children
            if nChildren == 0:
                # 만약 parent 가 있으면
                if parent :
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # parent.left 또는 parent.right 를 None 으로 하여
                # leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
                    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 node == parent.left :
                        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
                # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
                # 그에 따라 parent.left 또는 parent.right 를
                # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
                if successor == parent.left :
                    if successor.right :
                        parent.left = successor.right
                    else :
                        parent.left = None
                else : 
                    if successor.right :
                        parent.right = successor.right
                    else :
                        parent.right = None
            return True

        else:
            return False