binary treeについて
date: 2021-03-28 excerpt: binary tree(二分木)について
binary tree(二分木)について
- binary search(二分探索)に名前が似ているが別のものである
- 特性自体は似ており、検索コストが
O(log n)である
- 特性自体は似ており、検索コストが
- 木構造にデータを埋め込むことで、並び順を維持したままデータの追加削除、検索ができる
- ヒープの実装元にもなっており、
O(log n)で最大値、最小値を計算できる - C++だと、
std::setとstd::mapの実装が二分木になっており、最小と最大が一瞬で求められる
ランダウ表記
- 平均と最悪ケースが存在する
| algorithm | average | worst case |
|---|---|---|
| space | O(n) | O(n) |
| find | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
pythonの実装
class Node:
def __init__(self, v):
self.left = None
self.right = None
self.v = v
def insert(self, v):
if self.v:
if v < self.v:
if self.left is None:
self.left = Node(v)
else:
self.left.insert(v)
elif v > self.v:
if self.right is None:
self.right = Node(v)
else:
self.right.insert(v)
else:
self.v = v
def find(self, v):
if self.v == v:
return "found"
if v < self.v:
if self.left is None:
return "not found"
else:
return self.left.find(v)
elif v > self.v:
if self.right is None:
return "not found"
else:
return self.right.find(v)
def get_min(self):
current = self
while(current.left is not None):
current = current.left
return current.v
def get_max(self):
current = self
while(current.right is not None):
current = current.right
return current.v
def print_tree(self):
if self.left:
self.left.print_tree()
print(self.v, end=", ")
if self.right:
self.right.print_tree()
@staticmethod
def delete(node, v):
"""
再帰的に一致したノードと、一致したノードの傘下のノードを消していく
"""
if node is None:
return node
if v < node.v:
node.left = node.delete(node.left, v)
elif v > node.v:
node.right = node.delete(node.right, v)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
temp = node.get_min(node.right)
node.v = temp.v
node.right = node.delete(node.right, temp.v)
return node
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.insert(1)
root.insert(-10)
# 値の検索
print(root.find(1))
print(root.find(2))
print(root.find(200))
# 最小値を取得
print(root.get_min()) # -10
# 最大値を取得
print(root.get_max()) # 14
root.print_tree() # -10, 1, 3, 6, 12, 14,
root.delete(root, 1)
root.delete(root, 14)
print()
print(root.print_tree()) # -10, 3, 6, 12, None