- 트리(Tree)
- Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조
- 트리 중 이진 트리(Binary Tree) 형태의 구조로 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
-
알아둘 용어
- Node: 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 Branch 정보를 포함)
- Root Node: 트리 맨 위에 있는 노드
- Level : 최상위 노드를 Level 0으로 했을 때 하위 branch로 연결된 노드의 깊이를 나타냄
- Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
- Child Node: 어떤 노드의 하위 레벨에 연결된 노드
- Leaf Node: Child Node가 하나도 없는 노드
- Sibling Node: 동일한 Parent Node를 가진 노드
-
이진 트리와 이진 탐색 트리 (Binary Search Tree)
- 이진 트리: 노드의 최대 Branch가 2개인 트리
- 이진 탐색 트리(Binary Search Tree, BST): 이진 트리에 추가적인 조건이 있는 트리
- 왼쪽 노드는 해당 노드보다 작은 값이며, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있다
- 왼쪽 노드는 해당 노드보다 작은 값이며, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있다
-
자료 구조 이진 탐색 트리의 장점과 주요 용도
- 주요 용도: 데이터 검색(탐색)
- 장점: 탐색 속도를 개선할 수 있음
- 단점: 이진 탐색 트리 알고리즘 이해 후에 살펴봐야 함
-
파이썬 객체 지향 프로그래밍으로 이진 탐색 트리 구현하기
-
노드 클래스 만들기
class Node: def __init__(self, value): self.value = value self.left = None self.right = None -
이진 탐색 트리에 데이터 넣기
- 조건: 중복 데이터를 넣지 않음
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 -
이진 탐색트리의 검색
class NodeMgmt: def __init__(self, head): self.head = head def search(self,value): self.current_node = self.head while self.current_node: # 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 # 찾지 못했을 때 -
이진 탐색 트리의 삭제
- Leaf Node 삭제
- Leaf Node: Child Node가 없는 Node
- 삭제할 Node의 Parent Node가 Node를 가리키지 않도록 함
-
삭제할 노드 탐색
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 False1-2. 삭제할 노드가 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 # 부모노드의 오른쪽값 삭제1-3. Child Node 가 하나인 node를 삭제
- 삭제할 node의 Parent Node가 삭제할 Node의 Child Node를 가리키게 함
# 현재노드값의 왼쪽값이 있고 오른쪽값이 없을 때 if 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.parrent.left = self.current_node.right else: self.parent.right = self.current_node.right1-4. Child Node가 두 개인 Node를 삭제
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 함
- 삭제할 Node가 Parent Node 왼쪽에 있을 때
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 있을 때
- 삭제할 Node가 Parent Node 오른쪽에 있을 때
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 있을 때
가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 절대 없음. 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 존재한다는 뜻이기 때문
- 삭제할 Node가 Parent Node 왼쪽에 있을 때
1-5. Child Node가 두 개인 Node를 삭제하는 코드 구현하기
- 삭제할 Node의 오른쪽 자식을 선택
- 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
- 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Childe Node를 가리키게 함
- 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
- 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
- 만약 해당 Node가 오른쪽 Childe Node를 가지고 있었을 경우, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함
# 현재 노드의 왼쪽,오른쪽 값이 있을 때 if self.current_node.left != None and self.current_node.right != None: 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.current_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.right = self.current_node.right self.change_node.left = self.current_node.left
- Leaf Node 삭제
-
tistory로 이전! https://sweet-rain-kim.tistory.com/