꿈 꾸는 누렁이

자 오늘은 테이블과 해시이다.

자료구조는 자료를 저장하는 구조를 나타내는 것이지만, 그 구조 속에 들어 있는 값을 찾아서 꺼내는 것 또한 자료 구조의 영역 범위 내이다.

그래서 배열 리스트, 연결 리스트, 스택, 큐, 그래프, 트리 등에서 탐색에 해당하는 부분을 구현해왔다. 그 중 테이블이라는 자료구조에 대해 볼 것인데, 이 구조는 특별하다. 탐색 속도가 어마어마하게 빠르다. 기록해보자.

테이블이란 무엇인가?

이것이 테이블 자료구조이다. 키와 값으로 구성되어 있는 구조를 테이블 자료구조이다. 보통 언어에 따라 다르지만 키와 값으로 구성되어있는 자료구조를 사전(Dictionary), 맵(Map) 구조라고도 한다.

테이블 자료 구조에서의 핵 중요한 규칙

1. 테이블 자료구조에서는 키와 값이 한 쌍의 형태로 이루어 저장이 된다.
이 때 값은 뭐 하나가 되어도 좋고 여럿이 되어도 좋다.

2. 테이블 자료구조에서는 키 값은 중복되어서는 아니 된다.
아래의 그림을 보자

학생을 관리하는 테이블이다. 소위 말하는 학번이라는 것은 각 학생들에게 부여되는 고유 번호이다. 그러니까 학번 1번을 외치는 것만으로도 수 많은 학생들 중에서 '나루토'를 특정 지을 수 있어야한다. 이것이 실생활에서 적용되는 예이다. 

그런데 위의 테이블에서 학번 3번을 부르면 네! 하고 손을 드는 학생이 에렌과 아르민으로 두 명인 상황이 만들어졌다. 이런 경우에는 학번을 부르고 나서 이름까지 불러야 그제서야 에렌과 아르민을 특정 지을 수 있는 것이다.

만약 이런 상황에서 3번으로 중복되는 에렌과 아르민이 포함되어 있는 전교생 수천명이 시험을 본다고 생각하자. 그러면 자동적으로 OMR 채점을 진행할텐데 이 때 기계는 각 학생들을 구분할 때, 학번을 이용하여 학생을 특정 짓지만 에렌과 아르민 자식들이 포함되어 있는 경우가 존재하기 때문에 모든 학생들을 대상으로 학번과 이름을 한 번에 확인해야한다.

테이블 자료구조에는 보통 키 값을 이용하여 데이터를 특정짓기 때문에 위와 같은 경우를 만들지 않기 위해서 키의 중복을 허용하지 않도록 하겠다. (뭐 허용을 시키는 경우도 있긴 하지만 말이다.)

3. 키가 없으면 값을 저장할 수 없다.

키를 활용해 값을 특정 지어야 하기 때문에 키를 비울 수는 없다.

4. 값을 특정 짓는다는 것의 의미.

위 그림을 봤을 때, 3번이라는 학번을 통해 에렌을 특정 지었는데 달리 말하면 탐색이 완료되었다는 소리이다. 

이 개념들을 숙지한 채로 아래의 예시를 보면 된다.

기본적인 테이블 예시

테이블이 될 구조체 정의

구조체 정의를 이용하여 배열로 선언하면 테이블 형태의 구조를 만들 수 있다.

테이블에 데이터를 등록하는 함수

인덱싱이 특이하다는 것을 확인할 수 있다.

메인 함수 실행 부분

임의로 입력된 값을 키 값으로 활용한다.

49번 줄에서는 키 값을 이용해 원하는 값을 바로 뽑아낸다. 이런 것이 가능한 이유가 무엇인가? 

데이터를 삽입할 때, 키의 값 '번째'에 해당하는 배열 칸에 넣었으니,

값을 뽑아올 때에도 키를 인덱스로 던져주면 키의 값 '번째'에 해당하는 배열 칸에서 뽑아온다.

말이 탐색이지, 사실 탐색이라고 할 것도 없이 그냥 인덱싱일 뿐이다. 그냥 *(배열이름+인덱스(키값)) 이렇게 연산해주면 접근 가능하기 때문에 포스팅 초반에 겁나 빠르다고 한 것이다.

전체 코드 및 실행 결과

문제점

근데 위와 같은 테이블은 빠른건 빠른거지만 중요한 문제가 있다.

1. 학번이 원래 0부터 100까지의 자리였지만 갑자기 년도+번호와 같은 식으로 변해버리면 분명히 문제가 된다.
원래 99번이었던 번호가 20210099로 바뀐다면 이 또한 문제가 될 것이다. 

기존의 방법대로라면 user acc[20210100]; 이렇게 선언을 해야, 20210099 같은 인덱스가 먹혀도 먹힐 것이다. 그런데 이러한 크기의 배열 선언이 과연 정상일까?

모든 키가 0부터 시작해서 뭐 적절히 1,000 값으로 끝나면 좋겠지만 실제로는 그렇지가 않다. 학번은 보통 해당 년도와 고유 번호를 합쳐서 만든다. 군번은 말할 것도 없다 이런 번호 키들을 수용하기 위해서 user acc[20210100]; 이렇게 비정상적인 배열 선언을 할 수도 없는 노릇이다.

이를 다음 포스팅 때 해결하고자 한다.

앞선 내용들을 바탕으로 진행하기 때문에 읽고 나서 읽는 것을 추천한다. 설명을 잘 하지 못해서 읽어도 모를 수도 있다. 이 글들은 복습을 위한 기록이니, 잘 못 알아 듣겠으면 다른 곳 가서 읽기를 권한다ㅋㅋㅋㅋ ㅜㅜ

일단 먼저 BFS가 뭔지에 대한 내용은 위 링크 중 땡땡 우선 탐색이라는 글에 좀 더 자세하게 정리되어 있고, 이 글에서는 BFS 방법으로 순회하는 과정을 나타낼 것이다.

중요 핵심

일단 너비 우선 탐색은 깊이 우선 탐색과 달라도 너무 다르다. 현재 정점 하나에 연결되어 있는 모든 정점에 순회를 해야하다보니 현재 정점에 연결된 각 정점마다 순서를 매겨서 기록해야 한다.

깊이 우선 탐색은 현재 정점에서 다음으로 갈 타겟을 정하기만 한다면 정점 방문(순회)과 현재 정점의 갱신이 한 번에 발생한다. 

그러나 너비 우선 탐색의 경우에는 정점 방문이라는 개념을 좀 더 확장해야한다. 단순히 방문만 하는 것이 아니라, 방문 후에 방문한 해당 정점을 큐 자료 구조에 넣는 작업까지가 정점 방문이라고 생각해야한다.

그리고 정점 방문과 현재 정점의 갱신이 동시에 발생하지 않는다. 정점 방문과 현재 정점의 갱신을 동시에 해버리면 나머지 연결되었던 정점에 접근할 기회가 박탈된다.

위의 예에서 현재 정점이 0이고 (ㄱ, ㄴ)처럼 1 정점을 방문한 뒤 바로 현재 정점으로 갱신을 해버리면 0 정점에 연결되어 있던 2 정점에 접근할 수 있는 기회가 사라진다. 그렇기 때문에 정점의 방문과 현재 정점의 갱신이 동시에 발생하지 않는 것이다. 

이러한 이유 때문에 진짜 설명하기에 겁~~나 헤깔린다. 이러한 핵심적인 특징을 인지한 상태로 프로세스를 봐야한다.

순회 프로세스

먼저 다음과 같은 그래프에서 순회를 시작할 것이다.

정점 0은 시작 정점이므로 일단 방문 처리가 자동으로 된다. 정점 방문에 해당하는 부분이 순회라는 표현이고, 이는 접근 + 큐 기록 까지를 의미한다. 접근했다는 의미 또한 방문 Flag 배열에 값을 갱신하는 조작을 의미하는 것이다.

현재 정점에 연결된 모든 정점을 순회하는 과정이다.

현재 정점인 0 정점에 연결된 모든 정점에 대해서 순회가 완료되었으니, 큐에서 값을 꺼내서 그 값을 현재 정점으로 갱신하고, 다시 순회를 시작한다.

그리고 큐에 정점이 여전히 존재하므로 다시 큐에서 값을 빼내어 현재 정점을 갱신하고, 순회를 재시작한다. 그런데 2 정점 같은 경우는 순회 가능한 인접 정점이 없으므로 그냥 나가리~

큐에 정점이 여전히 존재하므로 다시 큐에서 값을 빼내어 현재 정점을 갱신하고, 순회를 재시작한다. 4 정점이 마지막 정점이긴 하지만 그림을 한 눈에 보는 우리나 아는 것이지 컴퓨터는 4 정점이 마지막 이라는 것을 아직 모른다! 그렇게 때문에 4 정점이 마지막이어도 원래 규칙대로 큐에 넣는다.

큐에 정점이 아직 존재하니 뽑고, 뽑힌 값으로 현재 정점을 갱신한다. 그런데 현재 정점에서 순회를 하려고 보니, 순회 가능한 인접 노드가 없다. 

그렇게 더 이상 큐에 값을 넣지 못하고, 큐가 비었으므로 모든 그래프를 순회했으므로 종료한다. 

0 -> 1 -> 2 -> 3 -> 4 순으로 순회가 이루어졌다.

진짜 뇌리에 박히겠다 박히겠어 정말 ㅋㅋ

이제 관련된 부분 코드를 보도록 하겠다.

코드 분석

큐가 새롭게 사용되므로 큐에 대한 코드가 필요한데 이미 만들어놓았던 배열 기반의 큐 코드를 활용할 것이다. 그런데! 그냥 큐는 배열 관리가 까다롭기 때문에 더 효율적인 배열 기반의 원형 큐를 사용할 것이다!

깊이 우선 탐색 코드에 대해서 바뀌는 부분과 추가되는 부분을 기록하겠다.

너무나도 기쁘게도 이거 하나가 변경된다.

ㄱ~ㅅ 순서대로 읽으면 된다.

전체 코드 및 실행 결과

전체 코드는 배열 기반의 원형 큐와 연결 리스트 BFS로 인해 변경된 그래프 코드 순으로 업로드를 하겠다.

배열 기반의 원형 큐 ArrayBasedCircleQueue.h -- -- -- -- -- 

연결 리스트 linkedlistforgraph.h -- -- -- -- --

BFS 로 인해 변경된 그래프 코드 BreadthFirstSearchGraph.cpp -- -- -- -- --

아래는 실행 결과이다.

이 두 탐색을 이용한 최소 비용 신장 트리 부터 해서 트리 부분의 AVL 트리, 해쉬 테이블 등등 더욱 복잡한 것들은 지금까지 포스팅 한 것들을 복습한 이후에 조금씩 업로드를 진행할 것이다.

그노므 DFS! DFS! 드디어 깔끔하게 정리를 한다. 이 탐색 기법 하나에 워낙 들어가는 내용이 많기 때문에 바로바로 정리하지 않으면 다시 처음부터 공부하는 수준으로 공부를 해야한다 흑흑...

이전의 포스팅의 내용을 기반으로 작성되기 때문에 이전 부분을 포스팅을 참고하라고 올려놓겠다.

중요 핵심

일단은 깊이 우선 탐색은 아래 세 가지가 핵심이다.

1. 깊이 접근하는 것
2. 왔던 경로를 되돌아오는 것
3. 정점 방문 여부를 기록하는 것

이 세 가지를 핵심으로 기록하겠다. 사용되는 예시는 간단하게 다음과 같다.

첫 번째, 깊이 접근한다는 것은 한 정점에서 연결되어 있는 정점 중 하나의 정점을 선택해서 파고 들어가고 또 그 정점에서 연결된 정점 중 하나의 정점을 파고 들어가는 식의 방법을 이야기 한다.

1로 갈지, 2로 갈지는 중요하지 않다. 0이라는 정점에 연결 되어 있는 정점이 1 먼저 연결되있는지, 2 먼저 연결 되어있는지에 따라 다르다. 즉, 정점의 연결 정보를 나타내는 연결 리스트의 정렬 구조에 따라서 1 노드와 2 노드 중 어떤 것을 선택하게 될지 결정된다는 소리이다. 어찌됐건 우리는 순회 하는 것이 목적이므로 어딜 먼저 방문하는지는 의미가 없다.

두 번째, 왔던 경로를 되돌아오는 것은 되돌아오면서 놓친 정점을 순회해야하는 것이다. 이 때 경로를 다시 되돌아오려면 경로를 일단 기록을 해야하는데 역행이므로 스택의 형식대로 기록하면 된다. -> 방문 추적을 목적으로 스택을 사용한다.

세 번째, 정점 방문 여부를 기록한다는 것은 일반 순차 배열을 이용하여 기록한다. 다음 그림에 설명을 포함시키겠다.

주요 3가지 핵심에 대해서 살펴보았고 이번엔 그 순서대로 그려볼 것이다...

순회 프로세스

시작 정점 0을 방문된 상태로 시작한다. -> 방문 Flag 배열에서 정점 0을 True 처리.

연결된 인접 정점은 1 정점과 2 정점인데 방문 Flag 배열을 봐도 방문 처리가 False이기 때문에 두 정점 모두 접근이 가능하다. 이 예에서는 2 정점을 방문하겠지만 1 정점으로 방문해도 순회 순서만 다를 뿐 다른 의미는 없다.

2 정점을 방문하면서 방문 Flag 배열에서 2 정점을 True(방문) 처리하고, 떠나온 0 정점은 다시 돌아가기 위한 발자국으로 남기기 위해서 스택에 넣는다.

위와 마찬가지 과정을 통해 2 정점을 떠나면서 스택에 2 정점을 넣고, 3 정점을 방문한 뒤 방문 Flag 배열의 3 정점에 대한 방문 여부를 True로 변경한다.

또 마찬가지로 같은 과정을 반복하는데 3 정점에서는 1 정점과 4 정점에 접근 가능하다 어디로 가든 상관없지만 이번 예에서는 4 정점에 방문할 것이다.

4 정점에서는 인접한 정점이 모두 방문 처리 되었으므로 이제 스택에서 값을 POP 함으로써 되돌아 가면서 그냥 지나친 정점을 탐색한다.

3 정점으로 돌아왔을 때, 보니까 1 정점을 방문하지 않고 그냥 지나쳤었기 때문에 1 정점에 방문한다. 이 때, 1 정점에 방문하기 위해서 3 정점을 떠나는 것이니 1 정점 방문 이후 다시 돌아오기 위해 3 정점을 다시 스택에 넣는다. 그리고 1 정점에 대한 방문 처리를 진행한다.

그리고 1 정점에서 인접 정점 모두 방문 처리 되었으니 Pop을 통해 돌아가고, 3 정점에서도, 2 정점에서도 마찬가지로 인접 정점 모두 방문처리 되었으므로 Pop을 통해 돌아가다가 0 시작 정점까지 Pop하여 스택이 빈 경우 비로소 모든 순회가 끝난 것이다.

0 -> 2 -> 3 -> 4 -> 1 순으로 순회가 이루어졌다.

진짜 뇌리에 박히겠다 박히겠어 정말 ㅋㅋ

이제 관련된 부분 코드를 보도록 하겠다.

코드 분석

스택이 새롭게 사용되므로 스택에 대한 코드가 필요한데 이미 만들어놓았던 배열 기반의 스택 코드를 활용할 것이다. 스택 설명 기록은 아래의 링크에서 확인하면 된다.

먼저 바뀌는 부분과 추가되는 부분이다.

그래프 내의 방문 Flag 배열이 추가 된다.

방문 처리를 수행하는 함수가 추가된다.

깊이 우선 탐색을 수행하는 함수이다.

한 함수이지만 라인 수를 맞춰서 읽으면 된다... 이전 자료구조인 스택에 대한 사용 방법 또한 익혀야 하고 너무나도 추상적이라서 용어 설명이 너무 어려운 것 같다..ㅠ.ㅠ

그래프 종료 및 메모리 공간 해체 관련 코드이다.

전체 코드 및 실행 결과

전체 코드는 배열 기반의 스택과 변형된 연결리스트(오름차순으로 노드를 삽입; 이전에는 그냥 삽입했다.), DFS로 인해 변경된 그래프 코드 순으로 업로드 한다.

배열 기반의 스택 ArrayBasedStack.h -- -- -- -- --

변형된 연결 리스트 linkedlistforgraph.h -- -- -- -- --

DFS로 인해 변경된 그래프 코드 DepthFirstSearchGraph.cpp -- -- -- -- --

일단, 위의 그래프 기본들을 기반으로 작성되기 때문에.. 링크해둔다.

뭐 BFS니 DFS니 이상한 용어 써가면서 아는 척 오졌던 학과 동기들 보면 이제 이렇게 생각하라. 

대단한 친구들이네

근데 사실, 이상한 용어가 나와서 오히려 겁 먹고 어려울지 모르겠지만 조금만 이해하면 그렇게 어렵지 않다. 

BFS 나 DFS 모두 Search의 일종이다. 뭐 말로만 Search지 순회다 순회. 순회하면서 원하는 값이 나오면 조건문으로 캐치하면 그게 Search이지 무엇이겠는가?

아무튼 두 개념 모두 순회인데, 순회하는 방법이 다르다. 그래서 두 가지를 모두 동시에 기록해 두려고 한다.

DFS (Depth First Search)

DFS는 Depth First Search 로 깊이 우선 탐색이다. 말 그대로 우선적으로 그래프를 깊게 깊게 파고 들어간다는 것이다. 그렇게 전부 파고 들어 갔다면 다시 되돌아 나오면서 깊게 파면서 놓쳤던 주변을 살펴보며 나오는 형식이다.

위 그림과 같은 식인데, 윤성우 교수님의 자료구조 책에서는 다음과 같이 표현한다. "너니까 이야기해주는거야" 하면서 깊고 친한 관계라고 생각하는 친구들에게만 비밀 이야기를 전달한다. 그러다보니 3번과 같은 정점에게도 퍼져있는 비밀 이야기가 소문이 나는 상황에 비유를 하셨다ㅋㅋ

중요한 것은 돌아 나오는 것과 각 정점들의 방문 여부이다. 이 둘을 어떻게 관리하고 코드로써 표현할 것인지가 큰 쟁점이다.

첫째로 돌아 나온 다는 것은 그 발자취를 기록하면 된다. 기록할 때 그냥 순서대로 기록하고 기록한 순서대로 다시 보는게 아니라 돌아나가는 것은 역재생하는 것과 같으므로 스택 자료구조를 이용한다.

둘째로 정점들의 방문 여부는 인덱스 값과 정점 값을 매칭 시킨 flag 역할을 1차원 배열로 처리를 하면 된다.

참고>>

이런 경로 또한 가능하다. 구현해 보면 알겠지만 하나의 정점에 연결된 정점들 중 어떤 것을 선택하는지에 대한 로직은 순회 로직에 들어가지 않는다. 그러니까 시작 정점에서 왼쪽 정점으로 갈지, 오른쪽 정점으로 갈지를 중요시 하지 않는다는 소리이다. 이는 정점간 연결을 나타내는 자료구조 내에서 어떤 순서로 연결 정보를 저장했는지에 따라서 다르게 나온다. 그니까 어떤 경로든 해당 탐색의 기본 원리에만 들어 맞다면 경로 순서의 맞고 틀리고를 따지는건 의미가 없다는 소리이다.

BFS (Breadth First Search)

반면에 BFS는 Breadth First Search 로 너비 우선 탐색이다. 말 그대로 우선적으로 넓게 넓게 퍼뜨리며 그래프를 파고들겠다는 것이다. 그러니까 어떤 정점을 순회하기만 했다 하면 바로 그냥 그 해당 정점에 연결된 모든 정점에게 방문하는 것이다. 

이건 약간 예로 들자면, 정책 발표에 따른 메시지 퍼짐이다! 출발 지점에서 정책을 발표한다. 그 양 옆 정점은 그 해당 정책을 티비를 통해 실시간으로 들은 정점들이고, 그리고 나서 그 실시간으로 들은 정점들이 지인을 만날 때마다 그 정책에 대해서 이야기하는 모습 같다고 비유할 수 있다.

중요한 것은 방문/순회 차례에 대한 기록과 각 정점들의 방문 여부이다. 이 둘을 어떻게 관리하고 코드로써 표현할 것인지가 큰 쟁점이다. 

첫째로 물론 각 정점들의 방문 여부는 위에서와 마찬가지로 flag 역할의 1차원 배열로 충분하다. 

둘째로 방문/순회 차례에 대한 기록은 위 DFS와는 조금 다르다. 방문한 정점과 연결된 정점들을 모두 방문하고, 그 다음 순서까지 정한 뒤 넘어가야헌다 그것이 BFS에서의 순회라고 보면 된다. 그러기 위해서는 꼭 순서를 기록해야한다. 그렇지 않으면 순회에 비효율이 생길 수 있다. 이 때 사용하는 것이 큐이다

이렇게 두 개념을 코드를 통해 구현해 볼 것이다 

드디어 그래프에 대한 포스팅이다. 여러가지 병행하며 정리할 것도 너무 많아서 ㅋㅋ 미루고 미루다 이제 올리게 된다. 오늘은 그래프의 기본 중에 기본인 용어 및 정의 정리이다.

그래프란?

먼저, 그래프란 아래의 설명과 같다.

비선형 자료구조, 즉, 트리 또한 그래프의 일종이라는 것을 알 수 있다!

이러한 그래프에는 간선의 방향성이라든가, 가중치, 부분 집합에 따라서 그래프의 종류가 나뉜다 이를 하나씩 나열해 볼 것이다.

무방향 / 방향 그래프

간선에 방향이 없고, 있고의 차이이다.

완전 그래프

정점 별로 모든 정점과 연결되어 있는 그래프를 완전 그래프라고 하는데, 이 때, 방향 완전 그래프는 무방향 완전 그래프보다 간선의 수가 2배 많다.

가중치 그래프와 부분 그래프

가중치 그래프는 간선에 가중치를 두고, 예를 들어, A에서 C로 가려면 3+1 혹은 4+5 비용이 든다고 표현할 수 있다. 부분 그래프는 말 그대로 그래프의 부분만을 그려낸 것이다.

그래프의 집합 표시

이러한 그래프를 집합 형태로 표현을 할 수 있다

그래프를 코드로 표현하기 위한 약속

그래프는 진짜 들쑥 날쑥인데 어떻게 표현하지 싶었는데, 사람들은 참 머리가 좋은 것 같다.

그래프가 어떻게 생겼든, 크기가 어떻든 정점 사이가 얼마나 멀든 좁든 간에 각 정점과 그 사이의 간선만 표현할 수 있다면, (예를 들어 어느 점과 어느 점이 어떤 선으로 연결되어 있는지 등의 정보) 오케이이다.

그 정점과 간선 등의 관계를 표현하는 방법은 위 그림에서처럼 인접 행렬, 인접 리스트가 그 방법이다. 방법은 그림으로 보는 것이 자세하고 편해서 그림으로 표현을 해 보았다.

지난 포스팅에서 순회까지 끝냈다. 이제 탐색과 삭제가 남았다.

바로 이어서 탐색을 보자.

이진 탐색 트리의 탐색

이진 탐색 트리에서 탐색과 순회는 다르다. 순회는 모든 노드를 방문하는 것을 이야기하지만, 탐색은 가장 효율적이고 적은 깊이로 노드를 방문하여 원하는 값을 찾는 것인가이다.

1번 : 찾으려고 하는 5 값이 루트 노드의 10 값보다 작으니, 왼쪽 서브 트리를 대상으로 하고 인덱스를 옮긴다.
2번 : 찾으려고 하는 5 값이 노드의 4 값보다 크니, 오른쪽 서브 트리를 대상으로 하고 인덱스를 옮긴다.
그 이후 발견.

위와 같이 서브 트리를 대상으로 옮기고, 또 서브 트리의 서브 트리로 대상을 옮기고 하는 과정에서 봤을 때, 재귀로 해결할 수 있다! 탐색 또한 마찬가지로 순회처럼 재귀를 이용하여 문제를 해결해갈 것이다.

코드를 보면 다음과 같다.

매개 변수인 sub_root에는 서브 트리의 루트 노드가 항상 들어온다. 이 서브 트리의 루트 노드와 값을 비교하여 같으면 탐색 완료, 작으면 다시 왼쪽 서브 트리 재탐색을 위한 재귀 호출, 크면 다시 오른쪽 서브 트리 재탐색을 위한 재귀 호출 순서로 조건 및 연산 수행을 진행하면 된다.

이진 탐색 트리의 삭제

아.. 삭제는 ㅋㅋ 여러 유형으로 나뉜다 쉽지가 않다. 왜냐하면? 자식이 없는 단말 노드를 삭제할 경우, 그냥 해당 단말 노드만 제거하면 끝나는 문제이지만 자식 노드가 존재하는 노드를 삭제할 경우 문제가 커진다. 

일단은 그림 형태로 유형 별로 확인한 뒤 코드를 보자.

삭제할 타겟이 단말(리프) 노드인 경우

간단하다. 그냥 끝에 있는 노드이므로 바로 삭제를 하면 되는데, 다만! 삭제할 타겟의 부모의 링크(left or right)가 NULL을 가리키도록 설정해주면 된다. 다음의 그림과 같이 말이다.

위에 해당하는 코드는 다음과 같다.

삭제할 타겟의 자식 노드가 하나만 존재하는 경우

이 경우 또한 간단하다. 아래의 그림과 같은 경우인데 삭제할 타겟의 부모의 링크와 삭제할 타겟이 가지고 있는 하나의 자식 노드를 연결해주면 된다.

위에 해당하는 코드는 다음과 같다.

삭제할 타겟의 자식 노드가 두 개 모두 존재하는 경우

이 경우는 좀 답이 없다. 물론 설명하기 답이 없다는 것이다. ㅋㅋ 좀만 생각해보면 쉽다! 

먼저, 이전의 노드 삭제 유형들처럼 타겟을 삭제하고 부모와 자식을 연결해주는 등의 간단한 방법으로 끝날 문제가 아니다.

삭제할 타겟 노드가 자식 노드를 두 마리나(?) 가지고 있는 바람에 왼쪽 자식 노드의 서브 트리와 오른쪽 자식 노드의 서브 트리를 만족할 수 있는 값으로 대체 노드 선별해야한다. 

아 그러면? 삭제할 타겟 노드의 자식들 중 하나로 선택하면 되는 것 아니냐?

응 안된다. 왜냐하면 그림에 자세히 설명을 해 놓았다. 아래의 그림에서 두 번째 케이스에 해당하는 경우다. 혼돈하지 말아야 한다.

그러면 자식 중에 아무나 하나를 그냥 올리면 안되면 어떻게 올려야 하나?

왼쪽 서브 트리에서 가장 큰 값을 갖는 노드를 대체 노드로 선별하거나,
오른쪽 서브 트리에서 가장 작은 값을 갖는 노드를 대체 노드로 선별해야한다.

두 경우 중 하나를 선택해야 한다. 그 선택은 뭐 개발자 마음이고, 코드 작성자 마음이다. 선택했다면 다음과 같은 순서를 떠올릴 수 있다.

1. 대체 노드의 링크들을 타겟 노드의 링크로 전부 동기화 한다.
2. 대체 노드의 부모의 링크를 적절한 포인터(노드 혹은 NULL)로 변경한다.
3. 타겟 노드를 제거한다.

이러한 순서를 떠올렸는데 여기서 약간의 꼼수(?)를 쓴다고 하며, 지혜를 발휘한다고 읽는다. 뭐냐하면, 대체 노드를 굳이 드러내어 타겟이 있던 자리로 옮겨서 링크를 수정할게 아니라, 타겟 노드의 값만 대체 노드의 값으로 바꿔준다면 링크들을 굳이 변경할 필요가 없기 때문이다. 

1번 연산이 굉장히 부담 그 자체이다. 헤깔려죽겠는데.. 2번과 3번은 어차피 대체 노드에 대해서 해야할 작업이기 때문에 그렇다 치더라도, 1번 연산은 안 해도 될 일을 하는 것과 다름이 없다! ㅋㅋ

그래서 뭐 어찌 되었든 간에 왼쪽/오른쪽 중에 선택을 했다면, 다음 그림으로 그 선택 이후의 과정을 설명한다. 번호 순서대로 색깔과 연관 지어서 차근 차근 읽으면 된다.

이에 따른 코드는 아래와 같으며, 타겟 노드를 루트 노드로 한 서브 트리의 오른쪽 자식의 서브 트리 군에서 가장 작은 값을 선택하여 타겟 노드의 자리에 대체하기로 하였다.

하.. 이로써 삭제까지 끝이다.

일요일에 정말 집중도 안되고, 포스팅을 하면 할수록 코드 작성 때는 떠 올리지도 않았던 세세한 부분까지 의구심이 들어서 시간이 두배, 세배 드는 것 같다.

뭐 다음 시간에는 코드와 실행 결과만 올린다.

여기에 이어서 이진 탐색 트리에 대해서 분석하고 기록할 것이다.

준비 및 구성

먼저, 이전 포스팅에서의 개념과 조건들을 토대로 어떻게 준비할 것인가이다!

트리 구성의 준비물이 되는 노드이다! 노드의 구성은 다음과 같다.

크게 설명할 것이 없다. 이 노드 구조체를 통해서 값과 이진 탐색 트리 조건에 맞는 자식 노드를 가리킬 포인터 2개의 구성이 끝인 것이다. 

이런 구조체로 노드를 생성할 때에는 꼭 다음과 같은 상태로 초기화되는 것이 보장되어야 한다.

트리에 접근하는 방법(루트 노드에 접근하는 방법)

삽입 연산을 하기 이전에 트리에 접근할 때에는 무조건 루트 노드부터 접근을 시작해야한다. 그 루트 노드로의 접근을 어떤 식으로 할 수 있는지, 그 루트 노드를 어떻게 정하는지를 기록한다.

위 코드는 메인 함수 내에서 실행되는 코드로 root 라고 하는 포인터로 트리의 루트 노드를 가리키도록 설계해놓았다.

트리에 노드 삽입 연산

먼저, 삽입 연산은 그림으로 나타냈을 때, 아래와 같다.

위 삽입 연산에 해당되는 코드를 함께 보는게 좋을 것 같다.

먼저, 트리에 노드가 0개 일 때 의 노드 생성이다.

트리에 노드가 1개 이상일 경우에는 다음처럼 삽입 연산을 수행한다.

트리 순회 연산

트리에 노드를 추가만 해서는 뭘 하는가! 순회도하고 탐색도 할 수 있어야, 탐색 트리이지. 먼저, 순회 연산에 대해 알아본다.

하.. 일단(ㅋ) 순회 연산은.. 여러 종류가 있다. 이 여러 종류의 연산 과정을 내 블로그 내에서 최초 도입한 신개념 비디오 장치를 통해 촬영된 것을 올릴 것이다.

일단 트리에서의 순회는 조금 특이하다. 

첫 노드인 루트 노드를 기준으로 한 큰 트리가 존재하지만, 첫 노드의 자식을 기준으로 또 하나의 서브 트리가 존재한다. 이 서브 트리를 하나의 대상으로 연산이 이루어지고, 또 그 자식 노드를 기준으로 또 서브 트리가 존재하며 단말 노드가 될 때까지 서브 트리 군이 형성된다. -> 재귀적으로 문제를 풀 수 있다는 것이다.

그래서 이 순회에서는 재귀를 통해 순회를 진행할 것이다. 삭제 또한 마찬가지이나 다양한 방법들을 넣기 위해서 순회에만 재귀를 적용하도록하고, 삭제에서는 반복문을 통해 삭제를 진행한다.

전위 순회 : 루트 노드를 기준으로 먼저 루트 노드의 값을 읽고, 그 다음 순차적으로 왼쪽 트리를 방문하고, 그 뒤에 오른쪽 트리를 방문하는 방법이다.

서브 트리의 루트 방문(값 Get) -> 왼쪽 링크를 통한 왼쪽 서브 트리 방문 -> 오른쪽 링크를 통한 오른쪽 서브 트리 방문

중위 순회 : 루트 노드를 기준으로 먼저 왼쪽 트리를 방문하고, 그 다음 해당 루트 노드의 값을 읽고, 그 다음 오른쪽 트리를 방문하는 방법이다.

왼쪽 링크를 통한 왼쪽 서브 트리 방문 -> 서브 트리의 루트 방문(값 Get) -> 오른쪽 링크를 통한 오른쪽 서브 트리 방문

후위 순회 : 루트 노드를 기준으로 먼저 왼쪽 트리를 방문하고, 그 다음 오른쪽 트리를 방문한 뒤에 해당 루트 노드의 값을 읽는 순회이다.

왼쪽 링크를 통한 왼쪽 서브 트리 방문 -> 오른쪽 링크를 통한 오른쪽 서브 트리 방문 -> 서브 트리의 루트 방문(값 Get)

레벨 순회 : 레벨 순회는 레벨 1부터 트리의 말단 리프 노드들이 있는 레벨까지 큐 자료 구조에 순서대로 넣고 출력하여 순회하는 간단한 순회 법이며, 레벨 순서 & 왼 -> 오 순으로 순회가 이루어진다.

각 순회의 실제 결과

다음 포스팅은 이진 탐색 트리에서 탐색과 삭제 연산을 포스팅할 것이다.

오늘은 이진 탐색 트리이다. 

이전까지는 선형 자료 구조를 공부했었다. 뭐 예를 들어, 일반 배열 리스트, 연결 리스트, 스택, 큐 등의 선형 구조만 포스팅했는데, 드디어! 비 선형 자료 구조이다. 

데이터가 선형으로 연속되지 않는만큼 삽입, 삭제, 탐색 연산에 신경쓸게 더 많다. 그래도 이렇게 선형을 끝내고 비선형을 진행하는게 뿌듯하긴 하지만 이게 들이는 시간에 비해 결과가 그렇게 크지 않아서 비선형 자료구조를 여러 가지의 예제로 다양하게 진행하지는 못할 것 같고, 핵심만 파악할 수 있는 그런 알찬 예제로 기록을 해 둘 것이다.

나중에 다시 봐도 아~ 이게 트리지 할 수 있도록.

일단은 나는 연결 리스트 기반의 이진 탐색 트리를 구현할 것이며, 데이터의 삽입, 삭제, 탐색(레벨 순회, 전위 순회, 중위 순회, 후위 순회)까지 구현할 것이다. 

배열 기반의 이진 트리는 Heap 자료 구조에서 구현이 될 것인데, 아래의 링크에서 Heap 구조를 알 수 있다. 기본은 Heap이지만 내용은 거의 우선 순위 큐이다. 다만, 큐 형태로 Wrapping만 하지 않았을 뿐...

특이사항이라면,

이전과 마찬가지로 메모리 관리는 기존에 공부했던 배열 기반 스택을 통해 이루어진다. 
레벨 순회를 위해서 배열 기반 원형 큐를 이용한다.

트리를 제외하고 부가적으로 자료구조를 이용할 때에는 메모리를 할당하지 않는 배열 기반으로 

그렇다면 군말없이 바로 시작해보자!

트리란? 

먼저 트리의 구조나 용어를 설명한다. 트리는 이러하다.

트리는 다음과 같이 여러 형태의 트리들이 올 수 있지만

그 중에 이진 탐색 트리에 대해서 기록할 것이다. 위 그림에서 가운데에 있는 트리 구조가 가장 이진 탐색 트리를 잘 나타낸 이진 탐색 트리의 모형이라고 보면 된다.

그러면 이진 트리란?

이진 트리에 논하기에 앞서, 가장 작은 단위인 노드부터 자세히 살펴보면 다음과 같은 구조로 되어 있다.

이런 노드를 요리조리 이용하면 트리를 완성시킬 수 있는데, 노드가 이렇게 최대 두 개의 자식을 가질 수 있는 형태로 이루어져 있으며, 이러한 노드들로 구성되어 있는 트리를 이진 트리라고 한다.

그러면 이진 탐색 트리는 또 무엇인가? 이진 탐색 트리는 이진 트리이긴 한데, 탐색이 가능한 트리라서 이진 탐색 트리라고 한다! 그러기 위해선 일정 조건들이 추가 되어야 하는데 조건은 다음과 같다.

위와 같은 조건을 가지고 있는 이진 트리가 이진 탐색 트리가 될 수 있다.

다음 포스팅은 삽입, 삭제, 탐색을 적절히 나눠서 여러 차례 포스팅한다.

오늘은 덱? 디큐? 라고 불리우는 자료구조이다.

Dequeue 는 매우 혼종이다. 큐라고는 불리우는데 큐의 특징 이외에 스택의 특징을 가지고 있기 때문이다. 선입선출 / 후입선출 등의 개념을 모두 가지고 있다. 먼저 들어온 놈이 먼저 나갈 수 있고, 나중에 들어온 놈이 먼저 나갈 수도 있다는 것이다.

도데체 어떤 구조이길래 위와 같은 특징을 가지고 있을까? 다음과 같다.

위와 같은 구조이다. 뒤에서도 (tail의 사이드) 추가 및 삭제가 가능해야 하기 때문에 꼭 양방향 링크로 구성이 되어야 한다!!!!! 

그런데 뭐, 이제까지 다 다뤄봤던 구조들이기 때문에 예를 들어, 양방향 링크라든지 head와 tail이 함께 있는 구조라든지 어렵지 않은 부분들이므로 간단하게 설명한다.

초기화와 Dequeue의 비워짐 / 꽉 참의 확인

먼저, 초기화는 Head와 Tail 을 NULL로 초기화 하는 것으로 시작한다.

그리고 이러한 초기화에 따라서, Head와 Tail이 NULL 인 경우가 비워진 경우이고, 해당 Dequeue의 꽉 찬 상태는 확인할 필요가 없다. 왜냐하면 연결 기반의 큐이기 때문에 추가하는 수의 제한이 없다고 보면 되기 때문이다.

노드 추가

위 그림으로 설명이 충분하다고 생각한다. 노란색이 추가되는 노드이고, head와 tail 은 각각 옮겨가는 것을 표현한 것이다.

노드 삭제

노드 그림을 그리지 않고 코드로만 설명해도 되겠다고 판단하여 그림을 그리지 않는다. 코드의 주석만으로 충분한 설명이 되었다고 본다.

탐색

탐색은 다른 리스트들과 마찬가지로 링크들을 타면서 순회하는 것이기 때문에 딱히 구현하지 않았다.

메모리 관리

배열 기반의 원형 큐를 통해 메모리 관리를 한다.

소스 코드 및 실행 결과