Tree (트리) 정리

👨🏼‍💻 Tree (트리) 정리 With Python

🥝 Tree란?

Node와 Branch를 이용해서 Cycle을 이루지 않도록 구성한 데이터 구조입니다.

 

🍋 관련 용어

Node          : 트리에서 데이터를 저장하는 기본 요소

Root Node   : 트리의 최상위 노드

Level           : 최상위 노드를 Level 0이라고 했을 때, 하위 Branch로 연결된 노드의 깊이를 나타냅니다.

Parent Node : 어떤 노드의 부모 노드

Child Node   : 어떤 노드의 자식 노드

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

Sibling         : 동일한 Parent Node를 가지는 노드

Depth          : 트리에서 Node가 가질 수 있는 최대 Level (위 사진에서의 Depth는 2)

 

🍊 이진 탐색 트리

이진 탐색 트리는 이진트리의 조건을 만족하면서

왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 크거나 같은 값을 가지고 있는 트리 구조입니다.

 

🍉 이진 탐색 트리의 장점

배열과 비교했을 때 데이터 탐색 속도가 월등히 빠른 것을 알 수 있습니다.

 

🍈 이진 탐색 트리 구현 With Python

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


class Tree:
    def __init__(self, head):
        self.head = head

    def insert(self, value):
        self.node = self.head
        while True:
            if value < self.node.value:
                if self.node.left != None:
                    self.node = self.node.left
                else:
                    self.node.left = Node(value)
                    break
            else:
                if self.node.right !=None:
                    self.node = self.node.right
                else:
                    self.node.right = Node(value)
                    break

    def search(self,value):
        self.node = self.head
        while self.node:
            if self.node.value == value:
                return True
            elif value < self.node.value:
                self.node= self.node.left
            else :
                self.node = self.node.right
        return False

 

🥥 이진 탐색 트리 삭제 구현

이진 탐색 트리의 삭제는 매우 복잡하기 때문에 경우를 나눠서 이해하는 것이 편합니다.

 

Case 1 : Child Node가 없는 Node

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

 

Case 2 : Child Node가 하나인 Node 삭제

1. 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 합니다.

 

Case 3 : Child Node가 두 개인 Node 삭제

1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 합니다.
2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 합니다.

 

🥞 이진 탐색 트리 삭제 코드 구현

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

 

🥭 이진 탐색 트리 시간 복잡도

위 사진 같이 트리가 균형 잡혀 있지 않을 때 O(n)의 성능을 보여 줍니다.