일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 시그널
- px4
- 워게임
- 시스템프로그래밍
- pwn.college
- css
- 프로그래밍
- 시스템
- pwncollege
- 시스템해킹
- 알고리즘
- write up
- 리눅스
- 커널
- 리버싱
- wargame
- 어셈블리어
- C언어
- Bandit
- Leviathan
- 취약점
- kernel
- 드론
- 리눅스 커널
- C++
- 컴퓨터구조
- Pwnable.kr
- 리눅스커널
- 시스템 프로그래밍
- radare2
Archives
- Today
- Total
Computer Security
#3. 이진 탐색 트리 본문
반응형
이진 탐색 트리
1.이진 탐색이 항상 동작하도록 구현하여 탐색속도를 극대화 시킨 자료구조를 이진 탐색 트리라 한다.
특징:
1.이진 탐색트리에서는 항상 부모 노드가 왼쪽 자식보다는 크고, 오른쪽 자식보다는 작다.
이로인해 훨씬 더 빠르게 탐색이 가능하다.
예) 부모노드가 50이고 , 내가 찾을 숫자가 55라면, 왼쪽노드는 항상 부모노드보다 작으니,
오른쪽 노드만 탐색하면 된다.
2.이진 탐색 트리에서는 한 번 확인할 때마다 보아야 하는 원소의 개수가 절반씩 줄어든다는 점에서 '완전 이진 트리'
인 경우 탐색시간에 O(logN)의 시간 복잡도를 가진다.
이진 탐색 트리 알고리즘
찾고자하는 값이 부모노드 보다 작을경우 왼쪽 자식으로 , 찾고자하는 값이 부모노드보다 클 경우 오른쪽자식으로 뻗어 나가며, 탐색한다.
코드예시
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct { //왼쪽자식과 오른쪽자식 구조체 선언
int data;
struct Node* leftChild;
struct Node* rightChild;
}Node;
//이진 탐색 트리의 삽입
Node* insertNode(Node* root, int data) {
if (root == NULL) { //root가 NULL값이라면, 해당루트 초기화
root = (Node*)malloc(sizeof(Node));
root->leftChild = root->rightChild = NULL;
root->data = data;
return root;
}
else {
if (root->data > data) {
root->leftChild = insertNode(root->leftChild, data);
}//루트가가지고있는데이터 > 삽입할데이터 ->왼쪽노드로 간다.
else {
root->rightChild = insertNode(root->rightChild, data);
}//루트가가지고있는데이터 < 삽입할데이터 ->오른쪽노드로 간다.
}
return root;
}
//이진 탐색트리의 탐색
Node* searchNode(Node* root, int data) {
if (root == NULL) return NULL;
//만약 탐색 실패시, NULL값 반환
if (root->data == data) return root;
//특정한 데이터 찾을경우->특정데이터로 반환
else if (root->data > data) return searchNode(root->leftChild, data);
//만약 루트가 가지고있는데이터>찾고자하는데이터 -> 왼쪽자식으로 탐색한다.
else return searchNode(root->rightChild, data);
} //그렇지 않다면, 오른쪽 자식으로 탐색 수행
//이진 탐색 트리의 순회
void preorder(Node* root) {
if (root == NULL) return;
printf("%d ", root->data);
preorder(root->leftChild);
preorder(root->rightChild);
}
//이진 탐색 트리 이용해보기
int main(void) {
Node* root = NULL;
root = insertNode(root, 20);
root = insertNode(root, 5);
root = insertNode(root, 25);
root = insertNode(root, 15);
root = insertNode(root, 30);
root = insertNode(root, 40);
root = insertNode(root, 7);
preorder(root);
system("pause");
}
결과값: 20 5 15 7 25 30 40
이진 탐색트리의 삭제
1.자식이 없는 경우
단순히 그냥 제거
2.자식이 하나만 존재하는 경우
삭제할 노드의 자리에 자식노드를 넣어준다.
3.자식이 둘 다 존재하는 경우
삭제할 노드의 자리에 자기 다음으로 큰 노드를 넣는다.
코드예시
//이진 탐색 트리의 가장 작은 원소 찾기 함수
Node* findMinNode(Node* root) {
Node* node = root;
while (node->leftChild != NULL) {
node = node->leftChild;
}
return node;
}
//이진 탐색 트리의 삭제 함수
Node* deleteNode(Node* root, int data) {
Node* node = NULL;
if (root == NULL) return NULL;
//찾고자하는 노드를 찾지못하면 NULL값 반환
if (root->data > data) root->leftChild = deleteNode(root->leftChild, data);
//삭제하고자하는 노드보다 현재노드가 더 크다면, 왼쪽 탐색
else if (root->data < data) root->rightChild = deleteNode(root->rightChild, data);
//그렇지 않다면, 오른쪽 탐색
else { //삭제할 노드를 찾은경우
if (root->leftChild != NULL && root->rightChild != NULL) { //자식이 두개 전부 존재
node = findMinNode(root->rightChild);
//오른쪽자식에서 가장 작은걸 찾는것
root->data = node->data;
//가장 작은걸 삭제할 노드자리로 넣는다(오른쪽 자식중 가장작은것은 부모다음으로 큰노드)
root->rightChild = deleteNode(root->rightChild, node->data);
//바꿔치기한 노드 지우기
}
else {// 왼쪽자식이 존재한다면, 왼쪽자식을 노드에, 오른쪽자식이 존재한다면, 오른쪽자식을 노드에 담는다.
node = (root->leftChild != NULL) ? root->leftChild : root->rightChild;
free(root);
//현재 자기 자신의 노드를 할당 해제 해준다.
return node;
}
}
return root;
}
반응형
'프로그래밍 > C언어 알고리즘' 카테고리의 다른 글
#6. 프림 알고리즘 (0) | 2022.05.07 |
---|---|
#5. 해시 (0) | 2022.05.06 |
#4. AVL 트리 (0) | 2022.05.05 |
#2. 너비 우선 탐색 (0) | 2022.05.04 |
#1. 깊이 우선 탐색 (0) | 2022.05.03 |
Comments