[자료 구조] 트리

대표적인 트리 구조

 

1. 트리 구조

트리 : Node와 branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조

실제로 트리 중 이진트리 형태의 구조로, 탐색 알고리즘 구현을 위해 많이 사용

 

2. 알아둘 용어

Node : 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 Branch 정보 포함)

Root Node : 트리 맨 위에 있는 노드

Level :  최상위 노드를 Level 0으로 하였을 때 하위 Branch로 연결된 노드의 깊이를 나타냄

Parent Node : 어떤 노드의 다음 레벨에 연결된 노드

Child Node : 어떤 노드의 상위 레벨에 연결된 노드

Leaf Node : Child Node가 하나도 없는 노드

Sibling : 동일한 Parent Node를 가진 노드

Depth : 트리에서 Node가 가질 수 있는 최대 Level

 

3. 이진 트리와 이진 탐색트리 (binary Search Tree)

이진 트리 : 노드의 최대 Branch가 2인 트리

이진 탐색 트리 : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리

- 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음

4. 자료 구조 이진 탐색 트리의 장점과 주요 용도

주요 용도 : 데이터 검색(탐색) - 탐색 속도를 개선할 수 있음

5. 파이썬 객체 지향 프로그래밍으로 링크드 리스트 구현하기

노드 클래스 만들기

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

이진 탐색 트리에 데이터 넣고 탐색

class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break
    
    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False

head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)
BST.insert(0)
BST.insert(4)
BST.insert(8)

이진 탐색 트리 삭제

매우 복잡하기 때문에 경우를 나누어서 이해하는 것이 좋음

 

Leaf Node 삭제

Leaf Node : child node가 없는 node

삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.

 

child Node가 하나인 Node 삭제

삭제할 Node의 Parent Node가 삭제할 Node의 child Node를 가리키도록 한다.

 

child Node가 두개인 Node 삭제

1번 방법 : 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

2번 방법 : 삭제할 Node의 왼쪽 자식 중 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

- 삭제할 Node의 오른쪽 자식 선택

- 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택

- 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 branch가 가리키게 함

- 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함

- 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게함

- 만약 해당 Node가 오른쪽 child Node가 가지고 있었을 경우 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 child Node를 가리키게 함

 

이진 탐색 트리 삭제 코드 구현과 분석

Case3-1 삭제할 노드가 Child Node를 두 개 가지고 있을 경우(삭제할 Node가 Parent Node 왼쪽에 있을 때

기본 사용 가능 전략

1. 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

2. 삭제할 Node의 왼쪽 자식 중 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

 

기본 사용 전략 중 1번 전략을 사용하여 코드를 구현

경우의 수가 또 다시 2가지 존재

1-1. 삭제할 Node가 Parent Node의 왼쪽에 있고 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 Child Node가 없을 때

1-2 삭제할 Node가 Parent Node의 왼쪽에 있고 삭제랗 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을때 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문

 

Case3-2 삭제할 노드가 Child Node를 두 개 가지고 있을 경우(삭제할 Node가 Parent Node 오른쪽에 있을 때)

기본 사용 가능 전략

1. 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

2. 삭제할 Node의 왼쪽 자식 중 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

 

기본 사용 전략 중 1번 전략을 사용하여 코드를 구현

경우의 수가 또 다시 2가지 존재

2-1. 삭제할 Node가 Parent Node의 왼쪽에 있고 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 Child Node가 없을 때

2-2. 삭제할 Node가 Parent Node의 왼쪽에 있고 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 Child Node가 있을 때 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문임

 

전체 코드

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

        
class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break
    
    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False        
    
    def delete(self, value):
        # 삭제할 노드 탐색
        searched = False
        self.current_node = self.head
        self.parent = self.head
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right

        if searched == False:
            return False    

        # case1
        if  self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None
        
        # case2
        elif self.current_node.left != None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right        
        
        # case 3
        elif self.current_node.left != None and self.current_node.right != None:
            # case3-1
            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.change_node.left
            # case 3-2
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left

        return True

6. 이진 탐색 트리의 시간 복잡도와 단점

시간 복잡도(탐색시)

트리의 높이를 h라고 표기한다면 O(h)

n개의 노드를 가진다면 h = log2n에 가까우므로 시간 복잡도는 O(logn)

참고 : 빅오 표기법에서 logn에서의 log의 밑은 10이 아니라 2이다.

한번 실행시마다 50%의 실행할 수도 있는 명령을 제거한다는 의미, 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함

이진 탐색 트리 단점

평균 시간 복잡도는 O(logn) 이지만

이는 트리가 균형 잡혀 있을때의 평균 시간 복잡도이며

다음 예와 같이 구성되어 있을 경우 최악의 경우는 링크드 리스트 등과 동일한 성능를 보여줌 (O(n))