木.
📌木。
これは2 D資料構造です.頂点(node)と幹線(edge)抽象データ配置形式を用いたデータ構造
ノード(nodes):通常、A、B、C~と表される値
幹線(エッジ):ノードを接続する線
ルートノード(root node):一番上のノード
リーフノード:一番下のノード.枝がない
内部ノード(内部ノード):ルートノードでもリーフノードでもない
親(親)ノードと子(子)ノード:ルートに近いノードを親ノード、リーフに近いノードを子ノードと呼びます.各ノードには複数のサブノードがありますが、親ノードは1つしかありません.
ノードのレベル(level):ルートノードのlevel:0で、edgeからなる下位レベルまで1増加します.ルートノードからノードへのedge数、すなわちノードのlevel
ノードの回数(度数):サブノード(サブツリー)の数.ノードが延びるedgeの数.エンドノード(leaf)の次元数は0です.
ツリーの高さ(height)または深さ(depth):ツリーの高さ(height)=最大レベル(level)+1.ルートノードのレベルを1に設定すると、エンドノードのレベルはツリーの高さと同じになります.
部分ツリー(サブツリー;サブツリー):あるノードに対するツリー
≪バイナリ・ツリー|Binary Tree|oraolap≫:すべてのノードの回数が2未満のツリー.再定義可能->(空のツリーまたはルートノード+左サブツリー+右サブツリーの場合)
飽和バイナリツリー(full binary trees):すべてのレベルでノードが埋め込まれたバイナリツリー(高さk、ノード数2 k-1のバイナリツリー)
完全二叉木(complete binary trees):高さkの完全二叉木(レベルk-2のすべてのノードに2つのサブノードの飽和二叉木があり、レベルk-1は左から右に順にノードの二叉木を充填する)
バイナリツリーの抽象データ構造
size()-現在のツリーに含まれるノード数を取得します.
depth()-現在のツリーの深さ(または高さ)を求めます.
「ループ」(Transversal)-指定した順序でノードにアクセスして処理します.
バイナリツリーの実装-ノード(ノード)
class Node:
def __init__(self, item): # Node에는 Data와 Left Child, Right Child를 가리키는 정보가 있다.
# (양방향 연결 리스트의 prev, next와 비슷)
self.data = item
self.left = None
self.right = None
def size(self): # 재귀적으로 구할 수 있다.
# 전체 이진 트리 size() : 왼쪽 서브트리 size() + 오른쪽 서브트리 size() + 1(자기 자신)
l = self.left.size() if self.left else 0
r = self.right.size() if self.right else 0
return l + r + 1
def depth(self): # 재귀적으로 구할 수 있다.
# 전체 이진 트리 depth() : 왼쪽 서브트리 depth()와 오른쪽 서브트리 depth()중 더 큰 것 + 1(자기 자신)
l = self.left.depth() if self.left else 0
r = self.right.depth() if self.right else 0
# if l > r:
# return l + 1
# elif r > l:
# return r + 1
return max(l, r) + 1
def inorder(self): # 중위 순회 - 1. 왼쪽 서브트리 2. 자기자신 3. 오른쪽 서브트리
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self.data)
if self.right:
traversal += self.right.inorder()
return traversal
def preorder(self): # 전위 순회 - 1. 자기자신 2. 왼쪽 서브트리 3. 오른쪽 서브트리
traversal = []
traversal.append(self.data)
if self.left:
traversal += self.left.preorder()
if self.right:
traversal += self.right.preorder()
return traversal
def postorder(self): # 후위 순회 - 1. 왼쪽 서브트리 2. 오른쪽 서브트리 3. 자기자신
traversal = []
if self.left:
traversal += self.left.postorder()
if self.right:
traversal += self.right.postorder()
traversal.append(self.data)
return traversal
class BinaryTree:
def __init__(self, r): # 루트 노드만 알고 있으면 그 자식 노드들의 edge로 나머지 노드들을 가르키고 있다.
self.root = r
def size(self):
if self.root:
return self.root.size()
else: # 빈 트리일 경우
return 0
def depth(self):
if self.root:
return self.root.depth()
else:
return 0
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
def preorder(self):
if self.root:
return self.root.preorder()
else:
return []
def postorder(self):
if self.root:
return self.root.postorder()
else:
return []
def bft(self): # 넓이 우선 순회
traversal = []
q = ArrayQueue()
if self.root == None:
return traversal
else:
q.enqueue(self.root)
while not q.isEmpty():
node = q.dequeue()
traversal.append(node.data)
if node.left and node.right:
q.enqueue(node.left)
q.enqueue(node.right)
continue
elif node.left:
q.enqueue(node.left)
elif node.right:
q.enqueue(node.right)
return traversal
def solution(x):
return 0トラバースツリー(Transversal-DFT,BFT)
深度優先順位(depth firstループ)
中位遍歴(in-order travelasl):左側のサブツリーを遍歴し、ノードx(自己)にアクセスし、右側のサブツリーを遍歴する
前列ループ(pre-orderループ):ノードxにアクセスし、左側のサブツリーをループし、最後に右側のサブツリーをループします.
後方ループ(post-orderループ):左サブツリーループ、右サブツリーループ、最後にノードxにアクセス
幅優先ループ
親ノードのアクセス順にアクセス
左サブノードにアクセスする前に右サブノードにアクセス
1つのノードにアクセスする場合は、後でアクセスするノードを順番に記録します.
->キューを使用します.再帰メソッドは使用しません.
任意の幅優先順位アルゴリズムの実現
3-1. q要素を抽出してnodeという変数にする
3-2. アクセスノード(ノードのデータを追加)
3-3. ノードの左、右サブノード(ある場合)をqに
バイナリ検索ツリー
すべてのノードについて、
左側のサブツリーのすべてのデータは、現在のノードの値よりも小さくなります.
右側のサブツリーのすべてのデータは、現在のノードの値よりも大きくなります.
性格を満たす李金樹!重複するデータ要素の値がないと仮定します.
アレイナビゲーションを使用するよりも、要素の追加、削除が容易ですが、スペースが大きくなります.
バイナリナビゲーションツリーの抽象データ構造
データ表示-各ノードは(key,value)ペアです.
Insert():指定したデータ要素をツリーに追加
remove():ツリーから特定の要素を削除する
lookup()lookup()lookup()lookup()lookup()lookup()lookup()lookup()lookup()lookup()lookup()lookup()lookup()lookup()lookup()
inorder():キー順にデータ要素をリストする
min()、max():最小キーと最大キーを持つ要素
min():左だけ探して、もっと値がなければ、自分に戻ります.最小値(最大()と対称)
lookup():パラメータを入力-検索するターゲットキー.戻る-見つかったノード、親ノード.それぞれが存在しない場合はNoneとして指定します
バイナリ・ツリーから要素を削除
キーにノードがない場合は削除する必要はありません
見つかったノードの親ノードも知っているはずです.
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:
if parent:
if parent.left == node:
parent.left = None
elif parent.right == node:
parent.right = None
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# parent.left 또는 parent.right 를 None 으로 하여
# leaf node 였던 자식을 트리에서 끊어내어 없앤다.
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 를 None 으로 하여 빈 트리로 만듦
else:
self.root = None
# When the node has only one child
elif nChildren == 1:
# 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
# 그 자식을 어떤 변수가 가리키도록 합니다.
if node.left:
s = node.left
else:
s = node.right
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
if parent:
if parent.left == node:
parent.left = s
elif parent.right == node:
parent.right = s
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 에 위에서 가리킨 자식을 대신 넣습니다.
else:
self.root = s
# 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 successor == parent.left:
# if successor.left or successor.right:
# 위의 while문에서 succesor의 왼쪽 자식이 없다는 것이 보장되었으니 필요 없는 코드
if successor.right:
parent.left = successor.right
else:
parent.left = None
elif successor == parent.right:
if successor.right:
parent.right = successor.right
else:
parent.right = None
return True
else:
return False
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
def solution(x):
return 0バイナリナビゲーションツリーの効率が悪い
->自分の役割を果たすには、高さが似ていて、左右対称です.片側に傾けると、時間が長くなり、線形配列に似ています.
パフォーマンスの向上したバイナリ・ナビゲーション・ツリー
->高度なバランスを保ち、O(longn)のナビゲーションの複雑さを確保します.挿入、削除操作がより複雑(AVL tree、Red-black treeリファレンスバイナリナビゲーションツリーには、構造を保持する制約があります)
Reference
この問題について(木.), 我々は、より多くの情報をここで見つけました https://velog.io/@yeonu/트리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol