BST
1. 여러개의 키(key)를 저장
2. insert, search, delete 연산을 지원하는 자료구조
3. node와 branch를 이용하여, 사이클이 이루어지지않도록 구성한 자료구조.트리의 구조
- 트리: node와 branch를 이용해서 사이클을 이루지않도록 구성한 데이터구조
- BST는, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
용어
- node: 트리에서 데이터를 저장하는 기본요소
- Root node: 최상단의 위치한 노드
- level : 최상위노드를 level 0으로 하였을때, 하위 branch로 연결된 노드이 깊이를 나타낸다.
- Parent, child노드 : 어떤노드의 상위, 하위노드
- leaf node (terminal node): child(하위)노드가 하나도 없는 노드
- sibling : 동일한 상위 부모노드를 가진 노드
- Depth: 트리에서 노드가 가질수있는 최대의 level
Search
시간복잡도: O(h)
h는 트리의 높이를 뜻함
// version 1
Tree-Search(x, k) // x == 트리노드, k == 찾는값
{
// CASE1 : x가 널값이거나, x의 값이 k일때
if (x == NULL || k = key[x])
return x;
// CASE2 : CASE1이 아닐경우, 왼쪽이나, 오른쪽의 서브트리로 내려감
if (k < key[x])
return Tree-Search(left[x], k);
else
return Tree-Search(right[x], k);
}
// version 2
Tree-Search(x, k)
{
while (x != NULL && k != key[x])
{
if (x < key[x])
x = left[x];
else
x = right[x];
}
return x;
}
Minimun
최소값은 항상 가장 왼쪽 노드 끝에 존재
시간복잡도: O(h)
Tree-Minimun(x)
{
while (left[x])
x = left[x];
return x;
}
Successor
나보다 크면서 가장작은값: 바로 위의 값CASE1 : 오른쪽 부트리가 존재할 경우, 오른쪽 부트리에서의 최소값
CASE2 : 오른쪽 부트리가 존재하지 않을경우, 부모를 따라 루트까지 올라가면서, 처음으로
누군가의 왼쪽자식이 되는경우.
CASE3 : CASE2에서 그런 노드가존재하지않는다면, 본인노드가 최대값이다. successor는 없다.
Tree-Succesor(x)
{
// CASE1
if (right[x])
return Tree-Minimum(x);
// CASE2, CASE3
y = parent[x];
while (y && x = right[y]) // x가 부모의 오른쪽자식인동안
{
x = y;
y = parent[y];
}
return y;
}
Predecessor
본인노드보다 가장 작으면서 큰 키를 가진 노드 (successor와 반대)
successor와 같다. right를 left로 바꿔주면끝.
Tree-Predecessor(x)
{
// CASE1
if (left[x])
return Tree-Minimum(x);
// CASE2, CASE3
y = parent[x];
while (y && x = left[y]) // x가 부모의 오른쪽자식인동안
{
x = y;
y = parent[y];
}
return y;
}
Insert
기존의 노드를 변경하지않고, 추가만한다.
Tree-Insert(T, z)
{
y = NULL; // 루트부터 시작하는 x를 따라오는 노드.
// z의 자리를 찾기위해서, search를 하는동안,
// x는 NULL이 되므로, y가 필요.
x = root[T];
while (x)
{
y = x;
if (key[z] < key[x])
x = left[x];
else
x = right[x];
}
parent[z] = x;
if (y == NULL)
root[T] = z;
else if (key[z] < key[y])
left[y] = z;
else
right[y] = z;
}
Delete
시간복잡도: O(h)
Search를 하여, 삭제할 노드를찾은후에 삭제.
즉, Search를 포함한다.CASE1 : 자식노드가 없는경우
부모노드의 자식노드를 NULL값으로 바꾸면 끝
CASE2 : 자식노드가 1개인 경우
나의 자식노드를 부모노드와 연결해주면된다.
CASE3 : 자식노드가 2개인 경우
삭제하려는 노드의 데이터를 노드의 successor의 데이터를 카피한다.
(자식이 2개인경우이므로, 무조건 successor가 존재한다.)
그후에, successor를 CASE1 또는 CASE2를 이용하여 노드를 정리한다.
(successor노드는 왼쪽노드가없으므로, CASE1이나 CASE2의 경우중 하나이다.)
Tree-Delete(T, z)
{
// y : 실제로 삭제할 노드
if (left[z] == NULL || right[z] == NULL) // CASE1, CASE2
y = z;
else // CASE3
y = Tress-Successor(z);
// left가 NULL이 아니라는말은, CASE2에 해당.
// successor는 왼쪽자식이없다.
// 노드 y를 삭제, 자식이 0개거나 1개일경우
// x : 삭제할 노드의 자식노드
if (left[y] != NULL)
x = left[y];
else
x = right[y];
// y(삭제할 노드)의 자식노드의 부모가된다.
if (x != NULL)
parent[x] = parent[y];
// 삭제할 노드의 부모노드가 존재하지않는다면, 그 노드는 루트노드.
if (parent[y] == NULL)
root[T] = x;
else if (y == left[ parent[y] ]) // 부모노드와 자식노드를 연결
left[ parent[y] ] = x;
else
right[ parent[y] ] = x;
// CASE3
if (y != x)
key[z] = key[y];
return y;
}
etudiant_42