Binary search tree

Overview

이진 탐색 트리(BST: Binary search tree) 내용 정리

Basic

BST 는 다음과 같은 속성이 있는 이진 트리 자료 구조 이다.

• 각 노드에 값이 있다.
• 각 노드의 키 값은 모두 달라야 한다.
• 값 들은 전순서(totally ordered set-toset: 임의의 두 원소를 비교할 수 있는 부분 순서 집합)가 있다.
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
• 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
• 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
• 중복된 노드가 없어야 한다.

Search

• 이진 탐색 트리에서 키 X 를 가진 노드를 검색하고자 할 때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL 을 리턴한다.
• 검색하고자 하는 값을 루트 노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다.

불일치하고 검색하고자 하는 값이 루트 노드보다 작을 경우 왼쪽 서브트리에서 재귀적으로 검색한다.

불일치하고 검색하고자 하는 값이 루트 노드보다 클 경우 오른쪽 서브트리에서 재귀적으로 검색한다.

Insert

• 삽입을 하기 전 검색을 수행한다.
• 트리를 검색한 후 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크리를 비교해서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.

Delete

삭제하려는 노드의 자식 수에 따라..

• 자식 노드가 없는 노드(리프 노드) 삭제: 해당 노드를 단순히 삭제한다.
• 자식 노드가 1개인 노드 삭제: 해당 노드를 삭제하고 그 위치에 해당 노드의 자식 노드를 대입한다.
• 자식 노드가 2개인 노드 삭제: 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰 값으로 대체하거나, 오른쪽 서브트리에서 가장 작은 값으로 대체한 뒤, 해당 노드(왼쪽 서브 트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.