[코딩 + 알고리즘 완주반] 14일차. 트리

# 트리 구조

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

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

 

# 알아둘 용어

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

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

Level : 최상위 노드를 level 0으로 하였을 때, 하위 branch로 연결된 노드의 깊이

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

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

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

Silbinng(Brother node) : 동일한 Parent Node를 가진 노드

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

 

# 이진 트리와 이진 팀색 트리

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

이진 탐색 트리 (Binary Search Tree)  : 왼쪽 노드는 해당 노드보다 작은값, 오른쪽 노드는 해당 노드보다 큰값을 가지고 있는 이진 트리

 

# 이진 탐색 트리의 장점과 주요 용도

주요 용도 :  데이터 검색(탐색)

장점 : 탐색 속도를 개선할 수 있음

 

# 데이터 넣기, 탐색 코드

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  

 

# 이진 탐색 트리 삭제

0. 삭제할 노드가 있는지 먼저 탐색

1. Leaf Node 삭제 ( Child Node가 없는 노드) : 삭제할 Node의 Parent Node가 가리키지 않도록

2. Child Node가 하나인 Node 삭제 :  Parent Node가 삭제할 노드의 Child Node를 가리키도록

3. Child Node가 두개인 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

# 이진 탐색 트리의 시간 복잡도

depth ( 트리의 높이)를 h라고 한다면 시간복잡도는 O(h)

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

 

# 이진 탐색 트리의 단점

평균 시간 복잡도는 O(logn) ( 균형잡혀 있을 때 )

한쪽으로만 치우쳐 있을 경우 (최악의 경우) 링크드 리스트 등과 동일한 성능 O(n)