개발하는 리프터 꽃게맨입니다.

1. 이진 탐색 트리의 문제점 이진 탐색 트리는 매우 효율적인 자료구조입니다. '균형 트리'라는 전제하에 삽입, 삭제, 탐색이 모두 O(log2 N)만을 소모합니다. 그런데, 이진 탐색 트리는 '균형' 을 보장하지 않습니다. 만약 삽입을 하다 이런 트리 구조가 나왔다면, 시간 복잡도가 O(N) 에 가까워지는 것이죠. 따라서 이진 탐색 트리에서는 균형을 유지하는 것이 매우 중요하여, 여러가지 스스로 균형을 잡은 자가 균형 트리에 대해서 알아보도록 하겠습니다. 2. AVL 트리 1) 개요 AVL 트리는 이진 탐색 트리에서 한 가지 조건을 더 추가합니다. 왼쪽 서브트리와 오른쪽 서브 트리의 높이 차이가 1 이하 AVL 트리는 항상 균형 트리를 보장되기 때문에 탐색이 O(log2 n) 만에 완료됩니다. 2) B..

[ 목차 ] 1. 개요 1) 개요 리스트, 큐, 스택, 배열과 같은 자료구조를 선형 자료 구조라고 부릅니다. 데이터들을 연속적으로 접근할 수 있는 것이죠. 근데, 예를 들어 가족의 가계도, 회사의 조직도, 컴퓨터의 디렉터리 등에 대한 자료구조를 어떻게 표현하면 좋을까요? 이 경우에 사용하는 것이 트리(tree) 계층적 자료 구조입니다. 트리 구조는 마치 나무를 거꾸로 뒤집을 형태라고 그렇게 부릅니다. 가장 최상단 노드를 루트노드라고 부르며, 루트의 아래로 작은 트리들이 재귀적으로 정의되는 것을 기본 구조로 합니다. 2) 용어 트리는 한 개 이상의 노드로 이루어진 유한 집합입니다. 트리에서 최상위 노드를 루트 노드 한 노드에서 뻗어 나오는 노드들을 자식 노드 그 반대를 부모 노드라고 합니다. 2의 경우 7..

[ 목차 ] 개요 1. 리스트란? 리스트는 자료를 정리하는 방법 중 하나입니다. 항목이 '연속적으로' 저장되어 있는 자료구조의 가장 기본적인 한 형태라고 할 수 있죠. 대부분의 언어에서 기본적으로 제공하는 '배열' 역시 '리스트'의 한 종류 입니다 그리고 '리스트'를 구현하는 방법이 하나 더 있는데, 그것이 연결 리스트입니다. 2. 연결리스트 연결리스트는 노드라는 데이터 단위가 존재하고, 노드 내부에는 데이터가 연결되는 데이터 영역, 그리고 다른 노드를 가리키는 링크 영역이 존재합니다. 저장하고 싶은 데이터를 데이터 영역에 저장하고, 링크 영역에서 링크라는 연결이 다른 노드를 가리킵니다. 이런 방식으로 메모리가 링크라는 줄로 연결된 상태입니다. 이런 링크라는 표현은 다른 여러 가지의 자료구조를 구현하는데..