트리
용어 정리
루트 : 최상위 노드
부모 - 자식
깊이 : 조상의 수
높이(층) : 후손의 길이
이진트리
인덱스
현재 노드의 인덱스가 k일 때
부모 : (k - 1) / 2
왼쪽 자식 : 2k + 1
오른쪽 자식 : 2(k + 1)
순회
current 노드에 접근하는 순서에 따라 결정
Preorder : root(current)노드 먼저 방문
Inorder : 왼쪽 자식 먼저 방문 후 current 노드 방문
Postorder : 왼쪽자식->오른쪽자식 방문 후 current노드 방문
트리와 그래프
트리 : 노드와 노드를 잇는 간선의 개수가 1개
그래프 : 노드와 노드를 잇는 간선의 개수가 2개 이상
출발지에서 목적지까지 향하는 방법이 2개 이상이면 그래프
힙정렬
최대 힙 : 루트에 가장 큰 값이 들어있는 트리
최소 힙 : 루트에 가장 작은 값이 들어있는 트리
정렬보다는 작업 프로세싱에 많이 사용(스케줄 관리, 우선순위 큐, 피격 판정(일반-경직-기절) 등)
이진 탐색 트리(Binary Search Tree, BST)
검색속도가 빠름
검색 비용이 균일
이진탐색트리의 삭제
단일 노드 삭제
그냥 링크 해제 후 노드 삭제
자식이 1개인 노드 삭제
삭제되는 노드의 자식과 삭제되는 노드의 부모를 연결
자식이 2개인 노드 삭제
- 삭제 노드를 오른쪽 자식 중 가장 작은 값으로 변경
- 옮겨온 값은 삭제
- 반복
or - 삭제 노드를 왼쪽 자식 중 가장 큰 값으로 변경
- 옮겨온 값은 삭제
- 반복
참고 : https://zeddios.tistory.com/492
자체 조정 트리
트리에 자주 접근하는 노드를 트리의 루트에 가깝게 배치하는 방법
참고 : http://egloos.zum.com/sweeper/v/891278
참고 : https://keichee.tistory.com/442
Balanced Tree
AVL tree
Balancing factor를 이용해 트리의 균형을 잡는 것
2-3-4 tree
2노드, 3노드, 4노드로 만들어진 트리
Red-Black tree
노드에 색을 칠해 균형을 알리는 트리
B tree
2노드 트리의 변형?
검색 알고리즘
해싱(Hashing)
key-function-bucket으로 이루어진 알고리즘
function(key) = bucket을 이용해 index를 구하는 알고리즘
hash함수는 딱히 정해진 것이 없으며, 키를 잘 분산할 수 있도록 개발자가 적절히 구현해야 함
탐색 알고리즘
깊이 우선 탐색
stack 사용
너비 우선 탐색
queue 사용
신장 알고리즘
최소 신장 트리
모든 노드를 방문할 수 있는 간선의 비용이 최소가 되는 알고리즘
Prim, Kruskal
최단거리 신장 트리
출발점에서 목적지까지 가는 간선의 합이 최소가 되는 트리
Dijkstra, Floyd, A*
상태 전환 알고리즘
FSM, Behavior Tree
오늘 수업은 간단히 앞으로 진행할 내용들을 짚고 넘어가는 느낌이었음
만약 차후 수업이 부족하다면 따로 조사가 필요
