-
반응형
1. 기본 구조와 용어
- 트리(Tree): Node와 Branch를 이용하여, 사이클을 이루지 않도록 구성한 데이터 구조
- 노드(Node): 트리에서 데이터를 저장하는 기본 요소로, Branch 정보 또한 포함
- 간선(Edge): 노드와 노드를 연결하는 연결선
- Root Node: 트리 맨 위의 노드
- Leaf 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<self.parent.value: self.parent.left = None else: self.parent.right = None del self.current_node #2 child의 left만 가지고 있는 노드 삭제 if self.current_node.left != None and self.current_node.right==None: #current가 parent 왼쪽인지 오른쪽인지 if vale<self.parent.value: #왼쪽일 때 self.parent.left = self.current_node.left else: #오른쪽일 때 self.parent.right = self.current_node.left #child의 right만 가지고 있는 노드를 삭제할 때 똑같은 방식으로 처리 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 #3 Child Node가 두개인 node 삭제 #삭제할 Node의 오른쪽 자식 중 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다. #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 있을 때 if self.current_node.left != None and self.current_node.right != None: if value<self.parent.value: #3-1 self.change_node = self.current_node.right self.change_node_parent = self.current_node.right while self.change_node.left != None:#left 타고 최대한 간 후 self.change_node.parent = self.change_node self.change_node = self.change_node.left if self.change_node.right != None: #3-1-2 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 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.left = self.current_node.left self.change_node.right = self.current_node.right
[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가 두 개 있을 때
##삭제할 Node의 오른쪽 자식 중 작은 값을 삭제할 Node의 Parent Node가 가리키도록 하는 방식 이용
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 있을 때
4. BST 시간복잡도와 단점
- Tree의 Depth가 1만큼 증가하면 탐색해야할 데이터가 반으로 줄어든다. -> 평균 시간복잡도: O(logn)
- But!! 가장 최악의 경우에는 링크드 리스트와 동일한 성능 -> 최악 시간복잡도: O(n)
반응형'IT > 자료구조 & 알고리즘' 카테고리의 다른 글
[알고리즘] 버블정렬(Bubble Sort) (Python) (0) 2021.07.29 [자료구조] 힙(Heap) (Python) (0) 2021.07.29 [자료구조] 해쉬 테이블(Hash table) (Python) (0) 2021.07.28 [자료구조] 링크드 리스트 (Linked List) (Python) (0) 2021.07.28 댓글