WHATIS. DATASTRUCTURE
52313 ワード
1. Stack
要素を追加すると、スタックが上部から追加されます.
要素を取り除く(取り出す)ときに、上から取り除く資料構造.(LIOF)
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得するとO(n)の時間的複雑さがある.
1-1. インプリメンテーション
class Stack {
constructor() {
this.storage = {};
this.top = -1;
}
size() {
return Object.keys(this.storage).length
}
push(element) {
this.top++
this.storage[this.top] = element;
return this.storage;
}
pop() {
const last = this.storage[this.top]
delete this.storage[this.top]
this.top--
return last
}
}
2. Queue
要素を追加すると、キューが後に追加されます.
要素を除去(取り出し)すると、前から除去されます.(FIFO)
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得するとO(n)の時間的複雑さがある.
2-1. インプリメンテーション
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
size() {
return Object.keys(this.storage).length;
}
enqueue(element) {
this.storage[this.rear] = element;
this.rear++;
return this.storage;
}
dequeue() {
let result = this.storage[this.front];
delete this.storage[this.front];
if (this.front < this.rear) {
this.front++;
}
return result;
}
}
3. Linked List
リンクリストは複数のノードで構成されています.
ノードはKey(value)とNext(Pointer)からなり、次のノードを指す.
このとき、Nextは前のノードと後のノードを指すことができる.
これをDouble-Linkリストといいます.
筆者は簡単なリンクリストの基準で説明する
リンクリストの最初のものをheadと呼び、headは最初のノードを表します.
(もちろん、最初のノード自体はHeadであってもよい.)
ノードのNextがNullである場合、このノードはTailと呼ばれる.
この構造をLinked-Listと呼ぶ.
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得するとO(n)の時間的複雑さがある.
3-1. インプリメンテーション
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this._size = 0;
}
addToTail(value) {
let node = new Node(value)
this._size ++;
// 1. 처음으로 추가할 때, head에 node 할당
if (this.head === null) {
this.head = node;
}
// 3. 앞에 node가 이미 있는 경우.
if (this.tail !== null) {
this.tail.next = node;
this.tail = node;
}
// 2. 새로운 노드가 추가될 때마다 tail에 node 할당
else {
this.tail = node;
}
}
remove(value) {
if (this._size > 0) {
if (this.head.value === value) { // 헤드의 벨류가 같을 때
this.head = this.head.next; // 헤드를 다음 노드로 변경하기
this._size--;
}
else {
let prevHead = this.head;
let newHead = this.head.next;
let size = this._size;
while (size) {
if (newHead.value === value) { // value 일 경우
if (newHead.next === null) {
prevHead.next = null;
prevHead = false;
this.tail = prevHead;
this._size--;
}
else {
prevHead.next = newHead.next;
newHead.next = null;
//newHead = false;
this._size--;
}
break;
}
else if (newHead.value !== value) { // value 아닐 경우
prevHead = this.head.next.next;
size--;
}
}
}
}
}
getNodeAt(index) {
let checkHead = this.head
while(index > -1) {
if (index === 0 && this.head !== null) {
return checkHead;
}
if (index > 0) {
index--
if (checkHead.next === null) {
return undefined;
}
checkHead = checkHead.next;
}
}
return undefined;
}
contains(value) {
let size = this._size
let checkHead = this.head
while (size) {
if (checkHead.value === value) {
return true;
}
else {
checkHead = checkHead.next;
}
size--
}
return false;
}
indexOf(value) {
let size = this._size
let result = 0
let checkHead = this.head
while (size) {
if (checkHead.value === value) {
return result;
}
else {
checkHead = checkHead.next;
result++
}
size--
}
return -1;
}
size() {
return this._size;
}
}
4. Hash Table
ハッシュテーブルは、データを格納する際にハッシュ機能、格納を使用します.
Hash Functionは入力したデータをHash値に置き換えます.
Hash値をStorageのIndex値にマッピングします.
次に、対応するインデックスにデータを入れます.
このとき、入力したデータをHash値に変換し、複数のindex値にマッピングします.
2つ以上の値が1つのインデックスに入る競合が発生しました.
(もちろん、目的によってカバーすることもあります.)
この問題を解決する方法は二つに分かれている.
1. Open Addressing
:2つの競合値のうちの1つを別の空のインデックスに挿入する方法.
2. Separate Chaining
:2つの値を1つのインデックスにリンクする方法.
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得する場合,O(1)の時間的複雑さを持つ.
4-1. インプリメンテーション
const LimitedArray = require('./helpers/limitedArray');
const hashFunction = require('./helpers/hashFunction');
// 위 문법은 helpers 폴더에 있는 limitedArray와 hashFunction을 불러오는 문법입니다.
// 위와 같이 require를 사용해서 다른 파일로부터 함수 등을 불러오는 작업은 이후에 따로 설명합니다.
class HashTable {
constructor() {
this._size = 0;
this._bucketNum = 8;
this._storage = LimitedArray(this._bucketNum);
}
insert(key, value) {
const index = hashFunction(key, this._bucketNum); // 0, 1, 2, 3, ...
let obj = {}
if (this._storage.get(index) === undefined) {
obj[key] = value;
this._storage.set(index, obj)
} else {
obj = this._storage.get(index)
obj[key] = value;
this._storage.set(index, obj)
}
this._size++;
//this._resize(this._bucketNum);
// 추가
if (this._bucketNum * 0.75 <= this._size) {
this._resize(this._bucketNum * 2)
}
}
retrieve(key) {
const index = hashFunction(key, this._bucketNum);
if (this._storage.get(index) === undefined) {
return undefined;
}
return this._storage.get(index)[key];
}
remove(key) {
const index = hashFunction(key, this._bucketNum);
delete this._storage.get(index)[key];
this._size--;
// 추가
if (this._bucketNum * 0.25 > this._size) {
this._resize(this._bucketNum * 0.5);
}
}
_resize(newBucketNum) {
let past = this._storage;
this._size = 0;
this._bucketNum = newBucketNum;
this._storage = LimitedArray(this._bucketNum); // new storage
// 해싱
past.each(function(past){
for (let i in past) {
this.insert(i, past[i])
}
}.bind(this))
}
}
5. Graph
グラフは複数のノードで構成されています.
また,これらのノード間の関係にはedge(幹線)がある.
edgeは一方向でも双方向でもよい.
(幹線に方向がある場合は、直接図形またはUndirect図形)
グラフの代表的な実装方法は2つに分けられます.
1.隣接行列
:2 D配列で表現する方法.(無幹線は0、有幹線は1)
O(1)だけで2つの頂点の間に幹線が存在するかどうかを知ることができるという利点がある.
定点の差はO(n)で、すべての幹線の数はO(n^2)が必要です.
2.隣接表
:各頂点に隣接する頂点をリスト化する方法.(作成者が使用)
2つの頂点を結ぶ幹線の有無や回数を知るためにはO(n)が必要である.
すべての幹線の数にはO(n+e)が必要です.(e=幹線数)
実施方法は、通常、目的に応じて選択される.
5-1. インプリメンテーション
class Graph {
constructor() {
/*
* ex)
* nodes = {
* 0: [ 1, 2 ],
* 1: [ 0 ],
* 2: [ 0 ]
* }
*/
this.nodes = {};
}
addNode(node) {
this.nodes[node] = this.nodes[node] || [];
}
contains(node) { // 해당노드가 들어있는지 유무 리턴
return node in this.nodes;
}
removeNode(node) {
delete this.nodes[node];
for (let key in this.nodes) {
if (this.nodes[key].includes(node)) {
this.nodes[key].splice(this.nodes[key].indexOf(node), 1);
}
}
}
hasEdge(fromNode, toNode) {
if (this.nodes[fromNode] !== undefined && this.nodes[toNode] !== undefined) {
return this.nodes[fromNode].includes(toNode) && this.nodes[toNode].includes(fromNode);
}
return false;
}
addEdge(fromNode, toNode) {
this.nodes[fromNode].push(toNode);
this.nodes[toNode].push(fromNode);
}
removeEdge(fromNode, toNode) {
this.nodes[fromNode].splice(this.nodes[fromNode].indexOf(toNode), 1)
this.nodes[toNode].splice(this.nodes[toNode].indexOf(fromNode), 1)
}
}
5. Tree
ツリーはグラフの一部であり、階層化された資料構造です.
同様に、複数のノードで構成され、上部にルートノードが作成されます.
childをルートに接続して実装します.
Leafと呼ばれるサブノードはありません.
最下部にサブノードがないノードをSibligsと呼ぶ.
ツリーのタイプ
1. Binary tree
2. Binary Search Tree
3. Balance
4. Complete binary tree
5. Full binary tree
6. Perfect binary tree
7. Binary tree traversal
木の遍歴方法
1.Inorder(中位数):Left、Root、Right(LRootr)
2.Preorder(前輪):Root、Left、Right(RootLR)
3.Postorder(後列):Left、Right、Root(LR Root)
ツリーの種類と巡回方法の詳細については、ここです。を参照してください.
5-1. インプリメンテーション
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}
insertNode(value) {
let node = new TreeNode(value);
this.children.push(node);
}
contains(value) {
let result = false;
if (this.value === value) {
return true;
}
for (let i = 0; i < this.children.length; i++){
result = this.children[i].contains(value)
if (result !== false) {
return result;
}
}
return false;
}
}
Reference
この問題について(WHATIS. DATASTRUCTURE), 我々は、より多くの情報をここで見つけました
https://velog.io/@315dragon/WHATIS.-DATASTRUCTURE
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
class Stack {
constructor() {
this.storage = {};
this.top = -1;
}
size() {
return Object.keys(this.storage).length
}
push(element) {
this.top++
this.storage[this.top] = element;
return this.storage;
}
pop() {
const last = this.storage[this.top]
delete this.storage[this.top]
this.top--
return last
}
}
要素を追加すると、キューが後に追加されます.
要素を除去(取り出し)すると、前から除去されます.(FIFO)
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得するとO(n)の時間的複雑さがある.
2-1. インプリメンテーション
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
size() {
return Object.keys(this.storage).length;
}
enqueue(element) {
this.storage[this.rear] = element;
this.rear++;
return this.storage;
}
dequeue() {
let result = this.storage[this.front];
delete this.storage[this.front];
if (this.front < this.rear) {
this.front++;
}
return result;
}
}
3. Linked List
リンクリストは複数のノードで構成されています.
ノードはKey(value)とNext(Pointer)からなり、次のノードを指す.
このとき、Nextは前のノードと後のノードを指すことができる.
これをDouble-Linkリストといいます.
筆者は簡単なリンクリストの基準で説明する
リンクリストの最初のものをheadと呼び、headは最初のノードを表します.
(もちろん、最初のノード自体はHeadであってもよい.)
ノードのNextがNullである場合、このノードはTailと呼ばれる.
この構造をLinked-Listと呼ぶ.
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得するとO(n)の時間的複雑さがある.
3-1. インプリメンテーション
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this._size = 0;
}
addToTail(value) {
let node = new Node(value)
this._size ++;
// 1. 처음으로 추가할 때, head에 node 할당
if (this.head === null) {
this.head = node;
}
// 3. 앞에 node가 이미 있는 경우.
if (this.tail !== null) {
this.tail.next = node;
this.tail = node;
}
// 2. 새로운 노드가 추가될 때마다 tail에 node 할당
else {
this.tail = node;
}
}
remove(value) {
if (this._size > 0) {
if (this.head.value === value) { // 헤드의 벨류가 같을 때
this.head = this.head.next; // 헤드를 다음 노드로 변경하기
this._size--;
}
else {
let prevHead = this.head;
let newHead = this.head.next;
let size = this._size;
while (size) {
if (newHead.value === value) { // value 일 경우
if (newHead.next === null) {
prevHead.next = null;
prevHead = false;
this.tail = prevHead;
this._size--;
}
else {
prevHead.next = newHead.next;
newHead.next = null;
//newHead = false;
this._size--;
}
break;
}
else if (newHead.value !== value) { // value 아닐 경우
prevHead = this.head.next.next;
size--;
}
}
}
}
}
getNodeAt(index) {
let checkHead = this.head
while(index > -1) {
if (index === 0 && this.head !== null) {
return checkHead;
}
if (index > 0) {
index--
if (checkHead.next === null) {
return undefined;
}
checkHead = checkHead.next;
}
}
return undefined;
}
contains(value) {
let size = this._size
let checkHead = this.head
while (size) {
if (checkHead.value === value) {
return true;
}
else {
checkHead = checkHead.next;
}
size--
}
return false;
}
indexOf(value) {
let size = this._size
let result = 0
let checkHead = this.head
while (size) {
if (checkHead.value === value) {
return result;
}
else {
checkHead = checkHead.next;
result++
}
size--
}
return -1;
}
size() {
return this._size;
}
}
4. Hash Table
ハッシュテーブルは、データを格納する際にハッシュ機能、格納を使用します.
Hash Functionは入力したデータをHash値に置き換えます.
Hash値をStorageのIndex値にマッピングします.
次に、対応するインデックスにデータを入れます.
このとき、入力したデータをHash値に変換し、複数のindex値にマッピングします.
2つ以上の値が1つのインデックスに入る競合が発生しました.
(もちろん、目的によってカバーすることもあります.)
この問題を解決する方法は二つに分かれている.
1. Open Addressing
:2つの競合値のうちの1つを別の空のインデックスに挿入する方法.
2. Separate Chaining
:2つの値を1つのインデックスにリンクする方法.
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得する場合,O(1)の時間的複雑さを持つ.
4-1. インプリメンテーション
const LimitedArray = require('./helpers/limitedArray');
const hashFunction = require('./helpers/hashFunction');
// 위 문법은 helpers 폴더에 있는 limitedArray와 hashFunction을 불러오는 문법입니다.
// 위와 같이 require를 사용해서 다른 파일로부터 함수 등을 불러오는 작업은 이후에 따로 설명합니다.
class HashTable {
constructor() {
this._size = 0;
this._bucketNum = 8;
this._storage = LimitedArray(this._bucketNum);
}
insert(key, value) {
const index = hashFunction(key, this._bucketNum); // 0, 1, 2, 3, ...
let obj = {}
if (this._storage.get(index) === undefined) {
obj[key] = value;
this._storage.set(index, obj)
} else {
obj = this._storage.get(index)
obj[key] = value;
this._storage.set(index, obj)
}
this._size++;
//this._resize(this._bucketNum);
// 추가
if (this._bucketNum * 0.75 <= this._size) {
this._resize(this._bucketNum * 2)
}
}
retrieve(key) {
const index = hashFunction(key, this._bucketNum);
if (this._storage.get(index) === undefined) {
return undefined;
}
return this._storage.get(index)[key];
}
remove(key) {
const index = hashFunction(key, this._bucketNum);
delete this._storage.get(index)[key];
this._size--;
// 추가
if (this._bucketNum * 0.25 > this._size) {
this._resize(this._bucketNum * 0.5);
}
}
_resize(newBucketNum) {
let past = this._storage;
this._size = 0;
this._bucketNum = newBucketNum;
this._storage = LimitedArray(this._bucketNum); // new storage
// 해싱
past.each(function(past){
for (let i in past) {
this.insert(i, past[i])
}
}.bind(this))
}
}
5. Graph
グラフは複数のノードで構成されています.
また,これらのノード間の関係にはedge(幹線)がある.
edgeは一方向でも双方向でもよい.
(幹線に方向がある場合は、直接図形またはUndirect図形)
グラフの代表的な実装方法は2つに分けられます.
1.隣接行列
:2 D配列で表現する方法.(無幹線は0、有幹線は1)
O(1)だけで2つの頂点の間に幹線が存在するかどうかを知ることができるという利点がある.
定点の差はO(n)で、すべての幹線の数はO(n^2)が必要です.
2.隣接表
:各頂点に隣接する頂点をリスト化する方法.(作成者が使用)
2つの頂点を結ぶ幹線の有無や回数を知るためにはO(n)が必要である.
すべての幹線の数にはO(n+e)が必要です.(e=幹線数)
実施方法は、通常、目的に応じて選択される.
5-1. インプリメンテーション
class Graph {
constructor() {
/*
* ex)
* nodes = {
* 0: [ 1, 2 ],
* 1: [ 0 ],
* 2: [ 0 ]
* }
*/
this.nodes = {};
}
addNode(node) {
this.nodes[node] = this.nodes[node] || [];
}
contains(node) { // 해당노드가 들어있는지 유무 리턴
return node in this.nodes;
}
removeNode(node) {
delete this.nodes[node];
for (let key in this.nodes) {
if (this.nodes[key].includes(node)) {
this.nodes[key].splice(this.nodes[key].indexOf(node), 1);
}
}
}
hasEdge(fromNode, toNode) {
if (this.nodes[fromNode] !== undefined && this.nodes[toNode] !== undefined) {
return this.nodes[fromNode].includes(toNode) && this.nodes[toNode].includes(fromNode);
}
return false;
}
addEdge(fromNode, toNode) {
this.nodes[fromNode].push(toNode);
this.nodes[toNode].push(fromNode);
}
removeEdge(fromNode, toNode) {
this.nodes[fromNode].splice(this.nodes[fromNode].indexOf(toNode), 1)
this.nodes[toNode].splice(this.nodes[toNode].indexOf(fromNode), 1)
}
}
5. Tree
ツリーはグラフの一部であり、階層化された資料構造です.
同様に、複数のノードで構成され、上部にルートノードが作成されます.
childをルートに接続して実装します.
Leafと呼ばれるサブノードはありません.
最下部にサブノードがないノードをSibligsと呼ぶ.
ツリーのタイプ
1. Binary tree
2. Binary Search Tree
3. Balance
4. Complete binary tree
5. Full binary tree
6. Perfect binary tree
7. Binary tree traversal
木の遍歴方法
1.Inorder(中位数):Left、Root、Right(LRootr)
2.Preorder(前輪):Root、Left、Right(RootLR)
3.Postorder(後列):Left、Right、Root(LR Root)
ツリーの種類と巡回方法の詳細については、ここです。を参照してください.
5-1. インプリメンテーション
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}
insertNode(value) {
let node = new TreeNode(value);
this.children.push(node);
}
contains(value) {
let result = false;
if (this.value === value) {
return true;
}
for (let i = 0; i < this.children.length; i++){
result = this.children[i].contains(value)
if (result !== false) {
return result;
}
}
return false;
}
}
Reference
この問題について(WHATIS. DATASTRUCTURE), 我々は、より多くの情報をここで見つけました
https://velog.io/@315dragon/WHATIS.-DATASTRUCTURE
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this._size = 0;
}
addToTail(value) {
let node = new Node(value)
this._size ++;
// 1. 처음으로 추가할 때, head에 node 할당
if (this.head === null) {
this.head = node;
}
// 3. 앞에 node가 이미 있는 경우.
if (this.tail !== null) {
this.tail.next = node;
this.tail = node;
}
// 2. 새로운 노드가 추가될 때마다 tail에 node 할당
else {
this.tail = node;
}
}
remove(value) {
if (this._size > 0) {
if (this.head.value === value) { // 헤드의 벨류가 같을 때
this.head = this.head.next; // 헤드를 다음 노드로 변경하기
this._size--;
}
else {
let prevHead = this.head;
let newHead = this.head.next;
let size = this._size;
while (size) {
if (newHead.value === value) { // value 일 경우
if (newHead.next === null) {
prevHead.next = null;
prevHead = false;
this.tail = prevHead;
this._size--;
}
else {
prevHead.next = newHead.next;
newHead.next = null;
//newHead = false;
this._size--;
}
break;
}
else if (newHead.value !== value) { // value 아닐 경우
prevHead = this.head.next.next;
size--;
}
}
}
}
}
getNodeAt(index) {
let checkHead = this.head
while(index > -1) {
if (index === 0 && this.head !== null) {
return checkHead;
}
if (index > 0) {
index--
if (checkHead.next === null) {
return undefined;
}
checkHead = checkHead.next;
}
}
return undefined;
}
contains(value) {
let size = this._size
let checkHead = this.head
while (size) {
if (checkHead.value === value) {
return true;
}
else {
checkHead = checkHead.next;
}
size--
}
return false;
}
indexOf(value) {
let size = this._size
let result = 0
let checkHead = this.head
while (size) {
if (checkHead.value === value) {
return result;
}
else {
checkHead = checkHead.next;
result++
}
size--
}
return -1;
}
size() {
return this._size;
}
}
ハッシュテーブルは、データを格納する際にハッシュ機能、格納を使用します.
Hash Functionは入力したデータをHash値に置き換えます.
Hash値をStorageのIndex値にマッピングします.
次に、対応するインデックスにデータを入れます.
このとき、入力したデータをHash値に変換し、複数のindex値にマッピングします.
2つ以上の値が1つのインデックスに入る競合が発生しました.
(もちろん、目的によってカバーすることもあります.)
この問題を解決する方法は二つに分かれている.
1. Open Addressing
:2つの競合値のうちの1つを別の空のインデックスに挿入する方法.
2. Separate Chaining
:2つの値を1つのインデックスにリンクする方法.
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得する場合,O(1)の時間的複雑さを持つ.
4-1. インプリメンテーション
const LimitedArray = require('./helpers/limitedArray');
const hashFunction = require('./helpers/hashFunction');
// 위 문법은 helpers 폴더에 있는 limitedArray와 hashFunction을 불러오는 문법입니다.
// 위와 같이 require를 사용해서 다른 파일로부터 함수 등을 불러오는 작업은 이후에 따로 설명합니다.
class HashTable {
constructor() {
this._size = 0;
this._bucketNum = 8;
this._storage = LimitedArray(this._bucketNum);
}
insert(key, value) {
const index = hashFunction(key, this._bucketNum); // 0, 1, 2, 3, ...
let obj = {}
if (this._storage.get(index) === undefined) {
obj[key] = value;
this._storage.set(index, obj)
} else {
obj = this._storage.get(index)
obj[key] = value;
this._storage.set(index, obj)
}
this._size++;
//this._resize(this._bucketNum);
// 추가
if (this._bucketNum * 0.75 <= this._size) {
this._resize(this._bucketNum * 2)
}
}
retrieve(key) {
const index = hashFunction(key, this._bucketNum);
if (this._storage.get(index) === undefined) {
return undefined;
}
return this._storage.get(index)[key];
}
remove(key) {
const index = hashFunction(key, this._bucketNum);
delete this._storage.get(index)[key];
this._size--;
// 추가
if (this._bucketNum * 0.25 > this._size) {
this._resize(this._bucketNum * 0.5);
}
}
_resize(newBucketNum) {
let past = this._storage;
this._size = 0;
this._bucketNum = newBucketNum;
this._storage = LimitedArray(this._bucketNum); // new storage
// 해싱
past.each(function(past){
for (let i in past) {
this.insert(i, past[i])
}
}.bind(this))
}
}
5. Graph
グラフは複数のノードで構成されています.
また,これらのノード間の関係にはedge(幹線)がある.
edgeは一方向でも双方向でもよい.
(幹線に方向がある場合は、直接図形またはUndirect図形)
グラフの代表的な実装方法は2つに分けられます.
1.隣接行列
:2 D配列で表現する方法.(無幹線は0、有幹線は1)
O(1)だけで2つの頂点の間に幹線が存在するかどうかを知ることができるという利点がある.
定点の差はO(n)で、すべての幹線の数はO(n^2)が必要です.
2.隣接表
:各頂点に隣接する頂点をリスト化する方法.(作成者が使用)
2つの頂点を結ぶ幹線の有無や回数を知るためにはO(n)が必要である.
すべての幹線の数にはO(n+e)が必要です.(e=幹線数)
実施方法は、通常、目的に応じて選択される.
5-1. インプリメンテーション
class Graph {
constructor() {
/*
* ex)
* nodes = {
* 0: [ 1, 2 ],
* 1: [ 0 ],
* 2: [ 0 ]
* }
*/
this.nodes = {};
}
addNode(node) {
this.nodes[node] = this.nodes[node] || [];
}
contains(node) { // 해당노드가 들어있는지 유무 리턴
return node in this.nodes;
}
removeNode(node) {
delete this.nodes[node];
for (let key in this.nodes) {
if (this.nodes[key].includes(node)) {
this.nodes[key].splice(this.nodes[key].indexOf(node), 1);
}
}
}
hasEdge(fromNode, toNode) {
if (this.nodes[fromNode] !== undefined && this.nodes[toNode] !== undefined) {
return this.nodes[fromNode].includes(toNode) && this.nodes[toNode].includes(fromNode);
}
return false;
}
addEdge(fromNode, toNode) {
this.nodes[fromNode].push(toNode);
this.nodes[toNode].push(fromNode);
}
removeEdge(fromNode, toNode) {
this.nodes[fromNode].splice(this.nodes[fromNode].indexOf(toNode), 1)
this.nodes[toNode].splice(this.nodes[toNode].indexOf(fromNode), 1)
}
}
5. Tree
ツリーはグラフの一部であり、階層化された資料構造です.
同様に、複数のノードで構成され、上部にルートノードが作成されます.
childをルートに接続して実装します.
Leafと呼ばれるサブノードはありません.
最下部にサブノードがないノードをSibligsと呼ぶ.
ツリーのタイプ
1. Binary tree
2. Binary Search Tree
3. Balance
4. Complete binary tree
5. Full binary tree
6. Perfect binary tree
7. Binary tree traversal
木の遍歴方法
1.Inorder(中位数):Left、Root、Right(LRootr)
2.Preorder(前輪):Root、Left、Right(RootLR)
3.Postorder(後列):Left、Right、Root(LR Root)
ツリーの種類と巡回方法の詳細については、ここです。を参照してください.
5-1. インプリメンテーション
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}
insertNode(value) {
let node = new TreeNode(value);
this.children.push(node);
}
contains(value) {
let result = false;
if (this.value === value) {
return true;
}
for (let i = 0; i < this.children.length; i++){
result = this.children[i].contains(value)
if (result !== false) {
return result;
}
}
return false;
}
}
Reference
この問題について(WHATIS. DATASTRUCTURE), 我々は、より多くの情報をここで見つけました
https://velog.io/@315dragon/WHATIS.-DATASTRUCTURE
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
class Graph {
constructor() {
/*
* ex)
* nodes = {
* 0: [ 1, 2 ],
* 1: [ 0 ],
* 2: [ 0 ]
* }
*/
this.nodes = {};
}
addNode(node) {
this.nodes[node] = this.nodes[node] || [];
}
contains(node) { // 해당노드가 들어있는지 유무 리턴
return node in this.nodes;
}
removeNode(node) {
delete this.nodes[node];
for (let key in this.nodes) {
if (this.nodes[key].includes(node)) {
this.nodes[key].splice(this.nodes[key].indexOf(node), 1);
}
}
}
hasEdge(fromNode, toNode) {
if (this.nodes[fromNode] !== undefined && this.nodes[toNode] !== undefined) {
return this.nodes[fromNode].includes(toNode) && this.nodes[toNode].includes(fromNode);
}
return false;
}
addEdge(fromNode, toNode) {
this.nodes[fromNode].push(toNode);
this.nodes[toNode].push(fromNode);
}
removeEdge(fromNode, toNode) {
this.nodes[fromNode].splice(this.nodes[fromNode].indexOf(toNode), 1)
this.nodes[toNode].splice(this.nodes[toNode].indexOf(fromNode), 1)
}
}
ツリーはグラフの一部であり、階層化された資料構造です.
同様に、複数のノードで構成され、上部にルートノードが作成されます.
childをルートに接続して実装します.
Leafと呼ばれるサブノードはありません.
最下部にサブノードがないノードをSibligsと呼ぶ.
ツリーのタイプ
1. Binary tree
2. Binary Search Tree
3. Balance
4. Complete binary tree
5. Full binary tree
6. Perfect binary tree
7. Binary tree traversal
木の遍歴方法
1.Inorder(中位数):Left、Root、Right(LRootr)
2.Preorder(前輪):Root、Left、Right(RootLR)
3.Postorder(後列):Left、Right、Root(LR Root)
ツリーの種類と巡回方法の詳細については、ここです。を参照してください.
5-1. インプリメンテーション
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}
insertNode(value) {
let node = new TreeNode(value);
this.children.push(node);
}
contains(value) {
let result = false;
if (this.value === value) {
return true;
}
for (let i = 0; i < this.children.length; i++){
result = this.children[i].contains(value)
if (result !== false) {
return result;
}
}
return false;
}
}
Reference
この問題について(WHATIS. DATASTRUCTURE), 我々は、より多くの情報をここで見つけました https://velog.io/@315dragon/WHATIS.-DATASTRUCTUREテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol