面接準備/資料構造7/ツリー
代表的なデータ構造7:ツリー
1.ツリー構造
2.必要な用語
3.バイナリツリーとバイナリ検索ツリー
(出典:https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)
4.資料構造バイナリナビゲーションツリーの利点と主な用途
欠点は、バイナリナビゲーションツリーアルゴリズムを理解してから表示する必要があることです.
バイナリツリーと整列配列間のナビゲーション比較
(出典:https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)
5.オブジェクト向けPythonプログラミングによるリンクリストの実装
5.1. ノードクラスの作成
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
5.2. バイナリナビゲーションツリーにデータを入れる
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
head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
5.3. バイナリツリーナビゲーション
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
head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)
BST.insert(0)
BST.insert(4)
BST.insert(8)
BST.search(-1)
5.4. バイナリナビゲーションツリーの削除
5.4.1. Leafノードの削除
5.4.2. Childノードが1つしかないノードを削除
5.4.3. 2つのChild NodeのNodeを削除
削除するノードの右側のサブノード
右サブアイテムの一番左のノード
5.5. バイナリナビゲーションツリー削除コードの実装と分析
5.5.1削除するノードへ移動
削除するノード
# 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
### 이후부터 Case들을 분리해서, 코드 작성
5.5.2. ケース1:削除するノードがLeaf Nodeの場合
# self.current_node 가 삭제할 Node, self.parent는 삭제할 Node의 Parent 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
5.5.2. Case 2:削除するノードがChildノードが1つしかない場合。
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.parent.left = self.current_node.right
else:
self.parent.right = self.current_node.right
5.5.3. Case 3-1:削除するノードにChildノードが2つある場合(削除するノードがParentノードの左側にある場合)
if self.current_node.left != None and self.current_node.right != None: # case3
if value < self.parent.value: # case3-1
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
5.5.4. Case 3-2:削除するノードに2つのChildノードがある場合(削除するノードがParentノードの右側にある場合)
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
5.5.5. Pythonフルコードの実装
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
注意:http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html5.5.6. Pythonフルコードのテスト
# 0 ~ 999 숫자 중에서 임의로 100개를 추출해서, 이진 탐색 트리에 입력, 검색, 삭제
import random
# 0 ~ 999 중, 100 개의 숫자 랜덤 선택
bst_nums = set()
while len(bst_nums) != 100:
bst_nums.add(random.randint(0, 999))
# print (bst_nums)
# 선택된 100개의 숫자를 이진 탐색 트리에 입력, 임의로 루트노드는 500을 넣기로 함
head = Node(500)
binary_tree = NodeMgmt(head)
for num in bst_nums:
binary_tree.insert(num)
# 입력한 100개의 숫자 검색 (검색 기능 확인)
for num in bst_nums:
if binary_tree.search(num) == False:
print ('search failed', num)
# 입력한 100개의 숫자 중 10개의 숫자를 랜덤 선택
delete_nums = set()
bst_nums = list(bst_nums)
while len(delete_nums) != 10:
delete_nums.add(bst_nums[random.randint(0, 99)])
# 선택한 10개의 숫자를 삭제 (삭제 기능 확인)
for del_num in delete_nums:
if binary_tree.delete(del_num) == False:
print('delete failed', del_num)
6.バイナリナビゲーションツリーの時間的複雑さと欠点
6.1. 時間の複雑さ(ナビゲート時)
-実行するたびに実行可能なコマンドの50%が削除されることを意味します.これは、稼働時間を50%削減できることを意味します.
6.2. バイナリナビゲーションツリーの欠点
Reference
この問題について(面接準備/資料構造7/ツリー), 我々は、より多くの情報をここで見つけました https://velog.io/@bbkyoo/면접준비자료구조7트리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol