데이터 구조-이진 검색 트리
이진 검색 트리 (BST)는 모든 노드가 아래에 언급 된 속성을 따르는 트리입니다.
왼쪽 하위 트리의 키 값이 부모 (루트) 노드의 키 값보다 작습니다.
오른쪽 하위 트리의 키 값이 부모 (루트) 노드의 키 값보다 크거나 같습니다.
따라서 BST는 모든 하위 트리를 두 개의 세그먼트로 나눕니다. 왼쪽 하위 트리와 오른쪽 하위 트리는 다음과 같이 정의 할 수 있습니다.
left_subtree (keys) < node (key) ≤ right_subtree (keys)
대표
BST는 BST 속성을 유지하는 방식으로 배열 된 노드 모음입니다. 각 노드에는 키와 관련 값이 있습니다. 검색하는 동안 원하는 키를 BST의 키와 비교하고 찾은 경우 관련 값을 검색합니다.
다음은 BST의 그림 표현입니다-
루트 노드 키 (27)의 왼쪽 하위 트리에는 값이 낮은 키가 모두 있고 오른쪽 하위 트리에는 값이 높은 키가 모두 있습니다.
기본 작동
다음은 트리의 기본 작업입니다-
Search − 트리에서 요소를 검색합니다.
Insert − 트리에 요소를 삽입합니다.
Pre-order Traversal − 사전 주문 방식으로 나무를 횡단합니다.
In-order Traversal − 순서대로 나무를 횡단합니다.
Post-order Traversal − 주문 후 방식으로 나무를 횡단합니다.
마디
데이터가있는 노드, 왼쪽 및 오른쪽 자식 노드에 대한 참조를 정의합니다.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
검색 작업
요소를 검색 할 때마다 루트 노드에서 검색을 시작하십시오. 그런 다음 데이터가 키 값보다 작 으면 왼쪽 하위 트리에서 요소를 검색합니다. 그렇지 않으면 오른쪽 하위 트리에서 요소를 검색합니다. 각 노드에 대해 동일한 알고리즘을 따릅니다.
연산
struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data){
if(current != NULL) {
printf("%d ",current->data);
//go to left tree
if(current->data > data){
current = current->leftChild;
} //else go to right tree
else {
current = current->rightChild;
}
//not found
if(current == NULL){
return NULL;
}
}
}
return current;
}
작업 삽입
요소를 삽입 할 때마다 먼저 적절한 위치를 찾으십시오. 루트 노드에서 검색을 시작한 다음 데이터가 키 값보다 작 으면 왼쪽 하위 트리에서 빈 위치를 검색하고 데이터를 삽입합니다. 그렇지 않으면 오른쪽 하위 트리에서 빈 위치를 검색하고 데이터를 삽입합니다.
연산
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
} //go to right of the tree
else {
current = current->rightChild;
//insert to the right
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}