몽땅뚝딱 개발자

15장, 16장 다시 읽어보기 .. 🥺 트리(Tree) 순서를 유지하면서도 빠른 검색과 삽입, 삭제가 가능한 자료 구조가 필요한 경우에 사용한다. 트리도 노드 기반 자료 구조이지만 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다. 트리의 각 노드에는 다른 두 노드로 이어지는 링크가 있다. 1.1. 개념 루트(root): 가장 상위 노드로 꼭대기에 있다. 부모(parent), 자손(descendant), 조상(ancestor) 레벨(level): 각 줄을 의미한다. 프로퍼티(property): 균형 잡힌 정도이다. 모든 노드에서 하위 트리의 노드 개수가 같으면 그 트리는 균형(balanced) 트리다. 1.2 이진 탐색 트리 이진과 탐색이라는 수식어가 붙는데 이진 트리는 각 노드에 자식이 0개나 1..

연결 리스트(linked list) 1.1. 연결 리스트가 유용한 순간 연결 리스트는 배열과 상당히 유사하지만 자료 구조의 성능에 큰 차이가 있다. 가령 세 번째 node에 있는 값을 읽거나 검색하기 위해서는 첫 번째부터 접근하여 순차적으로 진행해야 하므로 O(N)이다. 따라서 읽기와 검색에서는 유의미한 차이가 없지만 연결 리스트는 삽입에서 빛을 발휘한다. 배열에서 최악의 시나리오는 인덱스 0에 데이터를 삽입하거나 삭제할 때이다. 나머지 데이터를 한 셀씩 오른쪽으로 옮겨야 하기 때문에 효율성은 O(N)이 된다. 반면 연결 리스트는 딱 한 단계인 O(1)만 걸린다. 삽입하는 경우 배열처럼 한 셀씩 옮기는 것이 아니라 기존 리스트 앞에 새 노드를 생성하고 노드가 이전의 첫 번째 노드를 가리키도록 만들면 된다..