[자료구조]CH7. 트리(이진 탐색 트리)
참조 : C로 배우는 쉬운 자료구조(이지영 저)
공부날짜 : 2021.02.18
<Section5> 이진 탐색 트리
1. 이진 탐색 트리의 개념
이진 트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정의한 것이다. 탐색을 위해서는 찾을 자료를 식별할 수 있는 유일한 값이 필요한데, 이것을 키(key)라고 한다.
1) 모든 원소는 서로 다른 유일한 키를 갖는다.
2) 왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다.
3) 오른쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 크다.
4) 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.
2. 이진 탐색 트리의 탐색 연산
searchBST(bsT , x)
p ← bsT; //포인터 p
if (p = NULL) then
return NULL;
if (x = p.key) then
return p;
if (x < p.key) then
return searchBST(p.left , x);
else return searchBST(p.right , x);
end searchBST()
3. 이진 탐색 트리의 삽입 연산
insertBST(bsT , x)
p ← bsT; // 삽입할 자리를 찾기 위한 포인터
while (p != NULL) do {
if (x = p.key) then return;
q ← p; // 삽입할 노드의 부모 노드를 지정하기 위한 포인터
if (x < p.key) then p ← p.left;
else p ← p.right;
} // 삽입할 노드 탐색
new ← getNode();
new.key ← x;
new.left ← NULL;
new.right ← NULL; // 삽입할 노드 생성
if (bsT = NULL) then bsT ←new;
else if (x < q.key) then q.left ← new;
else q.right ← new;
return; // 삽입 노드 연결
end insertBST()
4. 이진 탐색 트리의 삭제 연산
deleteBST(bsT , x)
p ← 삭제할 노드;
parent ← 삭제할 노드의 부모 노드;
// 0. 삭제할 노드가 없는 경우
if (p = NULL) then return;
// 1. 삭제할 노드의 차수가 0인 경우
if (p.left = NULL and p.right = NULL) then {
if (parent.left = p) then parent.left ← NULL;
else parent.right ← NULL;
}
// 2. 삭제할 노드의 차수가 1인 경우
else if (p.left = NULL or p.right = NULL) then {
if (p.left != NULL) then {
if (parent.left = p) then parent.left ← p.left;
else parent.right ← p.left;
}
else {
if (parent.left = p) then parent.left ← p.right;
else parent.right ← p.right;
}
}
// 3. 삭제할 노드의 차수가 2인 경우
else if (p.left != NULL and p.right != NULL) then {
q ← maxNode(p.left); // 왼쪽 서브트리에서 후계자 노드를 포인터 q로 지정
p.key ← q.key;
deleteBST(p.left , p.key); //후계자 노드 자리에 대한 2차 재구성
}
end deleteBST()