이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리

탐색을 위한 자료구조로 저장할 데이터의 크기에 따라 위치를 정의한 것이다.

트리 자료 구조의 자료 중 하나로, 각 노드가 2개의 자식 노드를 가질 수 있는 트리이다.

※ 효율적인 탐색 작업을 하기 위해 이진 탐색 트리를 다음과 같이 정의한다.

• 모든 원소는 서로 다른 유일한 키를 갖는다.
• 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다.
• 오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 크다.
• 좌우 하위 트리도 각각 이진 탐색 트리 구조이다.

이러한 특징때문에 이진 탐색 트리를 중위 순회로 순회하게 되면, 정렬된 값을 읽을 수 있다.

이진 탐색 트리는 왜 중복노드를 가져서는 안될까?

이진 탐색 트리는 매우 직관적이고 단순한 검색 알고리즘을 가지고 있다.

이진 탐색 트리 탐색

탐색은 항상 루트 노드에서 시작한다. 먼저 키 x를 가진 노드를 검색하고자 할 때, 루트 노드와 키 값을 비교한다.

• if(x == 루트) 원하는 원소를 찾았으므로 탐색 성공
• else if(루트 > x) 루트의 왼쪽 서브트리에 대해서 탐색 연산 수행
• else if(루트 < x) 루트의 오른쪽 서브트리에 대해서 탐색 연산 수행

이진 트리 탐색 삽입

원소를 삽입하려면 먼저 이진 탐색 트리 탐색 연산을 수행해야한다.

트리를 탐색한 후, 키 값이 중복되지 않는 지 확인하고 삽입될 적절한 위치를 찾는다.

• if(탐색 성공) 이미 같은 원소가 트리 내에 있으므로 삽입 연산을 수행하지 않는다.

• else if(탐색 실패) 크기를 비교하여 찾아간 노드 위치에 원소를 삽입

이진 탐색 트리 삭제

원소를 삭제하는 경우에는 자식 노드의 수에 따라 세가지 경우의 수가 존재한다.

노드를 삭제한 후에도 이진 탐색 트리 구조를 유지해야하므로 각각의 경우에 맞는 처리가 필요하다.

1. 삭제할 노드가 단말 노드인 경우

자식 노드가 존재하지 않으므로 해당 노드를 삭제해주기만 하면 된다.

2. 삭제할 노드가 한 개의 자식 노드를 가진 경우

한개의 자식 노드를 가졌는데 노드를 제거하면 그 자식 노드는 자리를 잃어버린다.

그러므로 남겨진 자식노드를 삭제한 부모 노드의 자리로 올려주어야 한다.

3. 삭제할 노드가 두 개의 자식 노드를 가진 경우

삭제할 노드가 두 개의 자식노드를 가진 경우엔 두 개 중 어떤 노드를 대체할지 결정해야 한다.

이진 탐색 트리의 특성에 따라서 삭제할 노드의 자리에 위치할 값은 왼쪽 서브 트리의 값들 보다 커야하고,

오른쪽 서브 트리의 값들 보단 작아야한다.

그러므로 후보는 왼쪽 서브 트리에서 가장 큰 자손 노드 또는 오른쪽 서브 트리에서 가장 작은 자손노드

이렇게 두 개의 노드가 삭제할 노드의 자리에 올 수 있다.

이진 탐색 트리 구현 (Java)

https://github.com/jobcing/Algorithm/blob/master/src/imple/BinarySearchTree.java

※ 참조 : 

http://songeunjung92.tistory.com/31

https://ko.wikipedia.org/wiki/이진_탐색_트리

https://muckycode.blogspot.kr/2015/01/binary-search-treebst.html