[TIL] 트리 - Tree

트리(Tree)란?  

• node와 branch를 이용한 데이터 구조
• 사이클x 
• 탐색 알고리즘에 많이 사용(BST)

용어

• 노드(Node) : 데이터를 저장하는 기본 요소 (+ Branch)
• 루트노드(Root Node) : 트리의 최상위 노드
• 레벨(level) : 하위 브랜치로 연결된 노드의 깊이
• 부모 노드(Parent Node) : 어떤 노드의 다음 레벨 노드
• 자식 노드(Child Node): 어떤 노드의 상위 레벨에 연결된 노드
• 리프 노드(Leaf Node): 자식 노드가 하나도 없는 노드 (= terminal node)
• 형제 노드(Sibling Node): 동일한 부모 노드를 가진 노드 (= 레벨이 동일)
• Depth : 트리의 최대 level
• 이진 트리(Binary Tree) : 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리(Binary Search Tree, BST): 이진트리의 조건 + 왼쪽노드는 해당노드보다 작은 값이, 오른쪽 노드는 해당 노드보다 큰 값이 오도록 구성된 트리

 

BST 구현

1. 노드 클래스의 생성

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

# 노드 상태 초기화

 

2. BST 구현을 위한 클래스 생성 및 데이터 삽입 함수

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

 

3. BST 탐색

def search(self, value):
    self.cur_node = self.head
    while self.cur_node:
    	if self.cur_node.value == value:	# value가 해당 노드의 value와 일치하는 경우 True 리턴
            return True					
        elif value < self.cur_node.value:	# value가 해당 노드의 value 보다 작은 경우
            self.cur_node = self.cur_node.left
        else:						# value가 해당 노드의 value 보다 큰 경우
            self.cur_node = self.cur_node.right
    return False

 

4. BST 삭제 ※

    * 삭제의 경우 매우 복잡하므로 case를 나누어 구현한다.

    * 삭제할 노드가 없는 경우도 고려해야 하므로 노드 삭제 전 삭제할 노드를 탐색한다.

def delete(self, value):	# search 함수의 원리
    searched = False
    self.cur_node = self.head
    self.parent = self.head
    while self.cur_node:
        if self.cur_node.value == value:
            searched = True
            break
        elif value < self.cur_node.value:
            self.parent = self.cur_node
            self.cur_node = self.cur_node.left
        else:
            self.parent = self.cur_node
            self.cur_node = self.cur_node.right
    if searched == False:
        return False

 

    1) Leaf Node를 삭제할 경우

if self.cur_node.left == None and self.cur_node.rignt == None:
    if value < self.parent.value:	
        self.parent.left = None
    else:
        self.parent.right = None
    del self.cur_node	# 노드 삭제

    2) 삭제하는 노드의 자식노드가 1개인 경우

if self.cur_node.left != None and self.cur_node.right == None: 	# 왼쪽에 자식노드가 있는 경우
    if value < self.parent.value:
        self.parent.left = self.cur_node.left
    else:
        self.parent.right = self.cur_node.left
elif self.cur_node.left == None and self.cur_node.right != None: 	# 오른쪽에 자식노드가 있는 경우
    if value < self.parent.value:
        self.parent.left = self.cur_node.rignt
    else:
        self.parent.right = self.cur_node.rignt

    3) 삭제하는 노드의 자식노드가 2개인 경우

        3-1) 삭제할 노드가 부모노드의 왼쪽에 있을 때

            * 삭제할 노드의 오른쪽 자식 중 가장 작은 값 또는 왼쪽 자식 중 가장 큰 값을 삭제할 노드의 위치로 옮긴다.

            * 위 각각의 경우 역시 두가지로 나뉘는데 매우 복잡하기 때문에 구현하면서 살펴보기로 한다.

# 삭제할 노드가 부모노드의 왼쪽에 있는 경우 3-1로 구현
# 3-1-1) 삭제할 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드가 자식이 없는 경우
# 3-1-2) 삭제할 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드의 오른쪽에 자식 노드가 있는 경우 (가장 작은 값을 가진 노드이므로 왼쪽은 존재할 수 없다)

if self.cur_node.left != None and self.cur_node.right != Node:
    if value < self.parent.value:	# 삭제할 노드가 부모의 왼쪽에 있는 경우
        self.ex_node = self.cur_node.right
        self.ex_node_p = self.cur_node.right
        while self.ex_node.left != None:	# 오른쪽 자식 중 가장 작은 노드 탐색
            self.ex_node_p = self.ex_node
            self.ex_node = self.ex_node.left
        if self.ex_node.right != None:		# 가장 작은 노드에 오른쪽 자식이 있는 경우
            self.ex_node_p.left = self.ex_node.right
        else:
            self.ex_node_p.left = None
        self.parent.left = self.ex_node
        self.ex_node.right = self.cur_node.right
        self.ex_node.left =self.cur_node.left

 

        3-2) 삭제할 노드가 부모노드의 오른쪽에 있을 때

                *위의 경우와 유사하나 노드 방향에 주의한다.

 

 

BST의 시간복잡도는?

트리의 높이(Depth)를 h라고 할 때 O(h)이다.
n개의 노드를 가진다면 높이 h는 log2(n)에 가깝다고 할 수 있기 때문에 O(logn)
* 실행 시 50% 즉, 절반의 실행시간을 단축시킬 수 있으므로

그러나 최악의 경우 (트리의 불균형) 링크드 리스트, 배열과 동일한 성능이다. (O(n))

 

 

 

 

*본 내용은 패스트 캠퍼스 강의를 참고하였습니다.