Tree
tree 노드 안에는 과연 데이터만 있을까?? Nope
(구현에 따라서 다르겠지만) 객체로 되어있다
let rootNode = new Tree(9)
rootNode 생성 > {value:9, children:[]}
이분탐색(Binary Search Tree)
최대 2개만 놓는다
노드(Root)기분 왼쪽 작은것 오른쪽 큰것을 놓는다.
9찾기
12345678910
---------> 처음부터 끝까지 순차적으로? Nope
절반을 나눠서 탐색 > 5부터 그이하는 9가없음
또 절반을 나눠 탐색 5~10 의 절반 8
8이하는 버림 반복> 결국 9를 찾게됨
그렇게 되면 3번이면 끝남
예2
마지막까지 찾았는데 없다면 false를 리턴
전위/ 중위/ 후위 가 뭐지?
root를 전위에 찍고시작하느냐 중위에서 시작하느냐 후위에서 시작하느냐 의 차이
Graph
인접 매트릭스 인접 리스트가 있다
매트릭스: 2차원배열로 구현
리스트: 객체로구현 조금 어려울수 있다. (실제로 연결된것만 저장
0이 1과 2와 연결되어있구나!)
버텍스 추가하거나 삭제할때는 무조건 list를 써야한다.
자료구조 코플릿 10 인접행렬 생성하기
//정보파밍
1. bone => 매트릭스의 크기가 몇인지? 알고, 그 크기에 맞춰서 간선을 이어줘야함
매트릭스의 최대 크기를 찾아서 모든 요소가 0인 2차원 배열
//0~3까지의 버텍스가 있는 매트릭스를 만들어야한다
// slice와 Math.max를 사용해서 최대치를 구한다.
[[0,0,0,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
이런식으로 뼈대를 생성
그리고 return matrix를 해주면 된다.
자료구조 코플릿 11 인접행렬 길찾기
bfs 는 Queue를 사용 (Queue는 while 문으로)
dfs 는 stack을 사용 (stack은 재귀로)
