<div id="readability-page-1" class="page"><section><p>이전 포스팅에서 트리에 대해서 알아보았다. 이번에 알아볼 이진탐색트리의 정의는 다음과 같다.</p>
<h2>정의</h2>
<blockquote>
<ul>
<li>Binary Tree  </li>
</ul>
</blockquote>
<ul>
<li>Node의 key값은 <strong>왼쪽</strong> subtree <strong>보다 크고</strong> <strong>오른쪽</strong> subtree보다 <strong>작다</strong>.</li>
</ul>
<p>이진 탐색 트리는 <strong>트리</strong> 의 한 종류이며 tree의 정의를 만족해야한다. Binary Tree 즉, 이진 트리라 함은 한 부모가 최대 두개의 자식을 가질 수 있음을 의미한다.</p>
<p>위 정의를 바탕으로 이진 탐색 트리는 다음과 같은 성질을 갖는다.</p>
<ul>
<li>모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다.(모든 노드의 키값은 다르다.)</li>
<li>왼쪽 서브트리의 있는 키가 존재한다면, 키들은 그 루트의 키보다 작다.</li>
<li>오른쪽 서브트리의 있는 키가 존재한다면, 키들은 그 루트의 키보다 크다.</li>
<li>왼쪽 서브트리와 오른쪽 서브트리 모두 이진탐색트리이다.</li>
</ul>
<h2>탐색</h2>
<div data-language="text"><pre><code>root에서 시작
key값과 비교
반복 {
  찾으려는 값보다 작으면 왼쪽 child로 이동
              크면 오른쪽 child로 이동
              같으면 성공
}

만약 leaf까지 도달 할 때까지 찾지 못하면 실패</code></pre></div>
<p>이진탐색트리에서 탐색 연산의 시간복잡도는 O(h)이다. <strong>logN</strong> 이 아닌 트리의 높이임을 주의하자.</p>
<h2>삽입</h2>
<p>이진트리의 데이터 삽입은 search연산과 같이 이루어진다.</p>

<p>따라서 삽입의 시간복잡도는 O(h) + O(1)이 된다.</p>
<h2>삭제</h2>
<p>시간복잡도 O(h)</p>
<p><em>만약 중간 노드가 삭제되면 어떻게 할까?</em>
노드의 삭제가 이루어져도 트리의 정의를 항상 만족해야한다. 따라서 다음과 같은 연산을 해야한다.</p>
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Binary_search_tree_delete.svg/640px-Binary_search_tree_delete.svg.png">
<ol>
<li>삭제된 노드의 왼쪽 서브트리로 내려간다.</li>
<li>서브트리의 오른쪽 서브트리로 계속 내려간다.</li>
<li>오른쪽 서브트리가 없을경우 현재 노드를 삭제된 노드로 이동한다.</li>
<li>삭제된 노드의 왼쪽 서브트리는 삭제된 노드의 부모의 오른쪽 서브트리로 이동한다.</li>
</ol>
<p>이렇게 하면 중간의 노드가 삭제되어도 이진탐색트리의 정의를 계속 유지할 수 있다. 1, 2단계에서 왼쪽으로 한번 내려가고 오른쪽으로 계속 내려가는 이유는 <strong>삭제된 노드보다 작은것 중에 가장 큰</strong> 노드를 찾기 위함이다.<br>
만약 삭제된 노드의 왼쪽 자식이 없다면 해당 노드보다 작은 key값을 갖는 노드가 없으므로 <strong>큰 것중에 가장 key값이 가장 작은 노드</strong> 를 찾아 이동하면 된다.</p>
<h2>구현</h2>
<p>이진 탐색트리의 구현은 여러가지 방법으로 할 수 있다. LinkedList, 인접리스트, 인접행렬, 해쉬테이블 등등으로 구현할 수 있다. 가장 간단한 방법은 배열로 구현한는 방법이다.</p>
<h2>문제점</h2>
<p>데이터의 크기 순서대로 삽입연산을 수행하면 <del>linked-List</del>가 되어버린다. 따라서 탐색시간이 logN이라는 시간이 보장되지 않고 트리의 높이만큼의 시간이 보장된다.</p>
<h2>reference</h2>
<ul>
<li><a href="https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC" target="_blank" rel="noopener">위키피디아 - 이진탐색트리</a></li>
<li><a href="https://en.wikipedia.org/wiki/Binary_search_tree" target="_blank" rel="noopener">wikipedia - Binary Search Tree</a></li>
<li><a href="http://www.yes24.com/24/goods/2656393" target="_blank" rel="noopener">이석호. C++ 자료구조론 (2nd ed.). 인피니티북스.</a></li>
</ul></section></div>

Kimlog RSS Feed

KIM, WOOJUNG

이전 포스팅에서 트리에 대해서 알아보았다. 이번에 알아볼 이진탐색트리의 정의는 다음과 같다.
정의
Binary Tree  
Node의 key값은 왼쪽 subtree 보다 크고 오른쪽 subtree보다 작다.
이진 탐색 트리는 트리 의 한 종류이며 tree의 정의를 만족해야한다. Binary Tree 즉, 이진 트리라 함은 한 부모가 최대 두개의 자식을 가질 수 있음을 의미한다.
위 정의를 바탕으로 이진 탐색 트리는 다음과 같은 성질을 갖는다.
모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다.(모든 노드의 키값은 다르다.)
왼쪽 서브트리의 있는 키가 존재한다면, 키들은 그 루트의 키보다 작다.
오른쪽 서브트리의 있는 키가 존재한다면, 키들은 그 루트의 키보다 크다.
왼쪽 서브트리와 오른쪽 서브트리 모두 이진탐색트리이다.
탐색
root에서 시작
key값과 비교
반복 {
  찾으려는 값보다 작으면 왼쪽 child로 이동
              크면 오른쪽 child로 이동
              같으면 성공
}
만약 leaf까지 도달 할 때까지 찾지 못하면 실패
이진탐색트리에서 탐색 연산의 시간복잡도는 O(h)이다. logN 이 아닌 트리의 높이임을 주의하자.
삽입
이진트리의 데이터 삽입은 search연산과 같이 이루어진다.
search 실패시
  그자리에 node 생성
따라서 삽입의 시간복잡도는 O(h) + O(1)이 된다.
삭제
시간복잡도 O(h)
만약 중간 노드가 삭제되면 어떻게 할까?
노드의 삭제가 이루어져도 트리의 정의를 항상 만족해야한다. 따라서 다음과 같은 연산을 해야한다.
삭제된 노드의 왼쪽 서브트리로 내려간다.
서브트리의 오른쪽 서브트리로 계속 내려간다.
오른쪽 서브트리가 없을경우 현재 노드를 삭제된 노드로 이동한다.
삭제된 노드의 왼쪽 서브트리는 삭제된 노드의 부모의 오른쪽 서브트리로 이동한다.
이렇게 하면 중간의 노드가 삭제되어도 이진탐색트리의 정의를 계속 유지할 수 있다. 1, 2단계에서 왼쪽으로 한번 내려가고 오른쪽으로 계속 내려가는 이유는 삭제된 노드보다 작은것 중에 가장 큰 노드를 찾기 위함이다.
큰 것중에 가장 key값이 가장 작은 노드 를 찾아 이동하면 된다.
구현
이진 탐색트리의 구현은 여러가지 방법으로 할 수 있다. LinkedList, 인접리스트, 인접행렬, 해쉬테이블 등등으로 구현할 수 있다. 가장 간단한 방법은 배열로 구현한는 방법이다.
문제점
데이터의 크기 순서대로 삽입연산을 수행하면 linked-List가 되어버린다. 따라서 탐색시간이 logN이라는 시간이 보장되지 않고 트리의 높이만큼의 시간이 보장된다.
reference
위키피디아 - 이진탐색트리
wikipedia - Binary Search Tree
이석호. C++ 자료구조론 (2nd ed.). 인피니티북스.

5.Binary Search Tree에 대해서 알아보자.

댓글