[C++로 쉽게 풀어쓴 자료구조] 9장 이진 탐색 트리의 연산 요점정리

안녕하세요 공대생 블로거 여니입니다.

오늘은 C++로 쉽게 풀어쓴 자료구조 9장 이진 탐색 트리의 연산 요점정리 포스팅을 해보려 합니다.

 

이진탐색 트리는 이진 트리 기반의 탐색을 위한 자료구조로 효율적인 탐색 작업을 위한 자료구조입니다.

이진 탐색 트리의 정의에 대해 잠깐 살펴보도록 해요!

- 모든 노드는 유일한 키를 갖는다(힙에서도 잠깐 설명드렸지만 힙은 중복 가능하나 이진 탐색 트리는 X)

- 왼쪽 서브트리의 키들은 루트의 키보다 작다.

- 오른쪽 서브트리의 키들은 루트의 키보다 크다.

- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

 

이진 탐색 트리의 연산에 대해 알아보아요.

1. 탐색 연산

- 비교한 결과가 같으면 탐색이 성공적으로 끝난다.

- 비교한 결과 탐색 키가 루트 노드의 키 값보다 작으면 탐색은 이 루트 노드의 왼쪾 자식을 기준으로 다시 시작한다.

- 비교한 결과 탐색 키가 루트 노드의 키 값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.

 

내용출처 C++로 쉽게 풀어쓴 자료구조

순환을 사용해서 탐색을 진행합니다.

 

만약 ROOT값이 널이면, 널을 반환하고요.

키의 값이 루트값과 같다면 현재노드를 반환합니다.

만약 키의 값이 루트값보다 작다면 search(LEFT(root),key); 즉 루트의 왼쪽 노드를 search함수에 넣어서 순환을 이용합니다.

키의 값이 루트값 보다 크다면 오른쪽 노드를!!

 

이진 트리 탐색 코드 보여드릴게요

총 3가지의 방법이 존재합니다.

내용출처 C++로 쉽게 풀어쓴 자료구조

첫번째 방식은 순환적인 탐색 함수

즉 순환을 이용해서 탐색을 진행하는 방법입니다.

만약 루트값이 널이면 n을 반환하고요.

만약 키의 값이 루트값보다 작다면 아까 말씀드렸듯이 루트의 왼쪽값을 searchRecur함수 매개변수에 넣어서 순환함수를 실행시킵니다.

 

내용출처 C++로 쉽게 풀어쓴 자료구조

2번째 방식은 반복적인 탐색 함수입니다.

즉 반복문을 이용해서 하는 탐색 방법이죠.

(순환함수 쓰이지 않아요)

루트노드의 값이 널이 아닌경우에만 반복문을 실행시킵니다.

반복문 내용은 위에서 말씀드린 내용과 똑같아요.

 

 

내용출처 C++로 쉽게 풀어쓴 자료구조

3번째 방식은 순환적인 탐색함수입니다.

엥? 아까 하지 않았나?라고 생각하고 계시죠?

이거는 BinaryNode클래스의 멤버로 구현한 순환적인 탐색함수입니다.

여기서 주의해야할 점은 매개변수가 하나 줄어든다는 점!

 

2. 이진 탐색 트리 삽입

이번엔 이진 탐색 트리 삽입 연산에 대해 알아보도록 하겠습니다.

먼저 알고리즘부터 살펴볼게요.

내용출처 C++로 쉽게 풀어쓴 자료구조

insert(root, n)이 이진 탐색 트리 삽입함수입니다.

만약 루트의 값과 삽입하고자하는 노드의 값이 같다면 return;하고요.

만약 노드의 값이 루트의 값보다 작다면, 왼쪽 자식노드의 값이 널이면 그 자리에 삽입노드를 삽입해줍니다.

만약 널이 아니라면 순환함수 실행시킵니다. (매개변수값 변경 주의)

내용출처 C++로 쉽게 풀어쓴 자료구조

알고리즘을 먼저 이해한뒤에 코드를 보면 이해가 훨씬 빠르게 되지 않나요?!

근데 약간 헷갈리는 부분이 많긴 한듯하지만요..

 

마지막으로 삭제 연산에 대해 살펴보겠습니다.

3. 삭제 연산

삭제 연산이 가장 복잡해요.

경우의 수가 3가지나 되기 때문이에요.

찬찬히 살펴보도록 할게요.

 

첫번째. 삭제하려는 노드가 단말 노드일 경우를 살펴보겠습니다.

단말노드가 왼쪽, 오른쪽 자식이 없는 노드인거 알고 계시죠!?

그래서 단말노드만 삭제해주면 되는 가장 간단한 방법입니다.

(엇 18이랑 26사이에 연결선이 지워졌네요..)

내용출처 C++로 쉽게 풀어쓴 자료구조

먼저 단말노드인지 확인을 하고 부모노드가 널이면 루트노드에 널을 삽입해줍니다.

이 경우는 단말노드이면서 루트노드인 경우를 위해서 만든 조건입니다.

이 경우가 아니라면 부모노드의 왼쪽 자식 노드가 단말노드라면, 왼쪽 자식노드에 널을 대입해줍니다.

오른쪽 자식 노드가 단말노드라면 오른쪽 자식노드에 널을 대입해주면 되겠습니다.

두번째. 삭제하려는 노드가 하나의 서브트리만 가지는 경우에 대해 살펴보도록 하겠습니다.

내용출처 C++로 쉽게 풀어쓴 자료구조

68을 삭제하고 68의 자식노드인 99를 35인 부모노드와 연결해주면 됩니다.

 

 

세번째. 삭제 노드가 두개의 서브트리를 가지고 있는 경우

가장 복잡한 방식입니다.

 

내용출처 C++로 쉽게 풀어쓴 자료구조

왼쪽 서브트리와 오른쪽 서브트리중에서 후계노드를 먼저 탐색해야 합니다.

왼쪽 서브트리에서는 가장 큰 값 , 오른쪽 서브트리에서는 가장 작은값 즉 12와 22중에 후계노드를 고르면 되는데

이 책에서는 22를 선택했으므로,, (둘중 아무거나 선택해도 상관은 없습니다.)

 

코드를 직접 손으로 쓰면서 정리를 해나가니까 이해가 확실히 되네요

(시간이 오래걸리는게 단점이지만 확실하게 알고 갈 수 있어서 좋은 방법인 듯 합니다.)

지금까지 여니였습니다

구독 좋아요!