강동영의 일상

이번 글에서는 연결리스트를 지난 글에 이어서 배울 겁니다. 지난 글에서 노드를 만든 후 서로 연결해보았습니다. 작은 리스트이면 지난 글과 같이 만들어도 되지만 리스트가 커지면 전용 함수들을 통하여 노드를 추가하는 것이 편리합니다. 단순 연결리스트에서 저희가 작성할 함수들은 다음과 같습니다. - insert_first() : 리스트의 시작 부분에 항목을 삽입하는 함수입니다. - insert() : 리스트의 중간 부분에 항목을 삽입하는 함수입니다. - delete_first() : 리스트의 첫 번째 항목을 삭제하는 함수입니다. - delete() : 리스트의 중간 항목을 삭제하는 함수입니다. - print_list() : 리스트를 방문하여 모든 항목을 출력하는 함수입니다. 단순 연결리스트 정의 단순 연결리스..

이번 글에서는 연결리스트에 대해서 배워보도록 하겠습니다. 연결리스트를 설명하기 전에 용어부터 살펴보겠습니다. 리스트란? A, B, C, ... 처럼 순서를 가진 항목들의 모임입니다. 항목이란? 데이터 필드를 말합니다. 즉, 리스트의 원소들을 저장하는 곳입니다. 리스트는 대표적인 선형 자료구조로 노드들이 일렬로 연결된 구조입니다. 연결리스트에서는 리스트의 항목들을 노드라는 곳에 저장합니다. 노드란? 항목(데이터)과 링크의 쌍으로 표현합니다. 링크란? 다음 노드에 대한 주소입니다. 다음 노드가 있는 곳의 주소를 포인터로 표현합니다. 그렇기에 노드들은 데이터와 다른 노드에 대한 포인터를 가집니다. 이렇게 만들어진 연결리스트는 아래의 조건에 따라서 유형이 나뉠 수 있습니다. 링크의 갯수에 따라서 단일 연결리스트..

이번 글에서는 이진탐색트리의 탐색, 삽입, 삭제, 출력을 살펴보겠습니다. 이진트리에서 원하는 값을 찾으려면 루트부터 시작해 현재 선택한 노드의 키 값과 목표하는 값을 비교하면서 왼쪽, 오른쪽으로 검색을 진행하면 됩니다. 알고리즘은 다음과 같습니다. 1. 루트부터 선택하여 검색을 진행합니다. 여기서 선택하는 노드를 p라고 합니다. 2. p가 널이면 검색에 실패합니다. 3. 검색하는 값 key와 선택한 노드 p의 키 값을 비교하여 1) 값이 같으면 검색에 성공(검색 종료)합니다. 2) key가 작으면 선택한 노드에 왼쪽 자식 노드를 대입합니다(왼쪽으로 검색 진행). 3) key가 크면 선택한 노드에 오른쪽 자식 노드를 대입합니다(오른쪽으로 검색 진행). 4. 2번 과정으로 되돌아갑니다. 아래의 코드는 이 알..

이번 글에서는 이진트리와 이진탐색트리를 살펴보겠습니다. 이진트리 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리(binary tree)라고 합니다. 이때 각 노드의 자식은 2명 이하만 유지해야 합니다. 이진트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점입니다. 예를 들어 위의 그림에서 노드 A의 왼쪽 자식은 B, 오른쪽 자식은 C입니다. 이때 왼쪽 자식을 다시 루트로 하는 서브 트리를 왼쪽 서브 트리(left subtree), 오른쪽 자식을 다시 루트로 하는 서브 트리를 오른쪽 서브 트리(right subtree)라고 합니다. 완전이진트리 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리(complete binary tree)라고..