the key point of searching

how to store data!!!

보간 탐색 VS 이진 탐색

두 탐색인 일단 정렬이 된 상태에서 원소를 검색을 하는 것이다.

이진 탐색 코드

이진 탐색은 중간 지점을 찾아 가지만

int BsearchRecur(int arr[], int first, int last, int target)
{
  int mid;
  
  if( first > last )
      return -1;

  mid = (first + last)/2;
  
  if(arr[mid] == target)
      return mid;
      
  else if 
      return BsearchRecur(arr, first, mid-1, target);

  else  
      return BsearchRecur(arr, mid+1, last, target);
}

보간 탐색 코드

보간탐색은 좀 정렬된 대상이 비례하는 상태였을 때 이용을 하는 것이 조금 더 효율적일 것 같다.

I think that ISearch will be much better, If array is 비례하다면

ISearch

int ISearch(int arr[], int first, int last, int target)
{

  int mid;
  
  if(arr[first] > target || arr[last] < target)
  
  
  s = ((double)(target-arr[first])/(arr[last]-arr[first])*(last -first)) + first;

 if(arr[mid] == target)
      return mid;
      
  else if 
      return ISearch(arr, first, mid-1, target);

  else  
      return ISearch(arr, mid+1, last, target);

}

이진 탐색 트리

이진 탐색 트리 = 이진 트리 + 탐색

binary search tree

process of binary search tree

binary search tree

making binary search tree

현재 구현하는 방식은 이진 트리를 만든 것을 활용하여 이진탐색 트리로 확장을 하는 것이다.

binary Search tree

source code of binary tree

트리를 탐색을 한다면 일단 기본적으로 삽입, 삭제 검색 기능 만 있으면 된다.

insert part

삽입은 더 이상 내려갈때가 없을 때까지 내려가면된다.

binary search tree

// 링크드 리스트의 확장이라고 생각을 한다면(singly linked list) 뒤로 다시 돌아가지 못하니 // 이전을 가리키는 것이 있으면 좋을 거 같다.

void BSTInsert(BTreeNode ** pRoot, BSTData data)
{
    BTreeNode * pNode = NULL;  // parent Node
    
    BTreeNode * cNode = *pRoot // current Node;
    
    BTreeNode * nNode = NULL: // new Node;  //-> 새로운 데이터를 저장을 해줘야 한다.  


   // 계속 한다는 것은 while 로 하면 좋을 듯 
   while(cNode !== NULL)
   {
        if(data == GetData(cNode))
          return; 데이터의(키의) 중복을 허용하지 않는다. 
          
        pNode = cNode;
        
        if(GetData(cNode) < data)
            cNode = GetRightSubTree(cNode);
        else
            cNode = GetLeftSubTree(cNode);
   }
   
   if(pNode != NULL)
   {
      if(GetData(pNode) < data)
            MakeRightSubTree(pNode, nNode);
      else
            MakeLeftSubTree(pNode, nNode);
   }
   else /// 새 노드가 루트 노드라면 
      *pRoot = nNode;

}

binary search tree insertion

searching part

target 데이터가 있는지 위치를 찾아서 리턴한다.

BTreeNode * BSTSearch(BTreeNode * bst, BSTData target)
{
    BTreeNode * cNode = bst; // 현재 노드
    BSTData cd;      // 현재 데이타
    
    while(cNode != NULL)
    {
        cd = GetData(cNode);
        
        if(cd == target)
          return cNode;
        else if(target < cd)
          cNode = GetLeftSubTree(cNode);
        else
          cNode = GetRightSubTree(cNode);
        
    }
    return NULL;
}

binary search tree

delete of binary search tree

this case is divided into Three.

  1. parent Node dosen’t have child node

  2. parent Node has one child node

  3. parent Node has two child node

binary search tree

binary search tree