728x90
반응형
이진 탐색트리:
모든 노드에 대해서 왼쪽 트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 노드는 반대 인 이진트리
힙큐랑은 다르다 힙큐는 맨 위 노드가 최솟값 노드
배열 이용/ 이진트리 이용
이진트리 :
장점 : 데이터 원소의 추가, 삭제가 용이
단점: 공간 소요가 큼
거의 O(logn) 임
노드는 키와 밸류를 가지고있음.
insert (key, data) - 추가
remove(key) - 삭제
lookup(key) - 찾기
inorder() - 키 순서대로 데이터 나열
min(),max() -최소 최대
원소 삽입 구현 (insert)
class Node:
def __init__(self, key, data):
self.key = key
self.data = data
self.left = None
self.right = None
def insert(self, key, data):
if self.key == key:
raise KeyError
if key < self.key: # 넘어온 키가 작으면서
if self.left: # 만약에 왼쪽에 있으면
self.left.insert(key,data)
else:
self.left = Node(key,data)
elif key >self.key: # 넘어온
if self.right:
self.right.insert(key,data)
else:
self.right = Node(key,data)
def inorder(self):
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self)
if self.right:
traversal += self.right.inorder()
return traversal
class BinSearchTree:
def __init__(self):
self.root = None
def insert(self, key, data):
if self.root:
self.root.insert(key, data)
else:
self.root = Node(key, data)
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
def solution(x):
return 0
이진 탐색 트리 에서 원소 제거 >> 좀 더 어려움
key를 이용해 노드를 찾는다.
- - 찾은 노드의 부모노드도 알고 있어야함
이유 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도로 트리의 구조를 정리해야하기 때문
입력 : key 출력: 삭제하면 True, 없으면 False
삭제되는 노드가
1.말단 노드 :
2.자식 하나 : 삭제되는 노드 자리에 그 자식을 대신 배치
3. 자식 둘 : 삭제되는 노드보다 바로 다음 큰 키를 가진 노드를 찾아 대신 배치하고 , 이 노드(갖다놓은)를 대신 삭제
오른쪽 자식에서 계속 왼쪽으로 따라간다 >> 6 (successer), 8(parent)
높이의 균형을 유지합으로써 O(logn) 의 탐색 복잡도 보장
삽입, 삭제 연산이 보다 복잡하다.
루트노드가 leaf노드인경우 트리 전체가 없어지는 식으로 코드를 짜줘야한다.
remove삭제 구현
class Node:
def __init__(self, key, data):
self.key = key
self.data = data
self.left = None
self.right = None
def insert(self, key, data):
if key < self.key:
if self.left:
self.left.insert(key, data)
else:
self.left = Node(key, data)
elif key > self.key:
if self.right:
self.right.insert(key, data)
else:
self.right = Node(key, data)
else:
raise KeyError('Key %s already exists.' % key)
def lookup(self, key, parent=None):
if key < self.key:
if self.left:
return self.left.lookup(key, self)
else:
return None, None
elif key > self.key:
if self.right:
return self.right.lookup(key, self)
else:
return None, None
else:
return self, parent
def inorder(self):
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self)
if self.right:
traversal += self.right.inorder()
return traversal
def countChildren(self):
count = 0
if self.left:
count += 1
if self.right:
count += 1
return count
class BinSearchTree:
def __init__(self):
self.root = None
def insert(self, key, data):
if self.root:
self.root.insert(key, data)
else:
self.root = Node(key, data)
def lookup(self, key):
if self.root:
return self.root.lookup(key)
else:
return None, None
def remove(self, key):
node, parent = self.lookup(key)
if node:
nChildren = node.countChildren()
# The simplest case of no children
if nChildren == 0:
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# parent.left 또는 parent.right 를 None 으로 하여
# leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
if parent:
if parent.left == node:
parent.left = None
if parent.right == node:
parent.right = None
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 를 None 으로 하여 빈 트리로 만듭니다.
else:
self.root = None
# When the node has only one child
elif nChildren == 1:
# 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
# 그 자식을 어떤 변수가 가리키도록 합니다.
if node.left:
now = node.left
else:
now = node.right
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
if parent:
if parent.left == node:
parent.left = now
else:
parent.right = now
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 에 위에서 가리킨 자식을 대신 넣습니다.
else:
self.root = now
# When the node has both left and right children
else:
parent = node
successor = node.right
# parent 는 node 를 가리키고 있고,
# successor 는 node 의 오른쪽 자식을 가리키고 있으므로
# successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
# 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
# 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아냅니다.
while successor.left:
parent = successor
successor = successor.left
# 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입합니다.
node.key = successor.key
node.data = successor.data
# 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
# 그에 따라 parent.left 또는 parent.right 를
# successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
if parent.left == successor:
parent.left = successor.right
else:
parent.right = successor.right
return True
else:
return False
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
def solution(x):
return 0반응형
댓글