IT's me

[자료구조] 이진 탐색 트리의 구현(2) 삽입과 탐색

이번 포스팅에서는 이진 탐색 트리의 삽입과 탐색이 어떻게 구현되는지 알아보겠다.

앞선 포스팅에서 말했듯이 이진 트리의 함수들을 사용하여 이진 탐색 트리의 함수를 만들어보겠다.

코드로써 구현을 하는 것도 중요하지만, 어떠한 식으로 삽입과 탐색이 이루어지는가를

이해하는 것도 상당히 중요하기 때문에, 그 부분에 중점을 두고 이어 나가보도록 하겠다.

point -> 삽입과 탐색의 과정에서 데이터는 key값으로 사용된다. 즉 중복이 있으면 안된다!!

01. 이진 탐색 트리의 삽입과정 (출처 : 윤성우의 열혈 자료구조)

(1) 이진 탐색 트리의 특성상 자신의 왼쪽은 무조건 자신보다 작을 것이며

자신의 오른쪽은 무조건 자신보다 클것이다.

(2) 자신(루트노드)보다 작다면 왼쪽으로 보내고, 크다면 오른쪽으로 보내면된다. 간단한다.

(3) 이런식으로 위치를 찾다가 더 이상 비교대상이 없다면( 끝에 이르렀다면 ) 그 자리에 삽입되게 된다.

02. 이진 탐색 트리의 삽입 구현

03. 이진 탐색 트리의 탐색 구현

이진 탐색 트리의 삽입과 탐색의 과정을 구현해보았다.

1. 가장 중요한 것은 key값을 통해 삽입과 탐색을 진행한다는 것! 즉 중복이 있으면 안된다.

2. 기존의 이진 트리를 구현하는 데 썼던 함수들을 활용하여 구현을 했다는 것!

3. 현재의 노드의 왼쪽은 자신보다 작은 값이 들어가고, 오른쪽은 자신보다 큰 값이 들어가는 특징을 활용한다.

4. 코드로 이해하는 것도 중요하지만, 전체적인 알고리즘을 이해하는 것도 중요하다.

다음 포스팅에서는 이진 탐색 트리의 구현 중 살짝 난이도가 있는 삭제의 과정을 구현해보겠다.

[자료구조] 이진 탐색 트리의 이해(1)

이진 탐색 트리는 말 그대로 탐색에 특화된 이진 트리이다.

앞서 이진 트리를 공부했기 때문에 이해와 구현이 어렵진 않겠지만,

기본적인 기능인 삽입, 삭제, 참조 중 삭제의 구현이 까다롭다.

왜 까다로운지, 어떻게 구현하는지는 차차 알아가 보도록하겠다.

이진 탐색 트리는 이진 트리의 확장 버전이라고 생각하면 된다.

이진 탐색 트리 = 이진 트리 + 데이터의 저장 규칙    ( 저장 규칙은 곧 탐색 규칙이라 말할 수 있다. )

위의 트리는 이진 탐색 트리를 나타낸 것이다.

루트 노드보다 작은 쪽은 왼쪽으로, 루트 노드보다 큰 쪽은 오른쪽으로라는 단순한 저장 규칙이다.

자세히 보면 꼭 루트노드가 아니더라도 어떠한 노드를 찍었을 때 왼쪽은 현재 노드보다 값이 작고 오른쪽은 크다.

정리하자면

1. 이진 탐색 트리의 저장된 키는 유일하다.

2. 루트 노드의 키 > 왼쪽 서브 트리의 루트 노드의 키

3. 루트 노드의 키 < 오른쪽 서브 트리의 루트 노드의 키

4. 왼쪽과 오른쪽 서브트리 또한 이진 탐색 트리이다.

지금까지의 내용은 이진 트리에서 간단한 규칙하나만 적용되었을 뿐이다.

하지만 이 간단한 규칙에 의해 탐색에 엄청난 효율을 가져올 수 있는데, 그 구현은 다음 포스팅에서 다루도록 하겠다.

[자료구조] 우선순위 큐의 완성

힙을 사용하여 삽입, 삭제 등 우선순위 큐와 근접하게 완성해 보았다.

하지만 지금까지 구현한 우선순위 큐에는 한가지 문제점이 있는데

데이터와 함께 우선순위에 대한 정보를 사용자가 직접 지정해주어야 한다는 것에 있다.

주어진 데이터를 기반으로 우선순위가 정해지며 우선순위가 정해지는 기준을 사용자가 지정해주는 것이 좋은 자료 구조이다.

자 그럼 우선순위를 정하는 기준의 정보를 담은 함수를 정의하여 함수 포인터로 넘겨주는 식의 구현을 해보자.

1. 구조체 재정의

우선 기존의 힙 구조체를 지우고 함수 포인터를 멤버로 갖는 새로운 힙 구조체를 생성하자.

이 함수 포인터로 전달된 정보를 통해 우선순위를 정할 것이고, 정의 기준은 사용자의 필요에 따라 정한다.

위의 코드를 보면 함수 포인터의 선언과 멤버 선언이 각각 2개로 나누어져 있는데,

typedef로 함수 포인터를 선언하는 두 가지 방법이 있음을 보여주기 위한 것이다.

02. 초기화 함수

초기화 함수에 우선 순위를 정하는 기준에 대한 정보를 담은 함수를 적용시키고 있다.

02. 우선순위가 높은 트리 찾기 함수

원래는 사용자가 정해준 우선숭위에 대한 정보를 통해 처리되었다면

지금은 자용자가 정해준 함수를 통해 우선순위에 대한 처리가 이루어지고 있다.

03. 삽입

삽입 또한 사용자가 지정한 우선순위에 의해 처리되던 기존 방식과는 달리

사용자가 지정한 함수에 의해 우선순위가 가려지며, 새 노드의 위치가 결정되고 있다.

매개변수로 원래는 pr이라는 우선순위 정보가 전달되었지만 지금은 없어졌다.

04. 삭제

삭제 또한 삽입과 마찬가지로 진행된다.

05. 메인

초기화를 할 때 우선순위 기준 정보를 담은 함수를 적용시켜주고 있다.

지금까지 우선순위 큐의 이해와 구현과정에 대해 알아보았다.

다음 부터는 이진 탐색트리에 대해 공부해보도록 하겠다.

[자료구조] 우선순위 큐의 구현(3) - Delete , Insert

오늘은 우선순위 큐의 삽입, 삭제 과정에 대해 알아보도록 하겠다.

저번 시간에 두 자식 노드 중 우선순위가 높은 놈을 찾고, 자식이 없다면 0을 리턴하는 함수를 정의했다.

그 함수를 적극 활용하여 Delete 과정을 이해해 보도록 하자.

Delete 과정을 잘 이해한다면 Insert 과정 또한 쉽게 이해할 수 있을 것이다.

1. 우선순위 큐의 Delete 구현

2. 우선순위 큐 삭제의 과정

1. 가장 마지막 노드를 추출한다.

2. 인덱스 1번에 위치한 노드가 삭제되기 때문에 그 밑의 자식노드들과 마지막 노드의 우선순위를 비교한다.

3. 자식노드의 우선순위를 비교할 때, 저번 포스팅에서 정의한 GetHiPriChildIDX() 함수를 사용한다.

4. 현재의 노드가 마지막 노드보다 우선순위가 높다면 한칸 위로 이동한다. (1번이 빠졌기 때문에 공간을 메운다.)

5. 마지막 노드보다 우선순위가 낮거나, 자식노드가 더이상 없을 때, 마지막 노드의 자리가 결정된다.

3. 그림으로 이해(..?)

우선순위 큐의 Delete 구현 소스 우측에 적혀있는 번호와 위 그림의 번호의 동작과 일치한다. (그림이 쪼금 애매하다.)

쉽게 말해서, 힙의 마지막 데이터를 빼서, 가장 위쪽에서부터 차례로 비교를 해오면서 내려온다.

그리고 마지막 노드보다 우선순위가 높다면 한칸씩 위로 이동하게 해주는 것이다.

4. 우선순위 큐의 Insert 구현

5. 우선순위 큐의 삽입 과정

1. 힙의 마지막 자리에 새로운 노드를 배정 (실제로 넣지는 않고 가정만 한다.)

2. 그의 부모노드와 우선순위를 비교하여 위치 변경

3. 삭제의 과정이 위에서 밑으로 였다면, 삽입의 과정은 밑에서 위로

오늘은 우선순위 큐의 Delete와 Insert 과정에 대해 알아보았다.

다음 포스팅에서는 좀 더 유연성있게 우선순위를 정하는 힙에 대해 알아보도록 하겠다.

[자료구조] 우선순위 큐의 구현(2) - Helper Function

--> 초기화와 힙이 비었는지 확인하는 함수

--> 그리고 특정 노드의 인덱스를 전달하면, 부모 노드, 왼쪽 자식, 오른쪽 자식의 인덱스 값을 반환하는 함수

특정 노드의 부모, 왼쪽 자식, 오른쪽 자식 노드의 인덱스 값을 반환하는 함수의 구현이 이해가 되지 않는다면

우선순위 큐의 이해(3)으로 가서 인덱스 값을 구하는 간단한 공식을 이해해야 한다.

우선 순위가 높은 자식의 인덱스 값을 반환하는 함수

설명에 들어가기 앞서 힙은 완전 이진 트리라는 것을 다시 한번 숙지하자!

(1) 완전 이진 트리에서 왼쪽 자식 하나만 있는 트리는 0개 혹은 1개 뿐이다!

(2) 왼쪽 자식이 하나만 존재하는 트리가 있다면 그 왼쪽 자식 노드는 마지막 노드이다!

1. 자식 노드가 없는 경우

--> 왼쪽 자식 노드가 들어 갈( 혹은 들어간 ) 자리의 인덱스 값이 저장된 데이터의 개수보다 클 경우

--> 자식 노드가 존재하는 경우라면 총 데이터의 개수보다 클 수가 없다. (자식 노드 또한 데이터의 개수에 카운트 되었기 때문)

2. 자식 노드가 하나 있는 경우

--> 자식 노드가 하나 있는 경우는 완전 이진 트리에서 단 하나의 노드밖에 있을 수 없다.

--> 완전 이진 트리는 왼쪽부터 차곡차곡 저장되어 나가기 때문에 당연한 결과이다. (이해가 안된다면 그림을 그려보자.)

--> 또한 왼쪽 자식노드 하나만 존재하는 경우라면 그 노드는 힙에 저장된 마지막 노드이다.

--> 따라서 왼쪽 자식 노드의 인덱스와 저장된 데이터의 총 개수가 같다면 이는 자식 노드가 하나만 있는 경우이다.

3. 둘 다 존재하는 경우

--> 두 노드의 우선순위를 비교해서 우선순위가 높은 놈을 리턴한다.

--> 위에서 설명한 우선순위가 높은 노드를 리턴하는 방식은

매우 대표적인 연산문이기 때문에 잘 이해를 해 놓아야 한다!

오늘은 우선순위 큐를 구현하기 위한 Helper Function에 대해 알아보았다.

다음 포스팅부터는 삽입, 삭제에 대한 구현에 대해 다뤄보도록 하겠다.

[자료구조] 우선순위 큐의 구현(1) - 배열을 기반으로 한 힙의 구현

힙은 배열을 기반으로 구현하는 대표적인 이진트리이다.

-> 연결 리스트 기반은 마지막 위치에 새로운 트리를 추가하는 것이 쉽지 않다.

-> 배열을 기반으로 구현하는 이유는 힙의 마지막 위치에 추가하는 것이 쉽기 때문이다.

(우선순위 큐를 위한) 힙의 구현

1. 구현의 편의를 위해 배열의 인덱스 0은 비워둔다.

2. 왼쪽 자식의 노드의 인덱스 값 --> 부모 노드의 인덱스 값 x2

3. 오른쪽 자식의 노드의 인덱스 값 --> 부모 노드의 인덱스 값 x2 +1

4. 부모 노드의 인덱스 값 --> 자식 노드의 인덱스 값 /2 --> 정수형 나눗셈

꼭 알아야 할 점

1. 힙은 완전 이진 트리이다.

2. 배열 기반 (인덱스 0은 비워두기)

3. 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다.

4. 노드의 고유 번호가 저장되는 배열의 인덱스 값이 된다.

5. 우선순위를 나타내는 정수값이 적을수록 높은 우선순위를 나타낸다고 가정!

--> 힙에 저장된 노드의 개수와 마지막 노드의 고유 번호가 일치하기 때문에

마지막 노드의 인덱스 값을 쉽게 얻을 수 있다. 

(우선순위 큐를 위한) 힙의 헤더파일

오늘은 우선순위 큐의 구현을 위한 (우선순위 큐에 치우쳐진) 힙 구현에 대해 간단하게 알아보았다.

계속 해서 우선순위 큐의 구현에 대해 다룰 것이며, 위의 헤더파일에 다뤄진 함수들을 차근차근 구현해 나가도록 하겠다.

[자료구조] 우선순위 큐의 이해(2)

1. 우선순위 큐를 구현하기 위해 힙(heap)을 사용한다.

2. 우선순위 큐는 꼭 만족해야 하는 조건이 있다.

(1) 완전 이진 트리

(2) 자식노드의 우선순위 <= 부모노드의 우선순위

3. 힙(heap)의 삽입 과정 (출처 : 윤성우의 열혈 자료구조)

4. 힙(heap)의 삭제 과정 (출처 : 윤성우의 열혈 자료구조)

--> 루트의 우선순위가 가장 높기 때문에 (만족 조건2) 루트를 빼준다.

--> 마지막 노드가 루트 노드로 위치한 뒤, 자기자리를 찾아가는 과정에서 두 서브트리 중 우선순위가 높은 쪽과 교환하게 된다.

5. 삽입과 삭제 과정에서 보이는 성능 평가

(1) 배열 기반 우선순위 큐                                 삽입 : O(n)            --> 저장된 데이터 수 만큼 비교가 일어난 뒤에 자리를 찾게 된다.

  삭제 : O(1)

(2) 연결 리스트 기반 우선순위 큐                     삽입 : O(n)             -- 저장된 데이터 수 만큼 비교가 일어난 뒤에 자리를 찾게 된다.

  삭제 : O(n)

(3) 힙(heap) 기반 우선순위 큐                         삽입 : O(log2n)

  삭제 : O(log2n)

--> 4층 높이의 힙이 있다고 치면, 이는 각각의 우선순위에 따라 위치가 정해져 있을 것이다.

--> 삽입을 하기 위해서 루트 노드부터 우선순위를 비교를 해나간다.

--> 한 층에 한번씩만 비교연산을 하게 되면 자리를 찾게된다. (트리는 내려가면서 자리가 결정되는 구조이다.)

[자료구조] 우선순위 큐의 이해(1)

1. 큐 (queue)

큐는 대표적인 자료구조 중 하나이고 선입 선출(FIFO)의 동작을 한다.

즉, 들어간 순서대로 하나씩 빠져나오는 동작 구조이다.

때문에 큐는 선형 구조로 이루어져 있다.

2. 우선순위 큐 (priority queue)

이름이 똑같다고 해서 큐의 연장선에 있다고 생각할 수 없다.

우선순위 큐는 들어가는 순서와 나오는 순서가 상관이 없다.

들어가는 순서에 상관없이 우선순위가 가장 높은 놈이 가장 먼저 나오게 되어있다.

때문에 우선순위 큐는 비선형 자료구조로 이루어져있으며, 큐가 아닌 트리의 연장선상에 있다고 생각해야 한다.

3. 큐의 두 가지 연산

enqueue : 큐에 데이터를 삽입한다.

dequque : 큐에서 데이터를 꺼낸다.

4. 우선순위 큐의 두 가지 연산

enqueue : 우선순위 큐에 데이터를 삽입한다.

dequeue : 우선순위 큐에서 데이터를 꺼낸다. (우선순위를 근거로 deququq 연산이 진행된다.)

어떤 근거로?? --> 프로그래머가 결정할 수 있어야 한다.

5. 우선순위 큐의 구현 방법

1. 배열 기반                --> 구현이 간편하다. 데이터가 많아질 수록 이동과 비교에 대한 부담이 커진다.

2. 연결 리스트 기반    --> 구현이 간편하다. 이동에 대한 부담은 없으나 비교에 대한 부담은 여전하다.

3. 힙(heap) 기반        --> 이동과 비교에 대한 부담이 없다.

6. 그렇다면 힙(heap)이란?

완전 이진 트리이다.

--> 위에서 아래로 왼쪽에서 오른쪽으로 차곡차곡 저장해나가는 이진 트리..

(1) 최대 힙 - 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.

(2) 최소 힙 - 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 작거나 같아야 한다.

오로지 루트 노드와 자식 노드간의 값만 비교해서 저장해주면 된다.

같은 레벨의 노드에는 어떠한 정렬 기준이 없다.

우선순위 큐가 무엇인지 간단하게 알아보는 시간을 가졌다.

다음 포스팅에는 우선순위 큐를 직접 구현해보도록 하겠다.