기본 시작 틀
- 링크드 리스트와 흡사
안 보더라도 이것만은 기억하자
각 노드의 좌측에는 작은 숫자, 우측에는 큰 숫자가 저장된다.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class NodeMgmt:
def __init__(sel, value):
self.head = head삽입
- case 1 : 삽입하는 데이터 값이 현재 노드의 데이터 값 보다 작고 왼쪽 값이 비어 있으면 삽입
- case 2 : 삽입하는 데이터 값이 현재 노드의 테이터 값 보다 크고 오른쪽 값이 비어 있으면 삽입
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class NodeMgmt:
def __init__(self, value):
self.head = head
def insert(self, value):
self.current_node = self.head
while True:
# 넣으려는 데이터가 현재 노드의 데이터보다 작니?
if value < self.current_node.value:
# 작다면 노드의 왼쪽이 None이냐
if self.current_node.left != None:
#None이 아니라면 현재 노드에 현재 노드의 왼쪽 노드를 대입
self.current_node = self.current_node.left
else:
#None이라면 현재 노드의 왼쪽에 노드를 생성하여 대입
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삭제
- 자식 노드가 없다면 그냥 삭제
- 자식 노드가 하나라면 빼고 이어주면 된다.
- 하지만 가지가 두 개라면?!오른쪽 자식노드의 가장 작은 놈으로 바꾸기!!(왼쪽 가장 큰 노드로도 가능)
설명을 위한 지칭
- 타노드 : 타겟 노드
- 타부노드 : 타겟 노드의 부모 노드
- 오가작노드 : 타겟 노드의 오른쪽 자식 노드의 가장 작은 노드
- 오가작부노드 : 타겟 노드의 오른쪽 자식 노드의 가장 작은 노드의 부모 노드
흐름
- 타겟 노드(타노드)와 타겟 노드의 부모 노드(타부노드)를 구한다
- case 1 : 타노드의 자식 노드가 하나도 없을 때 없을 때
- 타부노드의 왼쪽, 오른쪽인지 판별 후 None처리
- case 2 : 타노드의 자식 노드가 둘 다 있을 때
- 오른쪽 자식 노드들 중 가장 작은 노드(오가작노드)와 그 노드의 부모 노드(오가작부노드)를 찾는다
- case2-1) 경우 1 : 오가작부노드가 head(가장 꼭대기)일 때는, 오가작부노드의 오른쪽에 오가작노드의 오른쪽을 연결.
- case2-2) 경우 2 : 오가작부노드가 head가 아닐 때는, 오가작부노드의 왼쪽과 오가작노드의 오른쪽을 이어준다.
- case 3 : 타노드의 자식이 오른쪽이나 왼쪽 하나 있을 때 (위에서 둘 다 없을 때, 있을 때의 경우를 나눴으므로 무조건 왼,오 중 하나만 있음)
- 타노드가 head인지 확인 후 처리(추가)
- 타노드가이 타부노드의 오른쪽에 있는지 왼쪽에 있는지 판별
- 타노드의 자식이 오른쪽에 있는지 왼쪽에 있는지 판별 후 연결
왜 case 2 에서 두 가지 경우로 나뉘나?
- 타겟 노드의 바로 오른쪽 자식의 가장 작은 노드를 찾고(오가작노드)
- 그 노드는 가장 작은 값이나 오른쪽으로 뻗은 가지가 있을 수 있다.
- 이런 경우 그 오른쪽으로 뻗은 가지를 부모 노드(오가작부노드)의 왼쪽과 연결해 줘야한다.
- 그러나 오가작부 노드가 head(가장 꼭대기)일 때, head의 왼쪽과 연결하면 데이터가 덮어씌워지고 트리의 조건이 깨진다.
- 그래서 오가작부 노드가 head일 때를 따로 처리해주는 것
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class NodeMgmt:
def __init__(self, value):
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 delete(self,value):
# 타노드와 타부노드 초기 시작 설정
self.target_node = self.head
self.target_parent_node = self.target_node
# 타노드와 타부노드 찾기(데이터 값이 같을 때 까지)
while self.target_node.value != value:
self.target_parent_node = self.target_node
if self.target_node.value > value:
self.target_node = self.target_node.left
else:
self.target_node = self.target_node.right
#case 1 타노드의 자식 노드가 하나도 없을 경우
if self.target_node.left == None and self.target_node.right == None:
# 타노드가 타부노드의 왼쪽이냐 오른쪽이냐 판별 후 타부노드에서 가지치기
if self.target_node == self.target_parent_node.left:
self.target_parent_node.left = None
else:
self.target_parent_node.right = None
return True
else:
#case 2 타노드의 자식 노드가 둘 다 있을 때
if self.target_node.left and self.target_node.right:
print('case3')
# 오가작노드와 오가작부노드 초기 설정
self.right_min_node = self.target_node.right
self.min_parent_node = self.target_node
# 오가작노드와 오가작부노드 찾기(가장 왼쪽 노드 찾기)
while self.right_min_node.left:
self.min_parent_node = self.right_min_node
self.right_min_node = self.right_min_node.left
# case 2 - 1 : 오가작부노드가 head인가요?
if self.min_parent_node == self.head:
# 맞다면 오가작부노드의 오른쪽에 오가작노드의 오른쪽을 연결
self.min_parent_node.right = self.right_min_node.right
self.head.value = self.right_min_node.value
else:
# 아니라면 오가작부노드의 왼쪽에 오가작노드의 오른쪽을 연결
self.min_parent_node.left = self.right_min_node.right
self.target_node.value = self.right_min_node.value
return True
#case 3 자식이 하나만 있을 때
# 타노드가 헤드와 같냐
if self.target_node == self.head:
if self.target_node.left:
self.head = self.target_node.left
else:
self.head = self.target_node.right
# 타겟이 부모의 오른쪽에 있는지 왼쪽에 있는지 판별
elif self.target_parent_node.left == self.target_node:
# 타겟이 왼쪽, 오른쪽 어느 자식이 있는지 판별하고 연결
if self.target_node.left:
self.target_parent_node.left = self.target_node.left
else:
self.target_parent_node.left = self.target_node.right
else:
if self.target_node.left:
self.target_parent_node.right = self.target_node.left
else:
self.target_parent_node.right = self.target_node.right
del self.target_node
return True검색을 추가한 코드 + 트리를 볼 수 있는 코드
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class NodeMgmt:
def __init__(self, value):
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 self.current_node.value > value:
self.current_node = self.current_node.left
else:
self.current_node = self.current_node.right
return False
def delete(self,value):
if self.search(value) == False:
return False
self.target_node = self.head
self.target_parent_node = self.target_node
while self.target_node.value != value:
self.target_parent_node = self.target_node
if self.target_node.value > value:
self.target_node = self.target_node.left
else:
self.target_node = self.target_node.right
if self.target_node.left == None and self.target_node.right == None:
if self.target_node == self.target_parent_node.left:
self.target_parent_node.left = None
else:
self.target_parent_node.right = None
return True
else:
if self.target_node.left and self.target_node.right:
self.right_min_node = self.target_node.right
self.min_parent_node = self.target_node
while self.right_min_node.left:
self.min_parent_node = self.right_min_node
self.right_min_node = self.right_min_node.left
if self.min_parent_node == self.head:
self.min_parent_node.right = self.right_min_node.right
self.head.value = self.right_min_node.value
else:
self.min_parent_node.left = self.right_min_node.right
self.target_node.value = self.right_min_node.value
return True
if self.target_parent_node.left == self.target_node:
if self.target_node.left:
self.target_parent_node.left = self.target_node.left
else:
self.target_parent_node.left = self.target_node.right
else:
if self.target_node.left:
self.target_parent_node.right = self.target_node.left
else:
self.target_parent_node.right = self.target_node.right
return Truedef view(node):
if node == None:
return []
return view(node.left)+ [node.value] + view(node.right)사용해보기
head = Node(10)
tree1 = NodeMgmt(head)
tree1.insert(5)
tree1.insert(3)
tree1.insert(7)
tree1.insert(6)
tree1.insert(15)
tree1.insert(19)
tree1.insert(18)
tree1.insert(11)
tree1.insert(13)
tree1.insert(20)view(head)[3, 5, 6, 7, 10, 11, 13, 15, 18, 19, 20]tree1.delete(20)
view(head)[3, 5, 6, 7, 10, 11, 13, 15, 18, 19]tree1.delete(11)
view(head)[3, 5, 6, 7, 10, 13, 15, 18, 19]tree1.delete(10)
view(head)[3, 5, 6, 7, 13, 15, 18, 19]강의에서 나온 코드(내것 보다 더 정확할 것)
- 혼자 생각하면서 코드를 잘 짰다고 생각했으나
- 부족한 점은 많을 것이다. 그러므로 강의의 코드도 추가해두겠다.
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
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
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
적은 대로 된다.