이진트리 Binary Tree , 이진탐색트리 Binary Search Tree

공부자료: 신찬수 교수님 '자료구조' 재생목록

자료구조 - 이진트리 - 정의와 순회 - YouTube

자료구조 - 이진트리 - 이진탐색트리 정의와 탐색, 삽입 연산 - YouTube

자료구조 - 이진트리 - 이진탐색트리 삭제 연산 - YouTube

 

이진트리: 자식 노드를 최대 두 개까지만 갖는 트리

힙에서 배웠던 세 가지 표현법 중 노드로 표현하는 법을 사용한다.

한 노드에 부모 노드와 오른쪽 자식노드, 왼쪽 자식노드를 가리키는 링크를 추가한다.

순회 traveral

- 이진트리 노드의 key 값을 빠짐없이 출력하는 방법

- 노드의 key 값에 모두 일정한 값을 더하거나 빼고 싶을 때, 값을 하나씩 전부 출력하고 싶을 때 순회가 필요하다.

 

순회 방법에는 세 가지가 있다. 

부모 노드를 M이라 하고 이를 기준으로 한 왼쪽 subtree를 L, 오른쪽 subtree를 R이라 하자.

1. preorder

MLR 순으로 방문.

 

2. inorder

LMR 순으로 방문.

 

3. postorder

LRM 순으로 방문

 

ex)

아래와 같은 트리가 있다고 가정.

각 순회 방식을 이용했을 때 출력 순서를 쓰면 아래와 같다..

1. preorder 방식

F, B, A, D, C, E, G, I, H

 

2. inorder 방식

A, B, C, D, E, F, G, H, I

 

3. postorder 방식

A, C, E, D, B, H, I, G, F

 

 

[try] 이진트리를 모르는 상태에서 각 순회 방식의 출력값만 가지고 트리 구하기 (reconstruct)

 

구현

1. 노드 클래스

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    
    def __str__(self):
        return str(self.key)

parent, left, right 노드의 초기값은 전부 None으로 설정한다.

Node를 출력했을 때 key값이 출력되도록 __str__함수도 작성한다.

 

 

순회 방법 구현 (Node 클래스)

순회 방법은 Node 클래스 또는 Tree 클래스에 정의할 수 있다.

 

1. preorder

    def preorder(self):  # MLR 순
        if self != None:
            print(self.key)
            if self.left:
                self.left.preorder()
            if self.right:
                self.right.preorder()

재귀함수로 간단히 작성할 수 있다.

print(self.key) -> M

self.left에 값이 있다면 거기에서 또 preorder를 재귀적으로 수행하고, self.right도 마찬가지로 수행한다.

 

2. inorder

다른 순회 방식은 코드의 순서만 잘 바꿔주면 된다.

    def inorder(self):  # LMR 순
        if self != None:
            if self.left:
                self.left.preorder()
            print(self.key)
            if self.right:
                self.right.preorder()

 

3. postorder

    def postorder(self):  # LRM 순
        if self != None:
            if self.left:
                self.left.preorder()
            if self.right:
                self.right.preorder()
            print(self.key)

 

순회 방법 구현 (Tree 클래스)

class Tree:
    def __init__(self):
        self.root = None
        self.size = 0
    
    def __len__(self):
        return self.size
    
    def __iter__(self):
        return self.root.__iter__()
    
    def __str__(self):
        return " - ".join(str(k) for k in self)
    
    def preorder(self, v):  # MLR 순
        if v:
            print(v.key, end=" ")
            self.preorder(v.left)
            self.preorder(v.right)

    def inorder(self, v):  # LMR 순
        if v:
            self.inorder(v.left)
            print(v.key, end=" ")
            self.inorder(v.right)
                
    def postorder(self, v):  # LRM 순
        if v:
            self.postorder(v.left)
            self.postorder(v.right)
            print(v.key, end=" ")

 

이진탐색트리 Binary Search Tree

탐색에 유용한 유형의 이진트리

 

<전제 조건>

- 각 노드의 왼쪽 subtree의 key값은 노드의 key값보다 작거나 같아야 함

- 각 노드의 오른쪽 subtree의 key값은 노드의 key값보다 커야 한다.

- 중복되는 값이 없어야 한다.

 

출처 Binary search tree - Wikipedia

BST 클래스

(노드 클래스는 이미 구현되어 있어야 한다.)

class BST:
    def __init__(self):
        self.root = None
        self.size = 0
    
    def __len__(self):
        return self.size
    
    def __iter__(self):
        return self.root.__iter__()
    
    def __str__(self):
        return " - ".join(str(k) for k in self)

 

탐색 연산

search 함수 구현을 위해 먼저 find_loc 함수를 구현한다.

find_loc 함수는 key값을 갖는 노드가 있으면 해당 노드를 리턴하고, 없으면 노드가 삽입될 부모 노드를 리턴한다.

1. find_loc

def find_loc(self, key):  # key값을 갖는 노드가 있으면 해당 노드 리턴, 없으면 노드가 삽입될 부모 노드 리턴
        if self.size == 0:
            return None
        p = None  # 부모 노드
        v = self.root  # 탐색용 노드
        
        while v != None:
            if v.key == key:
                return v
            elif v.key < key:
                p = v
                v = v.right
            else:
                p = v
                v = v.left
        return p

이진탐색트리는 오른쪽 노드의 값이 더 크다. 만약 찾아야 할 key값이 v의 key값보다 크다면 부모 노드를 p에 저장하고 오른쪽으로 이동한다. 반대라면 왼쪽으로 이동한다. 이렇게 탐색을 계속한 후 key 값이 같다면 v를 리턴하고, 아니라면 삽입될 곳의 부모 노드를 리턴한다. 

 

2. search

    def search(self, key):
        v = self.find_loc(key)
        if v and v.key == key:
            return v
        else:
            return None

find_loc 함수의 탐색 결과를 v라는 변수에 저장한다. 만약 v가 존재하고 v의 key값이 인자로 받은 key와 일치한다면 v를 출력하고, 아니라면 None을 출력한다.

 

3. insert

def insert(self, key):
        p = self.find_loc(key)  # O(h)
        if p == None or p.key != key:
            v = Node(key)
            if p == None:
                self.root = v
            else:
                v.parent = p
                if p.key > key:
                    p.left = v
                else:
                    p.right = v
            self.size += 1
            return v
        else:
            print("Key is already in tree")
            return p

find_loc 의 결과를 p에 저장한다.

만약 트리에 아무것도 없거나 p의 key가 넣으려는 key와 다르다면 삽입될 key 값을 갖는 노드 v를 새로 만든다.

 

1) 트리에 아무것도 없는 상태

- v를 루트 노드로 설정

2) 트리가 비어있지 않고 p.key가 key와 다른 상태

- p를 v의 부모 노드로 설정

- key가 p.key보다 작다 = key는 왼쪽에 가야 한다. 

- key가 p.key보다 크다 = key는 오른쪽에 가야 한다.

 

값 삽입을 완료한 후 size를 하나 키워준 후 삽입된 노드 v를 리턴한다.

만약 트리에 비어있지 않고 p.key와 key와 같다면(=값이 이미 있는 상태) 중복 문구를 출력한다. 

 

삭제 연산

노드를 지울 때에는 삭제된 빈 공간을 다른 노드들로 다시 메워야 함. 

1. deletebyMerging

delete by Merging은 아래 그림과 같이 수행된다.

위와 같은 트리가 있다고 가정하자. 여기서 20이 적힌 노드를 delete by merging으로 지우려고 한다.

변수 a에 x의 왼쪽 부트리를 저장하고, b에는 x의 오른쪽 부트리를 저장한다. 마찬가지로 pt에는 x의 부모 노드를 저장한다.

a를 본래 x의 자리로 이동한다. b는 a에서 가장 큰 노드의 자식노드가 되도록 조정한다.

    def deleteByMerging(self, x):
        a = x.left
        b = x.right
        pt = x.parent
        if a == None:
            c = b
        else:
            c = m = a  # m = 왼쪽 부트리의 가장 큰 값
            while m.right:
                m = m.right
            m.right = b
            if b:
                b.parent = m
        if self.root == x:
            if c:
                c.parent = None
            self.root = c
        else:
            if pt.left == x:
                pt.left = c
            else:
                pt.right = c
            if c:
                c.parent = pt
        self.size -= 1

 

그림과 같은 경우 외에도 다른 경우를 고려하여 코드를 짜야 한다.

1) x를 지워야하는데 x의 왼쪽 부트리가 존재하지 않을 경우

--> b(x.right)가 원래 x의 자리로 그대로 올라온다.

2) x가 루트노드인 경우

--> a가 존재한다면 b가 m의 오른쪽 자식노드가 되도록 수정한 후 루트를 a로 바꾼다.

--> a가 없다면 b가 새 루트가 된다.

 

2. deletebyCopying

그림으로 표현하면 다음과 같은 과정으로 수행된다.

20이 있는 노드를 지우고 싶다고 가정하자.

왼쪽 부트리에서 가장 큰 값을 y라는 변수에 저장한 후, x의 위치에 y의 값을 복사한다.

y의 자식노드를 y의 자리로 옮기고 y.parent에 연결한 후 y 노드를 지운다.

    def deleteByCopying(self, x):
        pt = x.parent
        L, R = x.left, x.right
        
        if L: # 왼쪽 부트리가 존재
            y = L
            while y.right:
                y = y.right
            x.key = y.key
            if y.left:
                y.left.parent = y.parent
            if y.parent.left is y:
                y.parent.left = y.left
            else:
                y.parent.right = y.left
            del y
        
        elif not L and R: # 왼쪽 부트리가 없고 오른쪽 부트리만 존재
            y = R
            while y.left:
                y = y.left
            x.key = y.key
            if y.right:
                y.right.parent = y.parent
            if y.parent.left is y:
                y.parent.left = y.right
            else:
                y.parent.right = y.right
            del y
        
        else:  # 부트리가 아예 없을 때
            if pt == None:  # x가 루트노드인 경우
                self.root = None
            else:
                if pt.left is x: 
                    pt.left = None
                else:
                    pt.right = None
            del x