20、21講:バイナリ検索ツリー
11030 ワード
20強サマリー
バイナリツリーのブラウズ、挿入などの機能を実現
20話の内容
探索する
lookup()
:特定の要素の検索(ナビゲーション)class Node:
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
class BinSearchTree:
def lookup(self,key):
if self.root:
return self.root.lookup(key)
else:
return None, None
最高価格と最低価格
max()
:最大キーを持つ要素に移動class Node:
def max(self):
if self.right:
return self.right.max()
else:
return self
class BinSearchTree:
def max(self):
if self.root:
return self.root.max()
else:
return None
min()
:最小キーを持つ要素に移動class Node:
def min(self):
if self.left:
return self.left.min()
else:
return self
class BinSearchTree:
def min(self):
if self.root:
return self.root.min()
else:
return None
挿入
insert()
:指定されたデータ要素をツリーに追加class Node:
def insert(self,key,data):
if key < self.key: #작을때
if self.left: #왼쪽 서브트리가 존재
self.left.insert(key,data) #왼쪽 서브트리로 이동
else: #왼쪽 서브트리가 존재x
node = Node(key,data) #노드 만들어
self.left = node #왼쪽 자식연결
elif key > self.key: #클때
if self.right: #오른쪽 서브트리가 존재
self.right.insert(key,data) #오른쪽 서브트리로 이동
else: #오른쪽 서브트리가 존재x
node = Node(key,data) #노드만들어
self.right = node #오른쪽 자식연결
else: #키 중복
raise KeyError #에러
class BinSearchTree:
def insert(self,key,data):
if self.root:
self.root.insert(key, data)
else:
self.root = Node(key, data)
質問する
バイナリナビゲーションツリーの要素挿入演算の実装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: #왼쪽 서브트리가 존재x
node = Node(key,data) #노드 만들어
self.left = node #왼쪽 자식연결
elif key > self.key: #클때
if self.right: #오른쪽 서브트리가 존재
self.right.insert(key,data) #오른쪽 서브트리로 이동
else: #오른쪽 서브트리가 존재x
node = Node(key,data) #노드만들어
self.right = node #오른쪽 자식연결
else: #키 중복
raise KeyError #에러
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
21課概要
バイナリ・ナビゲーション・ツリーから削除し、サブノード数を実装します.
21課の内容
サブノード数
簡単に言えば、左、右サブノードがあるかどうか、あれば+1
を加えます.class Node:
def countChildren(self):
count = 0
if self.left: #좌
count += 1
if self.right: #우
count += 1
return count
削除
remove()
:ツリーから特定の要素を削除class BinSearchTree:
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
elif 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:
child = node.left
else:
child = node.right
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
if parent:
if parent.left == node:
parent.left = child
elif parent.right == node:
parent.right = child
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 에 위에서 가리킨 자식을 대신 넣습니다.
else:
self.root = child
# 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 = parent.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
質問する
バイナリナビゲーションツリーでのノードの削除操作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()
if nChildren == 0:
if parent:
if parent.left == node:
parent.left = None
elif parent.right == node:
parent.right = None
else:
self.root = None
elif nChildren == 1:
if node.left:
child = node.left
else:
child = node.right
if parent:
if parent.left == node:
parent.left = child
elif parent.right == node:
parent.right = child
else:
self.root = child
else:
parent = node
successor = node.righㅅ
while successor.left:
parent = successor
successor = parent.left
node.key = successor.key
node.data = successor.data
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
Github
https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/20%2C21%EA%B0%95/20%2C21%EA%B0%95.py
Reference
この問題について(20、21講:バイナリ検索ツリー), 我々は、より多くの情報をここで見つけました
https://velog.io/@ds02168/2021강-이진-탐색-트리Binary-Search-Trees
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
class Node:
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
class BinSearchTree:
def lookup(self,key):
if self.root:
return self.root.lookup(key)
else:
return None, None
class Node:
def max(self):
if self.right:
return self.right.max()
else:
return self
class BinSearchTree:
def max(self):
if self.root:
return self.root.max()
else:
return None
class Node:
def min(self):
if self.left:
return self.left.min()
else:
return self
class BinSearchTree:
def min(self):
if self.root:
return self.root.min()
else:
return None
class Node:
def insert(self,key,data):
if key < self.key: #작을때
if self.left: #왼쪽 서브트리가 존재
self.left.insert(key,data) #왼쪽 서브트리로 이동
else: #왼쪽 서브트리가 존재x
node = Node(key,data) #노드 만들어
self.left = node #왼쪽 자식연결
elif key > self.key: #클때
if self.right: #오른쪽 서브트리가 존재
self.right.insert(key,data) #오른쪽 서브트리로 이동
else: #오른쪽 서브트리가 존재x
node = Node(key,data) #노드만들어
self.right = node #오른쪽 자식연결
else: #키 중복
raise KeyError #에러
class BinSearchTree:
def insert(self,key,data):
if self.root:
self.root.insert(key, data)
else:
self.root = Node(key, data)
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: #왼쪽 서브트리가 존재x
node = Node(key,data) #노드 만들어
self.left = node #왼쪽 자식연결
elif key > self.key: #클때
if self.right: #오른쪽 서브트리가 존재
self.right.insert(key,data) #오른쪽 서브트리로 이동
else: #오른쪽 서브트리가 존재x
node = Node(key,data) #노드만들어
self.right = node #오른쪽 자식연결
else: #키 중복
raise KeyError #에러
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
バイナリ・ナビゲーション・ツリーから削除し、サブノード数を実装します.
21課の内容
サブノード数
簡単に言えば、左、右サブノードがあるかどうか、あれば
+1
を加えます.class Node:
def countChildren(self):
count = 0
if self.left: #좌
count += 1
if self.right: #우
count += 1
return count
削除
remove()
:ツリーから特定の要素を削除class BinSearchTree:
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
elif 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:
child = node.left
else:
child = node.right
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
if parent:
if parent.left == node:
parent.left = child
elif parent.right == node:
parent.right = child
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 에 위에서 가리킨 자식을 대신 넣습니다.
else:
self.root = child
# 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 = parent.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
質問する
バイナリナビゲーションツリーでのノードの削除操作
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()
if nChildren == 0:
if parent:
if parent.left == node:
parent.left = None
elif parent.right == node:
parent.right = None
else:
self.root = None
elif nChildren == 1:
if node.left:
child = node.left
else:
child = node.right
if parent:
if parent.left == node:
parent.left = child
elif parent.right == node:
parent.right = child
else:
self.root = child
else:
parent = node
successor = node.righㅅ
while successor.left:
parent = successor
successor = parent.left
node.key = successor.key
node.data = successor.data
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
Github
https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/20%2C21%EA%B0%95/20%2C21%EA%B0%95.py
Reference
この問題について(20、21講:バイナリ検索ツリー), 我々は、より多くの情報をここで見つけました
https://velog.io/@ds02168/2021강-이진-탐색-트리Binary-Search-Trees
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
Reference
この問題について(20、21講:バイナリ検索ツリー), 我々は、より多くの情報をここで見つけました https://velog.io/@ds02168/2021강-이진-탐색-트리Binary-Search-Treesテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol