그래프와 트리

=> 그래프는 순회 가능한 자료구조인데, 보통 2차원 배열이나 링크드 리스트로 구현한다.

// 인접 행렬 방식으로 구현
const ghOne = Array.from(Array(5), () => Array(5).fill(false));

ghOne[0][1] = true;
ghOne[0][3] = true;
ghOne[1][2] = true;
ghOne[2][0] = true;
ghOne[2][4] = true;
ghOne[3][2] = true;
ghOne[4][0] = true;

console.log(ghOne);

// 인접 리스트 방식으로 구현
const ghTwo = Array.from(Array(5), () => []);

ghTwo[0].push(1);
ghTwo[0].push(3);
ghTwo[1].push(2);
ghTwo[2].push(0);
ghTwo[2].push(4);
ghTwo[3].push(2);
ghTwo[4].push(0);

console.log(ghTwo);

=> 트리는 계층형 자료구조인데 높이는 전체 노드 개수의 logn이다. 마찬가지로 2차원 배열과 링크드 리스트로 구현 가능하다.

const tree = [null, 9, 3, 8, 2, 5, null, 7, null, null, 4];
2진트리의 활용 1 인덱스부터 루트이며 인덱스 * 2는 왼쪽, 인덱스 * 2 + 1은 오른쪽을 의미한다.