Data Structure(2) - Graph, Tree, Binary Search Tree

Graph

グラフは、ノード(node)または頂点(渦)と、それらを接続する幹線(edge)から構成されます.方向がないかもしれないし、方向があるかもしれない.

隣接行列法はn*nからなる二次元配列で記述する方法である.幹線の有無は0と1のみで構成されており,データの変化に迅速に対応できるという利点があり,メモリ消費が大きいという欠点もある.

隣接リスト方式は,各ノードに接続ノードリストが1つある.メモリ数だけで使用できるメモリの利点と、隣接マトリクス方式に比べてアクセス速度が遅いという欠点があります.

これは現実生活でよく使われる資料構造です.代表的なものといえば、地図、ナビ、SNS注目ネットなど.

Params
ストレージスペースとしてのノード(空のオブジェクト)

Method
データを挿入するaddNode(Node)
contains(ノード)は、データが存在するかどうかを決定するために使用されます.
データを削除するremoveNode
haseEdge(ノードからノードへ)データ間の接続を確認する
接続データのaddEdge(ノードからノードまで)
ノードからノードへのデータ間の接続の削除
それ以外に、実装の程度にも依存します.

Psuedo Code

addNode(node) {
  // nodes에 node를 추가하고, 다른 노드와 연결 시 data를 추가할 빈 배열을 함께 넣어줌
}

contains(node) {
  // nodes의 key만 뽑아 node값을 includes하는지를 true/false로 반환
}

removeNode(node) {
  // 1. 해당 node의 키값쌍을 삭제 
  // 2. 객체를 순회하며 다른 node들에 있는 해당 node값을 삭제
}

hasEdge(fromNode, toNode) {
  // fromNode와 toNode가 서로의 값을 가지로 있는지 검사 후 true/false 반환
}

addEdge(fromNode, toNode) {
  // fromNode, toNode 서로의 값에 서로를 추가
}

removeEdge(fromNode, toNode) {
  // 1. fromNode에서 toNode를 찾아 삭제
  // 2. toNode에서 fromNode를 찾아 삭제
}

Tree

ツリーは、ノードからなる階層が明確なデータ構造です.最上位ノード(root)、ルートノードのchildを追加し、childにchildを追加することによって実現できます.親子関係が明確なので再帰構造です.
Treeも現実生活でよく使われる資料構造です.DOMからは,自動完了機能/探索に加えて,Treeから派生したアプリケーションTree構造が数多く存在する.

Params
データを格納する値
サブデータ

Method
insertNode(value)ルートディレクトリのサブディレクトリにデータを追加
contains(value)は、値が存在するかどうかを決定するために使用されます.
それ以外に、実装の程度にも依存します.

Psuedo Code

insertNode(value) {
  // 1. children에 새로운 treeNode instance 추가
  // 2. 추가한 node에 value 추가
}

contains(value) {
  // 1.children을 조회해 해당 value가 있는지 검사하는 함수 하나 만들기 (재귀)
  // 2. 찾으면 true를 반환 (탈출)
  // 2-1. value를 찾지 못하고 chilren이 존재하면 재귀
}

BST(Binary Search Tree)

バイナリ検索ツリー(BST,バイナリ検索ツリー)ツリーから派生した構造.rootを含むすべてのノードには、最大2つのサブノードしかありません.
子どもの並べ替えの仕方にも規定があります.親より小さい値は左、大きい値は右です.
これらの特性のために,BSTはtreeのデフォルトプローブ時間よりも複雑度O(n)が少ないO(logn)を有する.検索を主な機能とする言語辞書などのDBでよく使われる.
BSTには3つの巡回方法が存在する.

前列:親->左->右(A>B>D>E>C>F>G)
中尉:左->父->右(D>B>E>A>F>C>G)
後列:左->右->親(D>E>B>F>G>C>A)

Params
データを格納する値
左の子
右子右

Method
データを挿入するinsert(value)
データが存在するかどうかを確認するためのcontains(value)
中尉巡りorder(callback)
それ以外は、実装の程度に従います.

Psuedo Code

insert(value) {
  // 1. value와 root부터 비교시작
  // 2. root보다 작다면, ( left가 비어있으면 value 할당(탈출), 비어있지 않으면 재귀 )
  // 3. root보다 크다면, ( right가 비어있으면 value 할당(탈출), 비어있지 않으면 재귀 )
}

contains(value) {
  // 1. value가 일치하면 true 리턴 (탈출)
  // 2. left가 null일 때까지 재귀
  // 3. right가 null일 때까지 재귀
}

inorder(callback) {
  // 중위순회 : 왼 > 부모 > 오
  // 1. left가 null일 때까지 재귀
  // 2. callback(this.value)
  // 3. right가 null일 때까지 재귀
}