Binary tree
Binary tree는 node가 최대 2개의 child를 갖는 tree를 말한다. tree는 parent -> child의 방향이 있는 edge와 node로 구성된다.
Complete Binary Tree
완전 이진 트리는 모든 위에서 아래로, 좌에서 우로 번호를 메길때 빈 번호 없이 순서대로 번호가 메겨지는 트리이다. Heap으로 사용되기도 한다.
Heap
Heap은 부모 노드의 값과 자식 노드들의 값 사이에 항상 일정한 대소 관계가 성립한다.
완전 이진 트리를 Heap으로 사용 하는 것을 배열로 heap을 구성할 때 빈 공간이 없이 만들 수 있어 효율적이기 때문이다.
부모의 값이 자식 보다 크거나 같으면 max heap, 작으면 min heap이라고 한다. max heap은 priority queue라고도 불린다.
heap을 만들때는 heap builder와 heapify를 사용한다.
heap builder를 통해 가장 마지막 부모 노드(위치 n /2)부터 max hep으로 만들어 주는 것을 루트 노드로 올라올때까지 재귀적으로 반복한다.
max heapify는 다음의 과정을 통해 만들어진다.
- 자식노드중 가장 큰 값의 위치를 찾는다.
- 부모 노드가 제일 크다면 max heapify는 끝난다.
- 자식 노드중 더 큰 값을 갖는 것이 있다면 해당 자식 노드의 값과 부모 노드의 값을 교환 한후 해당 자식 노드를 부모 노드로 하여 max heapify를 한다.
Binary Search Tree
Binary Tree이면서 Parent node가 항상 왼쪽 자식의 값보다는 크거나 같고 오른쪽 자식의 값보다는 작거나 같을때를 말한다.
AVL Tree
insert or delete 후에 다시 balanced된 binary search tree를 말한다. balanced는 좌측 subtree의 높이와 우측 subtree의 높이차가 최대 1인 것을 말한다.
Graph
graph는 vertex의 집합 V와 vertex를 연결하는 edge의 집합 E로 정의된다.
V1과 V2사이의 edge인 E12=E21이면 undirected link, 아니면 directed link이다.
- walk : vertex와 edge가 교대로 나타나는 sequence를 의미한다. 즉 Vi 에서 Vj로의 길을 의미한다.
- trail : edge가 중복되지 않는 walk
- path : vertex가 중복되지 않는 walk
- closed walk : 시작 vetex와 종료 vertex가 같은 경우의 walk
- cycle : edge가 최소 하나 이상이고 vertex가 중복되지 않는 closed trail인 경우이다.
- acyclic : cycle이 없는 그래프
- loop : vertex에 edge가 하나 인것.
- connected : 임의의 두 vertex를 양 끝으로 하는 walk가 있는 경우를 의미한다.
- complete : 임의의 두 vertex가 모두 edge로 연결되어 있다.
- clique : ???
- degree of vertex : vertex의 edge 개수
- distance : v1에서 v2로 가는 가장 짧은 edge개수
- eccentricity : Vi에서 다른 모든 Vertex로의 길이중 최대인 distance
Breadth - first search
connected graph에서 모든 vertex를 한번씩 방문하도록 디자인된 알고리즘이다.
시작 vertex부터 길이가 1인 vertex들을 방문하기 시작한다. 그리고 2인, 3인 vertex를 방문하기 시작한다. 더이상 없으면 탐색을 마친다.
특정 vertex부터 다른 vertex까지 가는 최단 길이를 구할 수 있다.
BFS를 통해 graph를 다니다가 원하는 vertex가 나오는 순간 loop를 멈추면 된다.
방문했던 vertex리스트를 queue로 만들면 BFS, 스택으로 만들면 DFS 즉 가장 먼 거리부터 탐색하게 되는 알고리즘이다.
