C를 이용한 BST (Binary Search Tree) 와 KdTree(K Dimension Tree)

K-dtree 와 BST에 대해 알아보겠습니다!

이미 한 번 하다가 꺼졌는데,, 임시저장이 안되서 다시 처음부터 적어볼게요..흑흑

#BST

- 기본

Binary Search Tree 의 약자로 위와 같이 최대 두개의 자녀 노드를 가진 트리를 말합니다.

-성질

이때,

부모노드의

왼쪽 노드에는 부모노드보다 작은 수가    오른쪽 노드에는 부모노드보다 큰 수가

오게됩니다.

- 출력

BST의 출력을 해주는 Preorder, Inorder, Postorder의 3가지의 방식이 있습니다.

Preorder 는 부모노드가 제일 먼저 오는 것으로 부모노드 -> 왼쪽 노드 -> 오른쪽 노드의 순서로 출력합니다.

Inorder 는 부모노드가 가운데 오는 것으로 왼쪽 노드 -> 부토 노드 -> 오른쪽 노드의 순서로 출력합니다.

Postorder는 부모노드가 맨 나중에 오는 것으로 왼쪽 노드 -> 오른쪽 노드 -> 부모 노드의 순서로 출력합니다.

많이 사용하는 Inroder를 그림으로 알려드리겠습니다.

-Step 1.

왼쪽 -> 본인 -> 오른쪽 노드의 출력 순서를 갖고 있습니다.

그래서 처음 노드인 "15" 부터 시작해줍니다.

"15"에서 왼쪽 노드가 있으니 내려가 줍니다. 현재 노드는 "10"으로 바뀌게 됩니다.

현재 노드인 "10"에서 왼쪽 노드가 있으니 내려가 줍니다. 현재 노드는 "7"이 됩니다.

현재 노드인 "7"에서 왼쪽 노드가 없으니 본인을 출력해줍니다. 

-Step 2.

오른쪽 노드가 없으니 다시 위로 올라갑니다.

현재 노드인 "10"에서 출력하지 않은 왼쪽 노드가 없으니 본인을 출력합니다.

-Step 3.

오른쪽 노드가 없으니 다시 위로 올라갑니다.

현재 노드인 "15"에서 출력하지 않은 왼쪽 노드가 없으니 본인을 출력합니다.

-Step 4.

현재 노드인 "15"에서 오른쪽 노드가 존재해서 내려갑니다. 현재 노드는 "20"으로 바뀌게 됩니다.

현재 노드인 "20"에서 왼쪽 노드가 존재하니 "17"로 내려가줍니다. 현재 노드는 "17"로 바뀌게 됩니다.

현재 노드인 "17"에서 왼쪽 노드가 존재하지 않아 본인을 출력해줍니다.

-Step 5.

현재 노드인 "17"에서 위의 노드로 올라갑니다.

현재 노드인 "20"에서 출력하지 않은 왼쪽 노드가 없으므로 본인을 출력해줍니다.

-Step 6.

"20"노드에서 왼쪽 모두를 출력하고 본인까지 출력했으므로 오른쪽으로 내려가줍니다. 현재노드는 "25"입니다.

현재 노드인 "25"에서 왼쪽 노드가 없으므로 본인을 출력해줍니다.

이렇게 모든 노드가 출력을 하였습니다.

-전체 순서.

gif로 만들어 본 순서입니다. 블로그 하면 꼭 해보고 싶었는데 드디어 해보았습니당!! 빰빰 생각보다 엄청 귀찮더라구욥..

- 코드

#include<stdio.h>
#include<stdlib.h>
 
#pragma warning(disable:4996)
 
struct node {
    int number;
 
    struct node *left;// 나보다 작은 애는 왼쪽으로
    struct node *right; // 나보다 큰 애는 오른쪽으로
};
 
struct node *root = 0; // 맨 위에 있는 애
 
void addToBST(int n) // n이라는 숫자를 받아와서 n을 갖는 node를 만들고 기존에 있는 것에 넣는다.
{
    // node를 만든다.
    struct node *new_one = (struct node*)malloc(sizeof(struct node));
    //숫자를 넣는다.
    new_one->number = n;
    //오른팔과 왼팔을 null 값으로
    new_one->left = new_one->right = 0;
 
    //BST에 아무것도 없는 경우 -> root = 0
    if (root == 0) // no bst
    {
        root = new_one;
        return;
    }
    else // BST에 무언가 있을 경우
    {
        struct node *temp = root;
        while (temp != 0)
        {
            if (temp->number > n) // 왼쪽에 넣어야 함. 
            {
                if (temp->left == 0) // 아무것도 없으면 -> 그 자리는 new_one의 것
                {
                    temp->left = new_one;
                    return;
                }
                else // 무언가 있으면 -> 타고 내려가기
                    temp = temp->left;
                
            }
            else // 오른쪽에 넣어야 함.
            {
                if (temp->right == 0) // 아무것도 없으면 -> 그 자리는 new_one의 것
                {
                    temp->right = new_one;
                    return;
                }
                else // 무언가 있으면 -> 타고 내려가기
                    temp = temp->right;
            }
        }
        temp = new_one;
    }
}
 
//recurive
void inorderTraversal(struct node *_node) // 무조건 오름차순으로 나온다.
{
    // recursive 하려면 탈출 조건이 필요 ** -> 받아온 node 가 null인 경우
    if (_node == 0)
    {
        return;
    }
 
    inorderTraversal(_node->left);
    printf("%d \n", _node->number);
    inorderTraversal(_node->right);
}
 
 
int main(void)
{
    //tree build
    addToBST(100);
    addToBST(50);
    addToBST(150);
    addToBST(25);
    addToBST(75);
 
    // 함수를 다 짰으니까 잘 되었는지 확인하기
 
    //printf("%d\n", root->number);// 100이 나와야한다.
    //printf("%d\n", root->left->left->number); // 25
    // -> 잘 만든것 확인!
 
    // BST 가 제일 좋은 것인가? -> 아니다!! 왜냐하면 숫자의 들어오는 순서의 영향을 많이 받는다.
    // 그래서 어떻게 해야 좋은 tree 인가?
 
    //traversal
    inorderTraversal(root); // inorder의 경우 : 왼쪽 자신 오른쪽 출력 -> 오름차순으로 출력 가능
 
    return 0;
}

#K-d Tree

K Dimesion Tree의 뜻을 가지고 있는 이 트리는 BST와 같은 모양을 갖지만 1차원이 아닌 k차원의 Tree를 의미합니다. 

쉬운 설명을 위해 2차원의 KdTree를 설명하겠습니다.

아래와 같이 2차원의 노드들이 들어온다면 어떻게 Tree로 만들 수 있을까요?

-Step 1.

X축과 Y축 중 본인이 정한 축을 기준으로 오름차순 정렬을 해줍니다.

저는 X축 기준으로 먼저 하였습니다.

-Step 2.

정렬된 노드들에서 가운데 수를 뽑아줍니다.

이 규칙 또한 본인이 정하여 일정하게 해주면 되는데, 저는 6개 / 7개가 있다면 6÷2 / 7÷2 -> 3번째를 중간 값으로 하였습니다. (나머지는 무시해줍니다.) 

또한 인덱스를 기준으로 한 값이였기 때문에 아래와 같이 중간 값이 선정됩니다.

-Step 3.

중간값을 기준으로 왼쪽과 오른쪽 노드로 나눠줍니다. 나눠준 뒤 위에서 정렬한 기준과 반대 기준으로 오름차순 정렬해줍니다.

저는 위에서 X축을 기준으로 정렬하였기 때문에, 여기서는 Y축 기준으로 정렬해주었습니다.

-Step 4.

오른쪽, 왼쪽의 노드들에서 중간값을 뽑아줍니다.

위의 STEP 을 반복해주면 계속 나오게 되어 아래와 같은 트리가 완성됩니다.

-코드 구현

그렇다면 각각의 STEP을 어떻게 구현하면 될까요?

먼저, 아래와 같은 수를 받았을 때에는 저장을 하기 쉽도록 SLL(Single Linked List)에 넣어줍니다.

 - SLL

void addToSLL(int _x, int _y)
{
    // 데이터를 저장할 노드를 생성한다.
    struct node *new_one = (struct node *)malloc(sizeof(struct node));
    new_one->x = _x;
    new_one->y = _y;
    new_one->next = 0;
 
    // SLL에 new_one을 추가한다.
    if (head == 0)
    {
        head = new_one;
        return;
    }
    else  // SLL의 끝을 찾아서 붙여넣는다.
    {
        struct node *temp = head;
        while (1)
        {
            if (temp->next == 0)  // 맨끝을 찾은 경우
            {
                temp->next = new_one;  // 끝에 붙여넣는다.
                return;
            }
            else // 아직 맨끝 노드가 아닌 경우,
            {
                // 그 다음 노드로 이동한다.
                temp = temp->next;
            }
        }
    }
}

- SLL 포인터 배열

STEP 1에 해당하는 정렬을 위해서는 어떻게 구현하면 될까요?

정렬하기 편한것은 무엇보다 "배열"입니다.

따라서 위의 SLL각각을 가리키는 포인터를 모아두는 배열을 만들어줍니다.

// SLL에 담긴 노드의 개수를 가져온다.
    int numSLLNodes = howManyNodes(sll);
 
    // 노드 주소들을 담을 array를 할당한다.
    struct node **nodeAddrArray = (struct node **)malloc(sizeof(struct node *)*numSLLNodes);
 
    // array에 다가 노드 주소들을 하나씩 넣는다.
    int i;
    struct node *temp = sll;
    for (i = 0; i < numSLLNodes; i++)
    {
        nodeAddrArray[i] = temp;
        temp = temp->next;
    }

 - Rebuild SLL

STEP 3에서 중간 값이 정해졌을때, 왼쪽과 오른쪽으로 나눠 진행되는 것은 어떻게 구현하면 좋을까요?

왼쪽과 오른쪽 부분으로 나누어, 각각을 다시 SLL을 만들어주면 됩니다.

struct node *rebuildSLL(struct node **_array, int from, int to)
{
    if (from > to)
    {
        return 0;
    }
    struct node *cur = _array[from];
    cur->next = 0;
    struct node *temp = cur;
    for (int i = from + 1; i <= to; i++)
    {
        temp->next = _array[i];
        temp->next->next = 0;
        temp = temp->next;
    }
    return cur;
}

-제일 가까운 값 찾기

주어진 값에 가장 가까운 값을 찾기위해서는 어떻게 하면 될까요?

위의 Tree에서 (2,5)와 가장 가까운 값을 찾는 것을 예시로 진행해보겠습니다.

- 기존의 방식

이와 같은 순서를 따라 

struct kdtree_node *NaiveNearestNeighbor(struct kdtree_node *_root, int _x, int _y)
{
    int minDiff = INT_MAX;
    struct kdtree_node *minDiffNode = 0;
 
    struct kdtree_node *temp = _root;
    int axis = 0; // x축 부터 시작
    while (1)
    {
        if (temp == 0) // 탈출 조건
            return minDiffNode;
 
        // (_x,_y)와 temp 간의 거리를 구한다.
        int dist = (temp->data->x - _x) *  (temp->data->x - _x) + (temp->data->y - _y)* (temp->data->y - _y);
 
        //새로운 'Nearest Neighbor'를 발견햇음
        if (dist < minDiff)
        {
            minDiff = dist;
            minDiffNode = temp;
        }
 
        //struct kdtree_node *whichWayToGo(temp, _x, _y, axis) 
        temp = whichWayToGo(temp, _x, _y, axis); // 다음 temp 위치를 찾아낸다.
 
        // 다음 비교를 위해 axis 증가
        axis = (axis + 1) % 2;
    }
}
 

(4,7)의 결과를 갖게됩니다. 이것이 과연 맞는 결과일까요?

- 결과 확인

먼저, Tree를 2차원 그래프에 그리면 아래와 같이 그릴 수 있습니다.

여기에 (2,3)을 추가하여 거리를 계산해 보겠습니다.

아래 사진에서 눈으로도 볼 수 있듯 (2,3)의 거리가 더 가까운 것을 알 수 있습니다.

그렇다면 이와 같은 결과를 얻기 위해서는 어떻게 하면 좋을까요?

- 진짜 방식

위와 같이 제일 가까운 거리의 노드를 찾아낸 뒤, 그 거리를 반지름으로 하는 원 안에 다른 노드가 있는지 확인을 해봅니다.

만약 그 원안에 해당하는 노드가 있다면, 즉 내가 알고있는 최소 거리가 경계선을 넘어가면 그 경계선을 넘어가는 수를 한 번더 비교해주면 됩니다.

struct kdtree_node *RealNearestNeighbor(struct kdtree_node *_root, 
                                        int _x, int _y,
                                        int _minDiff,
                                    struct kdtree_node * _minDiffNode, int axis, int dim)
{
    //탈출조건
    if (_root == 0)
        return _minDiffNode;
 
    
    //가장 ㅍㅓ펙트
    if (_root->data->x == _x && _root->data->y == _y)
        return _root;
 
    else
    {
        //얼마나 멀리 떨어져있는지 계산
        // _root와의 거리 계산
 
        int dist = (_root->data->x - _x) *  (_root->data->x - _x) + (_root->data->y - _y)* (_root->data->y - _y);
 
        if (dist < _minDiff)
        {
            _minDiff = dist;
            _minDiffNode = _root;
        }
 
        //이제 root를 떠나, 왼쪽이든, 오른쪽이든 내려간다.
        struct kdtree_node *wayTo = whichWayToGo(_root, _x, _y, axis%dim);
 
        struct kdtree_node *NN
            = RealNearestNeighbor(wayTo, _x, _y, _minDiff, _minDiffNode, axis + 1, dim);
 
        //결정된 nearest neighbor까지의 거리를 구다.
        int dist_to_NN = (NN->data->x - _x)*(NN->data->x - _x) + (NN->data->y - _y)*(NN->data->y - _y);
 
        //nearest neighbor까지의 거리가 경계선을 넘는지 본다.
        if (axis%2 == 0) // x축에 대하여 검사
        {
            if (dist_to_NN > (_x - _root->data->x)*(_x - _root->data->x))
            {
                //경계선 저쪽을 뒤져봐야된다.
                return RealNearestNeighbor(whichWayNotToGo(_root, _x, _y, axis%dim),
                    _x, _y, _minDiff, _minDiffNode, axis + 1, dim);
            }
            else
                return NN;
        }
        else // y축에 대해서 검사
        {
            if (dist_to_NN > (_y - _root->data->y)*(_x - _root->data->x))
            {
                //경계선 저쪽을 뒤져봐야된다.
                return RealNearestNeighbor(whichWayNotToGo(_root, _x, _y, axis%dim),
                    _x, _y, _minDiff, _minDiffNode, axis + 1, dim);
            }
            else
                return NN;
        }
    }
}

- 최종 코드

https://github.com/leehy0321/algorithm_study/blob/master/Class/0917_kdtree_search.cpp

#include <stdio.h>
#include <stdlib.h>
 
struct node
{
    int x;
    int y;
    struct node *next;
};
 
struct node *head = 0;
 
// kd-tree의 root를 가리키는 root pointer
struct kdtree_node *kd_root = 0;
 
// kd-tree의 노드 구조체를 정의
struct kdtree_node
{
    struct node *data;
    struct kdtree_node *left;
    struct kdtree_node *right;
};
 
// linked list에 노드가 몇 개 있는지를 세는 함수
int howManyNodes(struct node *_head)
{
    int cnt = 0;
    struct node *temp = _head;
 
    while (1)
    {
        if (temp == 0)
        {
            return cnt;
        }
        else
        {
            cnt++;
            temp = temp->next;
        }
    }
}
 
//
// array에 담긴 주소들을 x 혹은 y값에 따라 오름차순으로 정렬
//
// _byX = 1: x에 대해서 소팅
//      = 0: y에 대해서 소팅
// _size: array의 길이
void doBubbleSort(struct node **_array, int _byX, int _size)
{
    int i = 0;
    int j = 0;
 
    for (j = 0; j < _size; j++)
    {
        for (i = 0; i < _size - 1 - j; i++)  // (0,1) (1,2), ......
        {
            if (_byX == 1)  // x에 대해서 비교
            {
                if (_array[i]->x > _array[i + 1]->x)
                {
                    // swap
                    struct node *temp = _array[i];
                    _array[i] = _array[i + 1];
                    _array[i + 1] = temp;
                }
            }
            else            // y에 대해서 비교
            {
                if (_array[i]->y > _array[i + 1]->y)
                {
                    // swap
                    struct node *temp = _array[i];
                    _array[i] = _array[i + 1];
                    _array[i + 1] = temp;
                }
            }
        }
    }
}
 
struct node *rebuildSLL(struct node **_array, int from, int to)
{
    if (from > to)
    {
        return 0;
    }
    struct node *cur = _array[from];
    cur->next = 0;
    struct node *temp = cur;
    for (int i = from + 1; i <= to; i++)
    {
        temp->next = _array[i];
        temp->next->next = 0;
        temp = temp->next;
    }
    return cur;
}
 
// kdtree를 생성해내는 함수
// 반환: 생성된 kdtree node의 주소를 반환한다.
// 입력: kdtree에 들어갈 linked list
//       depth정보: x축 혹은 y축에 대해서 비교할 정보,,,
//       dimension: 데이터의 차원, 2차원 점의 경우 2
struct kdtree_node *build_kdtree(struct node *sll,
    int _depth,
    int _dimension)
{
    if (sll == 0)
    {
        return 0;
    }
    // 1. SLL 노드들의 주소를 array에 저장한다.
 
    // SLL에 담긴 노드의 개수를 가져온다.
    int numSLLNodes = howManyNodes(sll);
 
    // 노드 주소들을 담을 array를 할당한다.
    struct node **nodeAddrArray = (struct node **)malloc(sizeof(struct node *)*numSLLNodes);
 
    // array에 다가 노드 주소들을 하나씩 넣는다.
    int i;
    struct node *temp = sll;
    for (i = 0; i < numSLLNodes; i++)
    {
        nodeAddrArray[i] = temp;
        temp = temp->next;
    }
 
    // 검증
    // nodeAddrArray를 이용해서 SLL 노드들의 값을 모두 출력
    //for (i = 0; i < numSLLNodes; i++)
    //{
    //    int _x = nodeAddrArray[i]->x;
    //    int _y = nodeAddrArray[i]->y;
    //    printf("%d, %d\n", _x, _y);
    //}
 
    // x축 혹은 y축에 대해서 소팅하는지 결정
    int axis = _depth % _dimension;
 
    doBubbleSort(nodeAddrArray, !axis, numSLLNodes);
 
    int _median = numSLLNodes / 2;
 
    struct kdtree_node *cur = (struct kdtree_node *)malloc(sizeof(struct kdtree_node));
    cur->data = nodeAddrArray[_median];
    cur->left = build_kdtree(rebuildSLL(nodeAddrArray, 0, _median - 1), _depth + 1, 2);
    cur->right = build_kdtree(rebuildSLL(nodeAddrArray, _median + 1, numSLLNodes - 1), _depth + 1, 2);
    free(nodeAddrArray);
 
    return cur;
 
}
 
//return 1 if (1,4) is in kd-tree
//         0 if not
int searchKdTree(struct kdtree_node *_root, int _x, int _y)
{
    struct kdtree_node *temp = _root;
    int axis = 0;
 
    while (1)
    {
        if (temp == 0) // (_x,_y)를 찾지 못했음.
            return 0;
 
        // 내가 찾고자 하는 값인지 비교
        if (temp->data->x == _x && temp->data->y == _y)
            return 1;
 
        if (axis == 0) // compare x coordinates
        {
            if (temp->data->x > _x)
                temp = temp->left;
            else
                temp = temp->right;
        }
        else // axis =1 -> compare y coordinates
        {
            if (temp->data->y > _y)
                temp = temp->left;
            else
                temp = temp->right;
        }
 
        axis = (axis + 1) % 2;//axis 바꿔주기
    }
}
 
 
void addToSLL(int _x, int _y)
{
    // 데이터를 저장할 노드를 생성한다.
    struct node *new_one = (struct node *)malloc(sizeof(struct node));
    new_one->x = _x;
    new_one->y = _y;
    new_one->next = 0;
 
    // SLL에 new_one을 추가한다.
    if (head == 0)
    {
        head = new_one;
        return;
    }
    else  // SLL의 끝을 찾아서 붙여넣는다.
    {
        struct node *temp = head;
        while (1)
        {
            if (temp->next == 0)  // 맨끝을 찾은 경우
            {
                temp->next = new_one;  // 끝에 붙여넣는다.
                return;
            }
            else // 아직 맨끝 노드가 아닌 경우,
            {
                // 그 다음 노드로 이동한다.
                temp = temp->next;
            }
        }
    }
}
 
//(_x, _y)가 주어졌을때,
//axis를 고려하여
//_root의 left혹은 right로 내려갈지를 반환
struct kdtree_node *whichWayToGo(struct kdtree_node *_root, int _x,int  _y, int axis)
{
    if (axis == 0)// x축 비교
    {
        if (_root->data->x > _x)
            return _root->left;
        else
            return _root->right;
    }
    else // y축 비교
    {
        if (_root->data->y > _y)
            return _root->left;
        else
            return _root->right;
    }
}
 
//_root의 left혹은 right로 내려갈지를 반환
struct kdtree_node *whichWayNotToGo(struct kdtree_node *_root, int _x, int  _y, int axis)
{
    if (axis == 0)// x축 비교
    {
        if (_root->data->x > _x)
            return _root->right;
        else
            return _root->left;
    }
    else // y축 비교
    {
        if (_root->data->y > _y)
            return _root->right;
        else
            return _root->left;
    }
}
 
struct kdtree_node *RealNearestNeighbor(struct kdtree_node *_root, 
                                        int _x, int _y,
                                        int _minDiff,
                                    struct kdtree_node * _minDiffNode, int axis, int dim)
{
    //탈출조건
    if (_root == 0)
        return _minDiffNode;
 
    
    //가장 ㅍㅓ펙트
    if (_root->data->x == _x && _root->data->y == _y)
        return _root;
 
    else
    {
        //얼마나 멀리 떨어져있는지 계산
        // _root와의 거리 계산
 
        int dist = (_root->data->x - _x) *  (_root->data->x - _x) + (_root->data->y - _y)* (_root->data->y - _y);
 
        if (dist < _minDiff)
        {
            _minDiff = dist;
            _minDiffNode = _root;
        }
 
        //이제 root를 떠나, 왼쪽이든, 오른쪽이든 내려간다.
        struct kdtree_node *wayTo = whichWayToGo(_root, _x, _y, axis%dim);
 
        struct kdtree_node *NN
            = RealNearestNeighbor(wayTo, _x, _y, _minDiff, _minDiffNode, axis + 1, dim);
 
        //결정된 nearest neighbor까지의 거리를 구다.
        int dist_to_NN = (NN->data->x - _x)*(NN->data->x - _x) + (NN->data->y - _y)*(NN->data->y - _y);
 
        //nearest neighbor까지의 거리가 경계선을 넘는지 본다.
        if (axis%2 == 0) // x축에 대하여 검사
        {
            if (dist_to_NN > (_x - _root->data->x)*(_x - _root->data->x))
            {
                //경계선 저쪽을 뒤져봐야된다.
                return RealNearestNeighbor(whichWayNotToGo(_root, _x, _y, axis%dim),
                    _x, _y, _minDiff, _minDiffNode, axis + 1, dim);
            }
            else
                return NN;
        }
        else // y축에 대해서 검사
        {
            if (dist_to_NN > (_y - _root->data->y)*(_x - _root->data->x))
            {
                //경계선 저쪽을 뒤져봐야된다.
                return RealNearestNeighbor(whichWayNotToGo(_root, _x, _y, axis%dim),
                    _x, _y, _minDiff, _minDiffNode, axis + 1, dim);
            }
            else
                return NN;
        }
    }
}
struct kdtree_node *NaiveNearestNeighbor(struct kdtree_node *_root, int _x, int _y)
{
    int minDiff = INT_MAX;
    struct kdtree_node *minDiffNode = 0;
 
    struct kdtree_node *temp = _root;
    int axis = 0; // x축 부터 시작
    while (1)
    {
        if (temp == 0) // 탈출 조건
            return minDiffNode;
 
        // (_x,_y)와 temp 간의 거리를 구한다.
        int dist = (temp->data->x - _x) *  (temp->data->x - _x) + (temp->data->y - _y)* (temp->data->y - _y);
 
        //새로운 'Nearest Neighbor'를 발견햇음
        if (dist < minDiff)
        {
            minDiff = dist;
            minDiffNode = temp;
        }
 
        //struct kdtree_node *whichWayToGo(temp, _x, _y, axis) 
        temp = whichWayToGo(temp, _x, _y, axis); // 다음 temp 위치를 찾아낸다.
 
        // 다음 비교를 위해 axis 증가
        axis = (axis + 1) % 2;
    }
}
 
int main(void)
{
    /*addToSLL(2, 3);
    addToSLL(5, 4);
    addToSLL(9, 6);
    addToSLL(4, 7);
    addToSLL(8, 1);
    addToSLL(7, 2);*/
 
    addToSLL(5, 1);
    addToSLL(6, 9);
    addToSLL(1, 1);
    addToSLL(2, 3);
    addToSLL(1, 5);
    addToSLL(4, 6);
    addToSLL(7, 10);
    addToSLL(3, 7);
 
    int num = howManyNodes(head);
    printf("num of SLL nodes: %d\n", num);
 
 
    kd_root = build_kdtree(head, 0, 2);
 
    //printf("(%d,%d)\n", kd_root->data->x, kd_root->data->y);
    //printf("(%d,%d)\n", kd_root->left->data->x, kd_root->left->data->y);
    //printf("(%d,%d)\n", kd_root->right->data->x, kd_root->right->data->y);
    //printf("(%d,%d)\n", kd_root->left->left->data->x, kd_root->left->left->data->y);
 
    //return 1 if (1,4) is in kd-tree
    //         0 if not
    //int result = searchKdTree(kd_root, 1, 4);
    //printf("%d\n", result);
 
    // (2,5)와 가까운 점을 찾기 위해서,
    // 순진한 방법으로 kd_tree를 타고 내려가면서,
    // 가장 가까운 점을 찾아서 그 포인터를 반환한다.
    // 마치 BST를 타고 내려가듯이 내려간다.
    struct kdtree_node *p = NaiveNearestNeighbor(kd_root, 5, 3); // 결과값은 아마도 (4,7)
    printf("%d , %d \n", p->data->x, p->data->y);
    
    struct kdtree_node *realP = RealNearestNeighbor(kd_root, 5, 3, INT_MAX, 0, 0, 2);
 
    printf("Rael Nearest is %d, %d\n", realP->data->x, realP->data->y); // 결과는 (2,3)
    return 0;
}