본문 바로가기

(탈퇴) Reuent's Post/Algorithms

Algorithm #2. Search algorithm. - 2.4 Binary Tree Search (1).


테슬라 군이 트리 자료구조에 대한 일반적인 설명을 해 주었군요. -_-a
- Dlbo 군이 그렇게나 강조하는 테슬라 군과의 자료구조 포스팅 첫번째 연동입니다. -

트리 구조에 대한 일반론은 테슬라군이 이미 설명을 해 놓았으니 생략하겠습니다.
Binary Tree 는 트리 자료구조 중에서도 각 부모 노드가 자식 노드를 2개씩 가지는 자료구조를 말합니다.
Binary Tree Search 기법은 일반적으로 Binary Tree 의 일반적 특징을 따릅니다만,여기에 한 가지 조건이 더 붙죠.

그것은 각 노드에 저장되는 레코드의 값 순서가 ' Left < Root < Right ' 여야 한다는 것입니다.
일반적으로 Binary Tree Search 는 동적인 자료집합에 대해서 가장 효율적입니다.
값을 그냥 넣기만 하고 수정이 필요없는 경우들 - Static programming - 엔 'Linear Search' 나 'Binary Search' 가
훨씬 나은 선택이지만, 자료집합이 유동적 - 삽입, 삭제가 빈번한 경우 - 엔 Binary Tree Search를 다들 사용하는 편이죠.

자. 그럼 알고리즘 소개를 해 볼까요.
우선 Binary Tree Search 는 ' Left < Root < Right ' 의 순서로 레코드들을 조직한다는 전제를 기억해 두시기 바랍니다.


1. 최상위 루트 노드부터 검색해 들어간다.

2 - 1. 만약 찾고자 하는 값이 현재 노드의 값과 같다면 Find it.

2 - 2. 만약 찾고자 하는 값이 현재 노드의 값보다 작다면 -> Left node 순회, 다시 2 - 1 부터 재귀.
2 - 3. 만약 찾고자 하는 값이 현재 노드의 값보다 크다면 -> Right node 순회, 다시 2 - 1 부터 재귀.
         - 전제조건에서 Left < Root < Right 이므로, inorder tree walk 를 하는 편이 효율적이다. -

2 - 4. 만약 현재 노드의 값이 NULL 이라면 Can't find it.
         - 현재 탐색 위치가 Binary Tree 의 leaf, 즉 레코드의 끝이므로. -



일반적으로, Binary Tree Search 알고리즘의 수행시간은 O( log N ) 입니다. 하지만, 만약 Binary Tree가
테슬라군의 포스트처럼 사향 트리의 꼴을 취할 경우, O( N ) 의 시간이 걸립니다.
- 즉 n 개의 선형 자료 집합의 경우겠죠. -

그렇지만, 일반적으로 이런 일이 생길 경우는 드물기에 O( log N ) 의 수행 효율을 가진다고들 말하죠.
특히 Balanced Binary Tree 에 대해서는 O( 2진로그 N ) 의 효율을 자랑합니다.
이런 수치가 나타나는 이유는 Tree 의 높이에 따라서 검색 시간이 좌우되기 때문이죠.

또 하나의 보너스.

앞서 알려드렸다시피 Binary Search Tree 는 동적 연산을 지원하는 Dynamic programming 기법입니다.
이 때문에 사전이나 priority queue 의 구현에 잘 사용되기도 하죠.

이제 구현차례군요.
구현에 관련된 부분은 따로 포스트를 올려보겠습니다... 시간이 너무 오래 걸릴 것 같네요.

다음주 중에 Binary Tree Search 구현과 Red - Black Tree 에 대한 포스트가 올라갑니다.


덧*)
계속 늦어서 죄송합니다. -_-...
그리고 매번 포스트가 빈약한 것 같네요. 고쳐야 할텐데 -_-

그리고 저번 Binary Search 포스트에 대한 Dlbo 군의 태클, 잘 봤습니다.
태클을 했으니 그에 대한 증명이 있어야 겠죠? -_-a 포스트, 기대하겠습니다.