자료구조와 알고리즘/자료구조
BST 이진 탐색트리 구현 / 수정
jaewpark
2021. 9. 14. 10:47
동작이 되지 않던 코드를 수정
- insertElementBST : 수정 전의 형태를 하게 되면 p->pLeftChild, p->pRightChild 가 가르키는 곳이 무엇인지 정해지지 않은 상태에서 element 로 할당이 되었기 때문에, 이후 삽입과정에서 element 를 찾을 수 없어서 오류가 발생하게 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
if (pBinSearchTree->pRootNode == NULL)
{
pBinSearchTree->pRootNode = element;
return TRUE;
}
while(TRUE)
{
if (p == NULL)
{
p = element;
return TRUE;
}
if (p->key > element->key)
{
p = p->pLeftChild;
}
else
{
p = p->pRightChild;
}
}
|
cs |
▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ 수정된 코드 ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
if (pBinSearchTree->pRootNode == NULL)
{
pBinSearchTree->pRootNode = element;
return TRUE;
}
while(TRUE)
{
if (p->key > element->key)
{
if (p->pLeftChild == NULL)
{
p->pLeftChild = element;
return TRUE;
}
p = p->pLeftChild;
}
else
{
if (p->pRightChild == NULL)
{
p->pRightChild = element;
return TRUE;
}
p = p->pRightChild;
}
}
|
cs |
deleteElementBST
- getParentsNode : key 값을 받는 코드였다가, DelNode 로 실행 하는 걸로 바꾸었다.
|
1
2
3
4
5
6
7
8
9
10
11
|
while(result != NULL) {
if (pDelNode == result->pLeftChild || pDelNode == result->pRightChild){
break;
}
else if (pDelNode->key < result->key) {
result = result->pLeftChild;
}
else
result = result->pRightChild;
}
|
cs |
- getpSuccessor : 트리에서 DelNode 보다 한 단계 큰 수
|
1
2
3
4
5
|
result = pDelNode->pRightChild;
while (result->pLeftChild != NULL)
{
result = result->pLeftChild;
}
|
cs |
- deleteElementBST : 삭제를 하는 부분은 아래 적힌 BST 구현을 통해 알 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
int deleteElementBST(BinSearchTree* pBinSearchTree, int key)
{
BinSearchTreeNode *pDelNode; //삭제할 노드
BinSearchTreeNode *pParentNode; //삭제할 노드의 부모녿
BinSearchTreeNode *pPredecessor; //대체노드의 부모노드
BinSearchTreeNode *pSuccessor; //대체할 노드
/*
삭제할 노드의 부모노드를 아는 방법.
삭제할 노드가 몇개의 자식노드를 가지는지 어떻게 알수있나..
*/
pDelNode = searchBST(pBinSearchTree, key);
if (pDelNode == NULL)
{
write(1, "NOT FOUND\n", 10);
return FALSE;
}
pParentNode = getParentsNode(pBinSearchTree, pDelNode);
//단말노드
if (pDelNode->pLeftChild == NULL && pDelNode->pRightChild == NULL)
{
//부모노드와 삭제할 노드의 관계를 끊어줘야한다.
if (pParentNode->pLeftChild == pDelNode)
pParentNode->pLeftChild = NULL;
else
pParentNode->pRightChild = NULL;
pDelNode = NULL;
free(pDelNode);
return TRUE;
}
//자식노드 1 개 왼쪽이 존제
else if (pDelNode->pLeftChild != NULL && pDelNode->pRightChild == NULL)
{
if (pParentNode->pLeftChild == pDelNode)
pParentNode->pLeftChild = pDelNode->pLeftChild;
else
pParentNode->pRightChild = pDelNode->pLeftChild;
pDelNode = NULL;
free(pDelNode);
return TRUE;
}
//자식노드 1 개 오른쪽 존제
else if (pDelNode->pLeftChild == NULL && pDelNode->pRightChild != NULL)
{
if (pParentNode->pLeftChild == pDelNode)
pParentNode->pLeftChild = pDelNode->pRightChild;
else
pParentNode->pRightChild = pDelNode->pRightChild;
pDelNode = NULL;
free(pDelNode);
return TRUE;
}
//자식노드 2 개
else if (pDelNode->pLeftChild != NULL && pDelNode->pRightChild != NULL)
{
pSuccessor = getpSuccessor(pDelNode);
pDelNode->key = pSuccessor->key;
pDelNode->value = pSuccessor->value;
pPredecessor = getParentsNode(pBinSearchTree, pSuccessor);
if (pSuccessor->pRightChild == NULL)
pPredecessor->pLeftChild = NULL;
else
pPredecessor->pLeftChild = pSuccessor->pRightChild;
pSuccessor = NULL;
free(pSuccessor);
}
return TRUE; //성공 1 실패 0
}
|
cs |