생각하며, 꾸준하게

Representation 1. Adjacency Matrix (인접 행렬) : 2차원 배열로 각 vertex간의 연결유무를 표현한다. undirected graph라면 symmetric 형태이다. : (단점) 공간이 낭비될 수 있고, "몇개의 edge가 있나?" 같은걸 해결하는데 최소 O(n^2)이 걸린다. 2. Adjacency List (인접 리스트) : 각 vertex를 array의 elements로 나타낸 후, 해당 vertex에 연결된 vertex들을 각 elements의 linked list로 연결한다. : undirected graph라면 두 vertex 모두에 각각 하나씩 만들어서 연결해야한다. : 쌩 1차원 배열로 나타낼 수도 있다. n+2e+1만큼 공간 필요. 0~i까지는 vertex..

Representation 자식 node 수에 제한이 없는 일반적인 tree : leftchid-right sbling의 linked node의 형태 (쓸일은 거의 없지싶긴함) Binary Tree : node 생성 후 linking 시켜서 표현하는게 일반적 BST도 여기 들어감. Complete Binary Tree : array로 표현하는게 저장공간측면도 그렇고 계산측면도 그렇고 훨씬 좋음 Heap도 여기 들어감. Binary Tree Operations 1. 순회(traversal) 2. 전체 복사 3. 전체 equality 확인 4. leaf node 연산(satisfiabiltiy problem) Binary Search Tree Operations 1. 검색 2. 삽입 3. 삭제 참고로 BST..