[자료구조] 트리(Tree) (Python)

[자료구조] 트리(Tree) (Python)

반응형

1. 기본 구조와 용어

트리(Tree): Node와 Branch를 이용하여, 사이클을 이루지 않도록 구성한 데이터 구조

노드(Node) : 트리에서 데이터를 저장하는 기본 요소로, Branch 정보 또한 포함

: 트리에서 데이터를 저장하는 기본 요소로, Branch 정보 또한 포함 간선(Edge) : 노드와 노드를 연결하는 연결선

: 노드와 노드를 연결하는 연결선 Root Node : 트리 맨 위의 노드

: 트리 맨 위의 노드 Leaf Node : Child Node가 하나도 없는 노드

: Child Node가 하나도 없는 노드 Depth: 트리에서 Node가 가질 수 있는 최대 Level

2. 이진 탐색 트리(Binary Search Tree)

이진 트리에 추가적인 조건이 있는 트리 (왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값)

3. Python Linked list로 간단한 Binary Seach Tree 구현

Python class를 통해 Linked list를 구현

NodeMgmt class의 (insert, search, delete) 함수를 통해 기능들을 구현

class Node: def __init__(self,value):#이진트리이므로 left와 right만 있어도 됨 self.value = value self.left = None self.right = None class NodeMgmt: def __init__(self,head): #root노드가 head self.head=head #원하는 값을 트리안에 넣어주는 기능 def insert(self,value): self.current_node = self.head #현재 노드는 head로 잡고 while True: #순회 #insert하려는 current_node.value보다 작을 때 if value < self.current_node.value: if self.current_node.left != None: #left가 있으면 current를 current.left로 이동 self.current_node = self.current_node.left else: #left가 없으면 left부분에 value값을 넣어줌 self.current_node.left = Node(value) break #insert하려는 값이 current_node.value보다 클 때 else: if self.current_node.right != None: #아래 아무것도 없다면 current.right로 이동 self.current_node = self.current_node.right else: #right가 없으면 right부분에 value값을 넣어줌 self.current_node.right = Node(value) break #어떤 값이 존재하는지 판단하는 기능 def search(self, value): self.current_node = self.head while self.current_node: #current_node가 none이 되면 종료 if self.current_node.value == value: #현재 노드가 내가 원하는 값인지 return True break elif value < self.current_node.value: self.current_node = self.current_node.left else: self.current_node = self.current_node.right return False # 원하는 value의 노드를 삭제하는 기능 def delete(self, value): searched = False self.current_node = self.head self.parent = self.head # 삭제할 Node 탐색 while self.current_node: if self.current_node.value == value: searched = True break #찾으면 break elif value < 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 #탐색이 끝나면 #Case를 분리하여 삭제해나가는 process #1 leaf node 삭제 if self.current_node.left == None and self.current_node.right==None: if value

[insert 함수]

맨 위의 노드를 current_node로 잡기

depth 하나씩 늘어날 때마다 넣고자 하는 value를 current_node.value와 비교하여 어떤 방향으로 내려갈지 결정

쭉쭉 내려가다가 (current_node.value보다 큰데 current_node.right가 비어있을 때), (current_node.value보다 작은데 current_node.left가 비어있을 때)의 경우에는 그 위치에 원하는 value가 담긴 노드를 만들어준다.

[search 함수]

그냥 간단하게 트리를 한번 쭉 훑으면서 찾고자 하는 value가 있는지 확인하는 함수

[delete 함수]

상당히 복잡하다;; 머릿속으로 각각의 상황을 잘 분할하는 것이 중요

먼저 삭제하고자 하는 value를 가지고 있는 노드를 탐색하여 current_node로 설정

트리 구조에서 하나의 노드를 삭제하면 이를 반영하여 노드간 연결을 수정해주어야 함

그렇기에 삭제하려는 노드가 어떤 연결관계를 가졌는지에 따라 여러 경우를 따져서 분할해준 뒤 하나하나씩 정복해나가는 방식을 사용

(분할해주기)

삭제할 노드의

1) child가 하나도 없을 때(leaf node일 때)

2) child가 하나 있을 때

2-1) child의 left만 가지고 있을 때

2-2) child의 right만 가지고 있을 때

3) child가 두 개 있을 때

3-1) 삭제할 node가 parent node 왼쪽에 위치

3-1-1) 삭제할 node의 오른쪽 child가 child 없을 때

3-1-2) 삭제할 node의 오른쪽 child가 child 있을 때

3-2) 삭제할 node가 parent node 오른쪽에 위치

3-2-1) 삭제할 node의 오른쪽 child가 child 없을 때

3-2-2) 삭제할 node의 오른쪽 child가 child 있을 때

반응형

from http://tipsyziasu.tistory.com/94 by ccl(A) rewrite - 2021-07-29 11:26:37