데이터 구조-이진 검색 트리

이진 검색 트리 (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;
            }
         }
      }            
   }
}