#009_자료구조와 알고리즘_이진 탐색 트리

안녕하세요 삽잡이입니다.

날이 정말로 real 덥네요... 하... 차라니 습하지만 않아도 좋을텐데...

아무튼...

이번 시간에는 이진 탐색 트리를 알아보겠습니다. 트리... 영어 아시죠 Tree 푸하하 나무입니다.

자료들이 나무형태로 쭉쭉 펴나가며 보관되는 방식입니다.

머릿속에 나무를 떠올려보세요...

가지가 서로 붙어서 순환되는 모습인 나무가 있을까요?

또한, 가지가 연결되 있지 않고 고립된 가지가 있는 나무가 있을까요?

없죠... 명백히

트리의 경우 Cycle 즉, 순환적이지 않으며 고립된 부분이 없는 구조여야합니다.

이와 같은 트리 구조에는 부모와 자식간에 계층적인 구조를 지니게 됩니다.

하나의 노드가 가질 수 있는 최대 노드의 개수가

2 개이면 이진 노드, 3 개이면 삼진 노드 트리라고 말할 수 있습니다.

트리의 요소에 대해서 알아보도록 하겠습니다.

우선, 트리에 자기의 조상 즉, 부모가 없는 노드를 뿌리(Root)라고 부를 수 있습니다.

그 외에 부모 노드가 있으면서 자식 노드들이 있는 노드를 가지(Branch)라고 부를 수 있으며,

자식 노드가 없이 부모 노드만 있는 경우 즉, 가장 밑단에 있는 노드를 잎(Leaf)이라고 부를 수 있습니다.

그 외에도, 루트로부터 몇개의 노드(몇 대손(?) 크크...)를 타고 

자기 자신까지 올 수 있는지를 레벨이라고 표현할 수 있습니다.

만약 자신 위에 3개의 조상 노드들이 있다면 자신은 레벨 3에 있을 것이며 

자신이 잎(Leaf)이라면, 이 트리의 높이는 3이 되겠죠...

여담으로 말씀드리자면, 

숫자를 0부터 시작해야하느냐 아니면 1로 시작해야하느냐를 고민해볼 수 있습니다. 

일반적인 분야에서는 1부터 시작되지만, 

전산에서는 0을 양수로 취급하는 경우가 많아서 0부터 시작한다는...

그런 뻘소리...

아무튼...

다음으로 트리의 표현 방법에 대해서 알아보도록 하겠습니다.

루트를 기준으로 한쪽의 노드들의 수가 

반대 편 노드들보다 많거나 적어 대칭을 이루지 않는 구조의 경우

우리는 편향(사향) 트리라고 부를 수 있습니다.

만약에 이 트리에 자료를 매달 때 모든 노드들이 채워져 있는 

그런 안전한 상태의 경우 완전한 트리라고 부를 수 있습니다. 

마지막으로, 트리 높이를 구성하고 있는 각 레벨의 모든 노드들이 꽉 차있을 때에

포화 이진 트리라고 부를 수 있습니다.

자 그렇다면, 완전한 이진 트리와 포화 이진 트리의 차이점에 대해서 의문을 품을 수 있게 됩니다.

완전한 이진 트리의 경우에는, 

포화 상태는 아니지만 왼쪽부터 노드들이 차곡차곡 채워져있는 상태라고 표현할 수 있겠습니다.

 

 

어떠한 이진 논법에 의해 만들어진 트리가 있다고 생각해보도록 하겠습니다.

X라는 값을 검색해보도록 하죠...

값을 비교하기 위해서 각 레벨별로 노드를 하나씩 비교하면 됩니다.

즉, 높이가 h인 이진 탐색 트리에서 어떤 데이터를 검색하고자 할 때 비교하는 검색 횟수는

h라고 할 수 있습니다.

데이터가 별로 없을 경우에는 검색 속도에 의미가 없겠지만,

자료개수가 충분히 많다고 했을 때에 

배열, 연결 리스트와 비견되게 매우 짧은 시간안에 검색할 수 있는 장점이 있습니다.

배열, 연결 리스트의 경우 데이터가 n개가 있다면 최대 n번을 비교해야하지만,

트리의 경우에는 각 레벨별로 한번씩 비교하면 되기 때문에 보다 양이 줄게 되지요...

정리를 하자면, 이와 같이 이진 논법에 의해 자료를 매다는 트리를 이진 트리라고 합니다.

이진 트리 중에서도 검색을 목적으로 하는 트리를 이진 탐색 트리라고 하는 것이고요...

Root를 기준으로 자식 노드들이 있을 것인데, 

각 자식 노드들도 트리 구조 형태를 나타내고 있다고 한다면,

자식 트리들은 모두 서브 트리들이라고 할 수 있습니다.

즉, 트리는 루트와 서브 트리들의 집합이라고 정의할 수 있습니다.

이진 탐색 트리의 경우 각 서브트리들도 이진 탐색 트리입니다.

따라서, 트리를 통한 문제해결을 재귀적으로 하는 경우가 많이 있습니다.

자... 그렇다면 루트를 기준으로 보관되어 있는 트리들 안에 데이터를 출력해본다고 해봅시다.

해당 트리에 보관하는 모든 노드들을 순회해야 모든 데이터 출력이 가능하겠지요...

또한, 노드를 소멸할때, 데이터를 파일에 저장하고 복원할 때에도 마찬가지고요...

전체 출력을 할 때 어떠한 순서로 접근하여 출력하는 것이 좋을까요?

무작위로 출력하는 것보다는 오름차순 혹은 내림차순으로 출력하는 것이 보기에 좋지 않을까요...

자... 위의 문제를 생각해보며 이진 트리의 순회에 대해서 알아보도록 하겠습니다.

루트를 중심으로 두고 트리 순회를 하면?

왼쪽 서브 트리 -> 루트 -> 오른쪽 서브 트리와 같은 순서로 순회가 됩니다.

루트를 봤을때 중간에 있게 되죠? 따라서 중위 순회라고 부릅니다... 억지인가요... 하하하..

아무튼... InOder라고 할 수 있습니다.

이진 탐색 트리를 통해 전체 노드를 출력하고자 한다면 가장 합리적인 순회 방식이라 볼 수 있겠습니다.

전체 제거를 해본다면? root를 먼저 제거하게 되면 어떻게 될까요?

서브의 것들이 다 제거가 되고 맨 위 root가 제거 되어야 모든 것을 제거할 수 있지 않을까요?

이와 같은 경우 후위 순회 즉, PostOrder로 접근하면 좋을 것 같습니다.

그렇다면 파일에 트리 구조를 모두 순회하며 데이터를 저장한 뒤에 다시 복원하기로 해보죠...

루트를 먼저 방문하면서 파일에 들어가고

루트를 기준으로 왼쪽 노드 순회, 다음으로 오른쪽 노드 순회를 한다면?

저장과 복원을 하기 위해서 모두 먼저 루트를 방문하고 있습니다.

이를 전위 순회(PreOrder)라고 합니다.

이진 탐색 트리를 파일에 저장했다가 다시 복원하면서 노드를 매달기 위해

PreOrder로 방문을 하면서 데이터를 보관하게 되면,

나중에 로딩을 하면서 이진 탐색을 구성할 때 원래 상태를 유지할 수 있게 된다고 합니다.

자 머리가 뽀글뽀글해지죠... 하하... 다음으로, 

트리 구조로 데이터를 보관할 때 알아야할 몇가지 사항에 대해서 살펴보도록 하지요...

우선, 이진 탐색 트리에서는 같은 키 값을 가지고 있는 데이터를 보관할 수 없습니다.

배열이나 연결리스트는 중복을 허용할지 하지 않을지는 개발자가 표현했지만,

트리에서는 똑같은 키 값을 보관하지 못하도록 합니다.

왜냐하면, 이진 탐색 트리 자체가 이진 논법에 의해 매달리기 때문에

사용자에 의해 '어디에 매달라'는 명령을 내릴 수 없습니다.

즉, 무조건 매달라는 요청 밖에 할 수 없는 것이죠...

노드를 매달기 위해서 즉, 값을 집어넣기 위해서는 우선 값이 들어갈 부모를 찾아야합니다.

root가 NULL이라면? 부모가 없는 것이니 이번에 넣는 값이 root가 되겠군요...

이를 고려해서 코드를 표현할 줄 알아야합니다.

이미 Node를 추가하는 기능 외에 트리에서 제공하는 기능들은 이미 STL 에 구현되있습니다.

하지만, 논리에 대해서 알아보자면...

이진 탐색 트리에서는 왼쪽/오른쪽 어디에 매달아야하는지 결정을 하기 위해 비교를 해야합니다.

복잡하지요? 내가 어느 위치에 매달지 결정하는 것이 아닌 

지금 달 노드의 데이터 크기를 비교하여 위치가 결정 되기때문에.... 하...

아무튼... 매다는 논리는 이렇게 됩니다.

다음으로 지우는 논리에 대해서 생각해보도록 하겠습니다.

지우는 논리는... 좀... 복잡합니다...

연결리스트 때도 값을 지우기 위해서 이전 노드와 이후노드가 가리키는 링크의 위치를 변경하느라 

복잡한 과정을 거쳤었는데요....

이진 탐색 트리의 경우에는 자식이 없을 때와 자식이 있을 때 논리가 다르며 

자식이 있을 때 자식이 하나일 경우와 둘일 경우 논리가 다릅니다...

정말... 무자식이 상팔자군요... 허허...

아무튼, 살펴보도록 하겠습니다.

쉽게, 자식이 없는 노드를 지울 경우에는 그냥 부모 노드에서 자식을 지우면 됩니다.

하지만, 자식이 있을 경우 부모 노드가 손자 노드를 가리키게... 

손자 노드가 부모 노드를 가리키게 이어줘야하지요...

하지만 이게 다가 아닙니다... 만약 자식이 둘이라면 문제가 생깁니다...

삭제할 노드의 자식 노드가 둘이라면... 이진 탐색 트리의 구조에 문제가 생기게 되기 때문에

생각을 한번 해봐야합니다... 어떻게 하면 지울 수 있게 될까...

자식 노드가 둘이라면, 우선 대체할 노드를 찾아야합니다...

즉, 트리 내에 지울 노드와 비슷한 노드를 찾아야하는 것이지요...

그 다음, 대체할 노드를 찾아 지울 노드 위치에 복사를 하고 

대체할 노드의 실제 위치에 있는 노드를 제거하면 되는 것입니다... 말이 어렵군요...

대체할 노드는 자식이 없거나 한쪽에만 있어야 됩니다.

마지막으로, 이진 탐색 트리는 자기가 죽을 때 자신이 동적 할당한 메로리를 해제해줘야합니다.

트리 구조를 떠나서 모든 코드를 구현할 때에는 초기화는 반드시 잘 해주세요... 

어정쩡하면... 터집니다... 하하하...

하... 놀다 오니 뭔 x소리를 하고 있네요...

역시 글로만 내용을 표현하는데에는 분명 한계가 있습니다...

아름다운 그림들을 몇몇 삽입 해줘야하는데.... 지금 상황에서는 벅차군요 ㅠㅠ

아름답게 조금씩 시간이 날 때마다 수정을.... 하하...

아무튼..

이상 삽잡이였습니다!