Data Structures and Algorithms (4)
9360 ワード
Data Structure and Algorithms (4)
1.ツリー（Tree）
≪構造｜Structure｜oraolap≫:ツリー・ノードとブランチを使用してデータ構造をループなしに構成
使用:バイナリツリー/ブラウズ(検索)アルゴリズムの実装
用語
node , root node , level , parent node , child node , leaf node , sibling/brother node , depth種類
1)バイナリツリー:最大2ブランチ
2)バイナリプローブツリー(BST):バイナリツリーであり、左ノードと右ノードはそれぞれ親ノードより小さいか大きい.
時間の複雑さ
深さ依存
O(h) = O(logn)
短所
1列のツリーでは、不要なナビゲーション時間が発生します.
この問題を解決するには、ツリーソートアルゴリズムが必要です.
delete
コード#コード#
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):
cur_node = self.head
ㅤ
while True:
if value < cur_node.value:
if cur_node.left != None:
cur_node = cur_node.left
else:
cur_node.left = Node(value)
break
else:
if cur_node.right != None:
cur_node = cur_node.right
else:
cur_node.right = Node(value)
break
ㅤ
def search(self, value):
cur_node = self.head
while cur_node:
if cur_node.value == value:
return True
elif value < cur_node.value:
cur_node = cur_node.left
else:
cur_node = cur_node.right
return False
ㅤ
def delete(self, value):
search = False
cur_node = self.head
ㅤ parent = self.head
ㅤ
# 해당 노드의 유무확인 및 삭제할 노드 업데이트
ㅤ while cur_node:
if cur_node.value == value:
search = True
break
elif value < cur_node.value:
parent = cur_node
cur_node = cur_node.left
else:
ㅤ parent = cur_node
cur_node = cur_node.right
ㅤ
if search == False:
return False
ㅤ
# case1 : 삭제할 노드가 leaf 노드인 경우
if cur_node.left == None and cur_node.right == None:
if value < parent.value:
parent.left = None
else:
parent.right = None
ㅤ del cur_node
ㅤ
# case2 : 삭제할 노드의 자식노드가 한 개인 경우
elif cur_node.left != None and cur_node.right == None:
if value < parent.value:
parent.left = cur_node.left
else:
parent.right = cur_node.left
elif cur_node.left == None and cur_node.right != None:
if value < parent.value:
parent.left = cur_node.right
else:
parent.right = cur_node.right
ㅤ
# case3 : 삭제할 노드의 자식노드가 두 개인 경우
elif cur_node.left != None and cur_node.right != None:
# case3-1 :
if value < parent.value:
change_node = cur_node.right
change_node_parent = cur_node.right
while change_node.left != None:
change_node_parent = change_node
change_node = change_node.left
if change_node.right != None:
change_node_parent.left = change_node.right
else:
change_node_parent.left = None
parent.left = change_node
change_node.right = cur_node.right
change_node.left = cur_node.left
# case3-2 :
else:
ㅤ change_node = cur_node.right
change_node_parent = cur_node.right
while change_node.left != None:
change_node_parent = change_node
change_node = change_node.left
if change_node.right != None:
change_node_parent.left = change_node.right
ㅤ else:
change_node_parent.left = None
ㅤ parent.right = change_node
change_node.right = cur_node.right
change_node.left = cur_node.left
ㅤ
--------------------------------------------------------------------
head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
print(BST.search(2))
--------------------------------------------------------------------
import random
ㅤ
BST_num = set()
while len(BST_num) != 100:
ㅤ BST_num.add(random.randint(0, 999))
ㅤ
head = Node(500)
BST = NodeMgmt(head)
for num in BST_num:
if BST.search(num) == False:
print('search failed')
ㅤ
delete_num = set()
BST_num = list(BST_num)
while len(delete_num) != 10:
delete_num.add(BST_num[random.randint(0, 99)])
ㅤ
for del_num in delete_num:
if BST.delete(del_num) == False:
print('delete failed', del_num)2.お尻
構造:Max/Min Heap->ルートディレクトリの最大/最小値
目的:データから最小値と最大値をすばやく取得するバイナリツリー
なぜお尻を使うのですか?
1)配列にデータを入れ、最大値/最小値を検索します.
*配列にデータを入れて検索し、O(n)/HIPにデータを入れ、O(logn)にデータを入れる
2)最大値または最小値(優先順位キューなど)の迅速な検索が必要なデータ構造およびアルゴリズムの実装
バイナリ探索木VSお尻
1)共通点:バイナリツリー
2)違い:バイナリプローブツリー-左右比較サイズ/hip-最大値のみ
class Heap:
def __init__(self, data):
self.heap = list()
self.heap.append(None)
self.heap.append(data)
ㅤㅤ
def move_up(self, insert_idx):
if insert_idx <= 1:
return False
parent_idx = insert_idx // 2
if self.heap[insert_idx] > self.heap[parent_idx]:
return True
else:
return False
ㅤㅤ
def move_down(self, pop_idx):
left_child_pop_idx = pop_idx * 2
right_child_pop_idx = pop_idx * 2 + 1
ㅤ
# case1 왼쪽 자식노드 없을때
if left_child_pop_idx >= len(self.heap):
return False
ㅤ
# case2 오른쪽 자식노드만 없을때
elif right_child_pop_idx >= len(self.heap):
if self.heap[pop_idx] < self.heap[left_child_pop_idx]:
#아직 max_heapify 이루어지지 않음
return True
else:
return False
ㅤ
# case3 오른쪽 왼쪽 다 있을때
else:
if self.heap[left_child_pop_idx] > self.heap[right_child_pop_idx]:
if self.heap[pop_idx] < self.heap[left_child_pop_idx]:
return True
else:
return False
else:
if self.heap[pop_idx] < self.heap[right_child_pop_idx]:
return True
else:
return False
ㅤ
def insert(self, data):
if len(self.heap) == 0:
self.heap.apppend(None)
self.heap.append(data)
return True
ㅤ
self.heap.append(data)
ㅤ
insert_idx = len(self.heap) - 1
ㅤ
while self.move_up(insert_idx):
parent_idx = insert_idx // 2
self.heap[insert_idx], self.heap[parent_idx] = \
self.heap[parent_idx], self.heap[insert_idx]
insert_idx = parent_idx
return True
ㅤ
def pop(self):
if len(self.heap) <= 1:
return None
ㅤ
return_data = self.heap[1]
self.heap[1] = self.heap[-1]
del self.heap[-1]
poped_idx = 1
ㅤ
while self.move_down(poped_idx):
left_child_pop_idx = poped_idx * 2
right_child_pop_idx = poped_idx * 2 + 1
ㅤ
# case2 오른쪽 자식노드만 없을때
if right_child_pop_idx >= len(self.heap):
if self.heap[poped_idx] < self.heap[left_child_pop_idx]:
self.heap[poped_idx], self.heap[left_child_pop_idx] = \
ㅤ self.heap[left_child_pop_idx], self.heap[poped_idx]
poped_idx = left_child_pop_idx
ㅤ
# case3 오른쪽 왼쪽 다 있을때
else:
if self.heap[left_child_pop_idx] > self.heap[right_child_pop_idx]:
if self.heap[poped_idx] < self.heap[left_child_pop_idx]:
self.heap[poped_idx], self.heap[left_child_pop_idx] = \
self.heap[left_child_pop_idx], self.heap[poped_idx]
poped_idx = left_child_pop_idx
else:
if self.heap[poped_idx] < self.heap[right_child_pop_idx]:
self.heap[poped_idx], self.heap[right_child_pop_idx] = \
self.heap[right_child_pop_idx], self.heap[poped_idx]
poped_idx = right_child_pop_idx
ㅤ
return return_data
ㅤ
--------------------------------------------------------
heap = Heap(1)
ㅤ
for i in range(2,99):
heap.insert((i))
ㅤ
print(heap.heap)
ㅤ
for i in range(2,99):
print(heap.pop())
print(heap.heap)본 게시글은 fastcampus 이준희강사 수업을 듣고 개인적으로 정리한 내용임을 밝힘.Reference
この問題について(Data Structures and Algorithms (4)), 我々は、より多くの情報をここで見つけました https://velog.io/@anthony16/자료구조-및-알고리즘-4テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol