2억개 랜덤수중에서 특정값찾는거인데 퀵소트로는 안됐음... 라이브러리도 쓰지말라고해서 자바컬렉션 multi hashmap 구현함 근데 이것도 힙사이즈 터질수있어서 분할해서 값넣어줘야함 사이즈가 몇인지는 모르겠는데 암튼 안터지는값으로 잘 쪼개서 넣고 분할탐색하면됨



#pragma once
#include "bTree.h"

class HashMap
{
private:
    int size;
    BTree* hm;
public:
    HashMap(int s);
    ~HashMap();
    BNode* Get(int key);
    void Set(int key);
};

#include "hashMap.h"
#include <iostream>

using namespace std;



HashMap::HashMap(int s)
{
    size = s;
    hm = new BTree[size];
}
HashMap::~HashMap()
{
    delete[] hm;
}
BNode* HashMap::Get(int key)
{
    int index = key % (size - 1);
    return hm[index].Search(key);
}
void HashMap::Set(int key)
{
    int index = key % (size - 1);
    BNode* item = new BNode();
    item->key = key;
    hm[index].Insert_Node(item);
}


///////////////////////////////////////////////////////////////////////////////////////// 바이너리트리 헤더


class BNode
{
public:
    BNode* parent;
    BNode* left;
    BNode* right;

    int key;
    BNode();
};

class BTree
{
private:
    BNode* root;
public:
    BTree();
    ~BTree();
    BNode* Create_Node(int key);
    BNode* Search(int key);
    BNode* Get_Root(){ return root; }
    void Insert_Node(BNode* item);
    void Inorder_Print(BNode* n);
    void Destroy_Tree(BNode* cur);
};


#include "bTree.h"
#include <iostream>
using namespace std;

BNode::BNode(){
    left = NULL;
    right = NULL;
    parent = NULL;
    key = 0;

}


BTree::BTree()
{
    root = NULL;
}
BTree::~BTree()
{
    Destroy_Tree(root);
}

void BTree::Destroy_Tree(BNode* cur)
{

    if (cur->left != NULL)
        Destroy_Tree(cur->left);
    if (cur->right != NULL)
        Destroy_Tree(cur->right);

    cur->left = NULL;
    cur->right = NULL;
    delete cur;

}
BNode* BTree::Create_Node(int key)
{
    BNode* node = new BNode();
    node->key = key;
    return node;
}
BNode* BTree::Search(int key)
{
    BNode* t = root;
    while (t != NULL){
        if (t->key == key)
            return t;
        else if (t->key < key)
            t = t->right;
        else
            t = t->left;
    }
    return NULL;
}

void BTree::Insert_Node(BNode* item)
{
    if (root == NULL)
    {
        root = item;
        return;
    }
       
    BNode* t = root;
    while (1){
        if (t == NULL){
            t = item;
            break;
        }           
        else if (t->key == item->key)
            break;
        else if (t->key < item->key)
        {
            if (t->right == NULL){
                t->right = item;
                return;
            }                 
            t = t->right;

        }
        else{
                if (t->left == NULL){
                    t->left = item;
                    return;
                }
                t = t->left;
        }   
    }
}
void BTree::Inorder_Print(BNode* n)
{
    if (n == NULL)
        return;
    cout << n->key << " ";
    Inorder_Print(n->left);
    Inorder_Print(n->right);
}