February 11, 2020SujinLee

Data Structure - Tree (Concept and C++ code)

트리 구조

트리 : Node 와 Edge (branch) 를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
tree는 계층적 자료구조(hierarchical structure)
stack, queue, list 의 자료구조는 선형자료구조(Linear data structure)

주요 용도
- 트리 중 이진 트리 형태의 구조로, 탐색(검색)알고리즘 구현을 위해 많이 사용됨

Term

Node : 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 edge 정보 포함)
Edge (branch) - 간선 : 노드들 간의 연결 선
Root Node : 트리 맨 위에 있는 노드
Parent node : 노드의 상위레벨에 연결된 노드
Child node : 노드의 다음 레벨에 연결된 노드
Terminal node (Leaf node) : Child node가 하나도 없는 노드
Sibling : 동일한 Parent node를 가진 노드
Level : 트리에서 각 층의 번호를 매기는 것 - 루트의 레벨은 1, 한 층씩 내려갈 수록 1씩 증가
Depth : 트리에서 node가 가질 수 있는 최대 level
Degree - 차수 : 노드가 가지고 있는 자식노드의 개수

이진트리와 이진 탐색트리

이진트리 (Binary Tree) : 노드의 최대 edge 가 2인 트리

이진 탐색 트리 ( Binary Search Tree) - BST : 이진 트리에 다음과 같은 추가 조건이 있는 트리
왼쪽 노드는 해당 노드보다 작은 값, 오른쪽노드는 해당 노드보다 큰 값을 가지고 있음

이진 탐색 트리의 장점
- 탐색 속도를 개선할 수 있음
- 빠른 검색이 가능
  - 배열 탐색시간 - O(n)
  - 트리 탐색시간 - O(log n)
이진 탐색 트리의 주요 용도
- 데이터 검색(탐색)
이진 탐색 트리의 시간 복잡도
- O(log n)
  - 빅오 표기법에서 log n 의 밑은 10이 아니라 2
  - 한 번 실행시마다, 50%의 실행할 수도 있는 탐색경우의 수를 제거한다는 의미
  - 50%의 실행시간을 단축
- log n의 시간 복잡도에 대한 증명
  1. n 의 크기를 반씩 줄이는 걸 가정
    n 이 반씩 줄다보면 k 단계에서 최종적으로 1이 된다 가정하자.
  2. 단계별로 n -> n/2 -> n/4 -> n/2의k 승 진행
  3. n = 2 의 k 승
  4. 양쪽에 로그 붙이면 logN = k 가 됨.
이진 탐색 트리의 단점
- 평균 시간 복잡도는 O(log n)이지만, 이는 트리가 균형이 잡혀있을 때의 평균시간 복잡도
- 최악의 경우는 링크드 리스트와 동일한 성능을 보여줌 O(n)
  quora.com - worst case time complexity

C++ code

노드 클래스 만들기 - 링크드 리트스 활용
이진 탐색 트리 - Insert Data
이진 탐색 트리 - Search
이진 탐색 트리 - Delete
tree 참고 c++ code

tree_code

struct treeNode
{
	int data;
	treeNode *right, *left;	
};

트리에서 데이터와 브랜치(edge) 값을 관리하기 위해서는 트리 자료구조를 구현할때 링크드 리스트를 활용하는 것을 권장

insert_data_in_tree

void TreeNodeMgmt::insert_node(int value)
{
	TreeNode * binary_tn = new TreeNode;
	TreeNode * parent;
	binary_tn->data = value;
	binary_tn->lChild = nullptr;
	binary_tn->rChild = nullptr;
	
	if(root == nullptr)
	{
		root = binary_tn;
	}
	else
	{
		TreeNode * ptr;
		ptr = root;
		while(ptr != nullptr)
		{
			parent = ptr;
			if(value > ptr->data)
				ptr = ptr->rChild;
			else
				ptr = ptr->lChild;
		}
		if(value > parent -> data)
			parent->rChild = binary_tn;
		else
			parent->lChild = binary_tn;
	}
	
}

search_tree

bool TreeNodeMgmt::search_node(int value)
{
	return searchBinTree(root, value);
}
bool TreeNodeMgmt::searchBinTree(TreeNode * ptr, int value)
{
	TreeNode * tn = ptr;
	while(tn != nullptr)
	{
		if(value == tn->data)
			return true;
		else
		{
			if(value > tn->data)
				tn = tn->rChild;
			else
				tn = tn->lChild;
		}	
	}
	return false;
}

delete_data_in_tree

이진 탐색 트리 삭제

삭제할 노드가 없는 경우 false를 return 하고 함수 종료

Case 1. Leaf Node 삭제

삭제할 node의 parent node가 삭제할 node를 가리키지 않도록함
parent node의 edge에 nullptr 대입

void TreeNodeMgmt::deleteBinTree(TreeNode *ptr, int value)
{
	if(!searchBinTree(ptr, value))
		return;
	
	TreeNode * parent;
	TreeNode * tn = ptr;
	
	while(tn != nullptr)
	{
		if(value == tn->data)
			break;
		else
		{
			parent = tn;
			if(value > tn->data)
				tn = tn->rChild;
			else
				tn = tn->lChild;
		}
	}
	
	//Case1. Leaf Node deletion
	if(tn->rChild == nullptr && tn->lChild == nullptr)
	{
		if(value < parent->data)
			parent->lChild = nullptr;
		else
			parent->rChild = nullptr;
		delete tn;	
	}
}

Case 2. Child Node가 하나인 Node 삭제

삭제할 노드의 parent node가 삭제할 노드의 child node를 가리키도록 함

//Case2. One Degree Node deletion	
if(tn->rChild == nullptr && tn->lChild != nullptr)
{
	if(value < parent->data)
		parent->lChild = tn->lChild;
	else
		parent->rChild = tn->lChild;
	delete tn;
	return;
}
else if(tn->rChild != nullptr && tn->lChild == nullptr)
{
	if(value < parent->data)
		parent->lChild = tn->rChild;
	else
		parent->rChild = tn->rChild;
	delete tn;
	return;
}

Case 3. Child Node가 두 개인 Node 삭제

option1 - Rightmost. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 함

option2 - Leftmost. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 함

Case 3-1. 삭제할 Node가 Parent Node의 왼쪽에 있을 때
- Case 3-1-1. 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
- Case 3-1-2. 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
Case 3-2. 삭제할 Node가 Parent Node의 오른쪽에 있을 때
- Case 3-2-1. 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
- Case 3-2-2. 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때

//Case3. Two Degree Node deletion
if(tn->rChild != nullptr && tn->lChild != nullptr)
{
	if(value < parent->data) //Case 3-1
	{	
		TreeNode * changeNode = tn->rChild;
		TreeNode * changeNodeParent;
		while(changeNode->lChild != nullptr)
		{
			changeNodeParent = changeNode;
			changeNode = changeNode->lChild;
		}
		
		if(changeNode->rChild != nullptr)
			changeNodeParent->lChild = changeNode->rChild;
		else
			changeNodeParent->lChild = nullptr;
		parent->lChild = changeNode;
		changeNode->rChild = tn->rChild;
		changeNode->lChild = tn->lChild;
		
		delete tn;
		return;
	}
	else //Case 3-2 
	{
		TreeNode * changeNode = tn->rChild;
		TreeNode * changeNodeParent;
		while(changeNode->lChild != nullptr)
		{
			changeNodeParent = changeNode;
			changeNode = changeNode->lChild;
		}
		
		if(changeNode->rChild != nullptr)
			changeNodeParent->lChild = changeNode->rChild;
		else
			changeNodeParent->lChild = nullptr;
		parent->rChild = changeNode;
		changeNode->rChild = tn->rChild;
		changeNode->lChild = tn->lChild;
		
		delete tn;
		return;
	}	
}

C++ 전체 코드

#include <iostream>

using namespace std;
struct TreeNode
{
	int data;
	TreeNode *lChild, *rChild;
};

class TreeNodeMgmt
{
private:
	TreeNode * root;
public:
	TreeNodeMgmt()
	{
		root = nullptr;
	}
	void insert_node(int value);
	void displayBST();
	void printBinTree(TreeNode * ptr);
	bool search_node(int value);
	bool searchBinTree(TreeNode * ptr, int value);
	void delete_node(int value);
	void deleteBinTree(TreeNode * ptr, int value);
};

void TreeNodeMgmt::insert_node(int value)
{
	TreeNode * binary_tn = new TreeNode;
	TreeNode * parent;
	binary_tn->data = value;
	binary_tn->lChild = nullptr;
	binary_tn->rChild = nullptr;
	
	if(root == nullptr)
	{
		root = binary_tn;
	}
	else
	{
		TreeNode * ptr;
		ptr = root;
		while(ptr != nullptr)
		{
			parent = ptr;
			if(value > ptr->data)
				ptr = ptr->rChild;
			else
				ptr = ptr->lChild;
		}
		if(value > parent -> data)
			parent->rChild = binary_tn;
		else
			parent->lChild = binary_tn;
	}
	
}

void TreeNodeMgmt::displayBST()
{
	printBinTree(root);
	cout << endl;
}

void TreeNodeMgmt::printBinTree(TreeNode * ptr)
{
	if(ptr != nullptr)
	{
		printBinTree(ptr->lChild);
		cout << ptr->data << " ";
		printBinTree(ptr->rChild);		
	}
}
bool TreeNodeMgmt::search_node(int value)
{
	return searchBinTree(root, value);
}
bool TreeNodeMgmt::searchBinTree(TreeNode * ptr, int value)
{
	TreeNode * tn = ptr;
	while(tn != nullptr)
	{
		if(value == tn->data)
			return true;
		else
		{
			if(value > tn->data)
				tn = tn->rChild;
			else
				tn = tn->lChild;
		}
	}
}
void TreeNodeMgmt::delete_node(int value)
{
	deleteBinTree(root, value);
}
void TreeNodeMgmt::deleteBinTree(TreeNode *ptr, int value)
{
	if(!searchBinTree(ptr, value))
		return;

	TreeNode * parent;
	TreeNode * tn = ptr;
	
	while(tn != nullptr)
	{
		if(value == tn->data)
			break;
		else
		{
			parent = tn;
			if(value > tn->data)
				tn = tn->rChild;
			else
				tn = tn->lChild;
		}
	}
	//Case1. Leaf Node deletion
	if(tn->rChild == nullptr && tn->lChild == nullptr)
	{
		if(value < parent->data)
			parent->lChild = nullptr;
		else
			parent->rChild = nullptr;
		delete tn;
		
		return;
	}
	//Case2. One Degree Node deletion	
	if(tn->rChild == nullptr && tn->lChild != nullptr)
	{
		if(value < parent->data)
			parent->lChild = tn->lChild;
		else
			parent->rChild = tn->lChild;
		delete tn;
		return;
	}
	else if(tn->rChild != nullptr && tn->lChild == nullptr)
	{
		if(value < parent->data)
			parent->lChild = tn->rChild;
		else
			parent->rChild = tn->rChild;
		delete tn;
		return;
	}
	//Case3. Two Degree Node deletion
	if(tn->rChild != nullptr && tn->lChild != nullptr)
	{
		if(value < parent->data) //Case 3-1
		{	
			TreeNode * changeNode = tn->rChild;
			TreeNode * changeNodeParent;
			while(changeNode->lChild != nullptr)
			{
				changeNodeParent = changeNode;
				changeNode = changeNode->lChild;
			}
			
			if(changeNode->rChild != nullptr)
				changeNodeParent->lChild = changeNode->rChild;
			else
				changeNodeParent->lChild = nullptr;
			parent->lChild = changeNode;
			changeNode->rChild = tn->rChild;
			changeNode->lChild = tn->lChild; //nullptr
			
			delete tn;
			return;
		}
		else //Case 3-2 
		{
			TreeNode * changeNode = tn->rChild;
			TreeNode * changeNodeParent;
			while(changeNode->lChild != nullptr)
			{
				changeNodeParent = changeNode;
				changeNode = changeNode->lChild;
			}
			
			if(changeNode->rChild != nullptr)
				changeNodeParent->lChild = changeNode->rChild;
			else
				changeNodeParent->lChild = nullptr;
			parent->rChild = changeNode;
			changeNode->rChild = tn->rChild;
			changeNode->lChild = tn->lChild;
			
			delete tn;
			return;
		}	
	}
}

int main()
{
	TreeNodeMgmt bst;
	bst.insert_node(20);
	bst.insert_node(10);
	bst.insert_node(5);
	bst.insert_node(15);
	bst.insert_node(40);
	bst.insert_node(45);
	bst.insert_node(30);
	
	bst.displayBST();
	
	//search node
	if(bst.search_node(45))
		cout << "node search success" <<endl;
	else
		cout << "node search fail" <<endl;
	
	//case1 - Leaf node deletion
	bst.delete_node(30);
	bst.displayBST();
	
	//case2 - one Degree node deletion
	bst.insert_node(30);
	bst.insert_node(25);
	bst.delete_node(30);
	bst.displayBST();
	
	//case3 - two Degree node deletion
	bst.insert_node(30);
	bst.insert_node(35);
	bst.delete_node(30);
	bst.displayBST();
	
	return 0;
}

January 30, 2020SujinLee

Data Structure - Hash Table (Concept and C++ code)

Hash Table 구조

Hash Table: 키에 대한 데이터를 저장하는 데이터 구조
키만 알면 데이터가 어디에 저장되어있는지 알 수 있는 데이터 구조

Hash Table Wiki

Key 를 통해 바로 데이터를 받아올 수 있으므로 속도가 빠름

Term

해쉬(Hash) : 임의 값을 고정 길이로 변환하는 것
해쉬 테이블 (Hash Table) : 키와 키와 연관된 해쉬 값의 데이터가 저장된 공간
해싱 함수 (Hashing Function) : 키를 입력으로 넣어서 데이터가 저장되어있는 해쉬 테이블의 해쉬 주소를 리턴하는 함수
해쉬 값 (Hash Value), 해쉬 주소(Hash Address) : Key를 해싱함수로 연산해서 알아낼 수 있는 리턴값
슬롯 (Slot), 버킷 (Bucket) : 해쉬 값을 저장하는 공간

Hash Table 의 장단점과 주요 용도

장점
- 데이터 저장/읽기 속도가 빠르다 (검색 속도가 빠르다)
  - 검색에서 배열보다 해쉬테이블 구조가 좋은 이유
    - 배열 : index별로 일일이 검색해야, index를 순차적으로 검색할 때 찾고자 하는 데이터가 배열의 마지막 인덱스에 값인 경우 시간이 오래걸림
    - 해쉬테이블 : 데이터를 받고 그에 해당하는 키를 찾으면 해쉬함수를 한번만 돌리면 바로 그 데이터 저장위치를 해쉬테이블에서 찾을 수 있음
- 키에 대한 해쉬 값이 있는지 없는지 중복체크가 쉬움
  - 배열같은 경우는 index 에 대한 값이 있는지 없는지 중복체크할때 기존 데이터를 일일이 봐야함
단점
- 일반적으로 저장공간이 많이 필요
- 여러 key에 해당하는 해쉬 주소가 동일한 경우 충돌이 발생
  - 따라서 충돌을 해결하기 위한 별도의 자료구조가 필요
주요 용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현시 (중복확인이 쉽기 때문) - 웹 프로그래밍에서 캐쉬 기능을 구현할 때 바뀐 데이터만 서버에서 처리
- 블록체인

충돌해결책


Hash Table wiki_collision resolution
해쉬 테이블의 가장 큰 문제는 충돌(Collision): 한 개 이상의 key값이 동일한 hash address에 저장이 되어야 되는 경우

체이닝
- Open Hashing 기법 (개방해슁) : 해쉬 테이블 저장 공간 외의 공간을 활용
- 충돌이 일어나면 연결리스트 자료구조를 활용
- 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 방법
- 메모리 추가 문제
선형 조사법
- Closed Hashing 기법 (폐쇄 해슁) : 해쉬테이블 저장공간 안에서 충돌문제를 해결
- 충돌이 일어나면 hash address 의 다음 address 부터 맨 처음나오는 빈공간에 저장
- 저장공간 활용도를 높이기 위한 방법
- open addressing method
빈번한 충돌을 개선하는 방법
- 해쉬 함수의 재정의 및 해쉬 테이블 저장공간 확대
- 저장 공간을 두배로 증가시키는 것이 일반적 해결 방법

해쉬 함수

std::hash
c++ utility library - std::hash
Any bulit in hash function in C++
Key type as string, then why not int type?
- Defined in header functional
- Argument type : Key
- Return type : std::size_t
- 매개 변수(Key)의 해시 값을 나타내는 std :: size_t 유형의 값을 리턴
  - size_t는 해당 시스템에서 어떤 객체나 값이 포함할 수 있는 최대 크기의 데이터를 표현하는 타입(unsigned 형)
- hash support for strings (hash 에서 support하는 key는 cppreference Standard specializations for library types 항목 참고)

#include <iostream>
#include <string>
#include <functional>

using namespace std;

int main()
{
    string str = "Sunny";
    size_t str_hash = hash<string>{}(str);
    cout << "hash value is " << str_hash << endl; //1392135701625917544
}

SHA-256(Secure Hash Algorithm, 안전한 해시알고리즘)
SHA-256
- 어떤 데이터에도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬함수로 유용하게 활용 가능
- SHA-256
  - 가장 많이 사용되는 해시 함수
  - 해쉬의 결과 : 128 bit
  - 비트코인, 블록체인 시스템에서 활용
한국인터넷진흥원 KISA에서는 256비트 해시함수 SHA-256을 쉽게 활용할 수 있도록, 소스코드를 배포하고 있습니다.

시간복잡도

저장 및 데이터 읽는 데 걸리는 시간 복잡도
일반적인 경우 (Collision이 없는 경우) : O(1)
최악의 경우 (Collision이 모두 발생하는 경우) : O(n)

해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간복잡도는 O(1)이라고 할 수 있음

참고 개념

Open Addressing
- Open addressing strategy requires, that hash function has additional properties. In addition to performing uniform distribution, it should also avoid clustering of hash values, which are consequent in probe’s order.

C++ Code

해쉬 테이블 - by Linear Probing기법
해쉬테이블 - by Chaining 기법)
Hash Table 구현 by list

C++ Hash Table Implementaion

hash_table_with_linear_probing

constexpr int TABLE_SIZE = 128; 

class HashBucket
{
private:
	int key;
	int hashValue;
public:
	HashBucket(int key, int hashValue)
	{
		this->key = key;
		this->hashValue = hashValue;
	}
	int getKey()
	{
		return key;
	}
	int getHashValue()
	{
		return hashValue;
	}
};

class HashTable
{
private:
	HashBucket **table;
public:
	HashTable()
	{
		table = new HashBucket*[TABLE_SIZE];
		for(int i = 0; i < TABLE_SIZE ; ++i)
		{
			table[i] = nullptr;
		}
	}
	
	int get (int key)
	{
		int hash = (key % TABLE_SIZE);
		while(table[hash] != nullptr && table[hash]->getKey() != key)
		{
			hash = (hash+1) % TABLE_SIZE;
		}
		if(table[hash] == nullptr)
			return -1;
		else 
			return table[hash]->getHashValue();
	}
	void put (int key, int value)
	{
		int hash = (key % TABLE_SIZE);
		while(table[hash] != nullptr && table[hash]->getKey() != key)
		{
			hash = (hash+1) % TABLE_SIZE;
		}
		if(table[hash] != nullptr)
			delete table[hash];
		else 
			table[hash] = new HashBucket(key, value);
	}
	
	~HashTable()
	{
		for(int i = 0; i < TABLE_SIZE; ++i)
			if(table[i] != nullptr)
				delete table[i];
		
		delete[] table;
		
	}
};

hash_table_with_chaining

constexpr int TABLE_SIZE = 128; 

class LinkedHashBucket
{
private:
	int key;
	int hashValue;
	LinkedHashBucket * next;
public:
	LinkedHashBucket(int key, int hashValue)
	{
		this->key = key;
		this->hashValue = hashValue;
		this->next = nullptr;
	}
	int getKey()
	{
		return key;
	}
	int getHashValue()
	{
		return hashValue;
	}
	void setHashValue(int value)
	{
		this->hashValue = value;
	}
	LinkedHashBucket *getNext()
	{
		return next;
	}
	void setNext(LinkedHashBucket *next)
	{
		this->next = next;
	}
};

class HashTable
{
private:
	LinkedHashBucket **table;
public:
	HashTable()
	{
		table = new LinkedHashBucket*[TABLE_SIZE];
		for(int i = 0; i < TABLE_SIZE ; ++i)
		{
			table[i] = nullptr;
		}
	}
	
	int get (int key)
	{
		int hash = (key % TABLE_SIZE);
		if(table[hash] == nullptr)
			return -1;
		else 
		{
			LinkedHashBucket * bucket = table[hash];
			while(bucket != nullptr && bucket->getKey() != key)
				bucket = bucket->getNext();
			if(bucket == nullptr)
				return -1;
			else 
				return bucket->getHashValue();
		}
	}
	void put (int key, int value)
	{
		int hash = (key % TABLE_SIZE);
		if(table[hash] == nullptr)
			table[hash] = new LinkedHashBucket(key, value);
		else
		{
			LinkedHashBucket * bucket = table[hash];
			while(bucket -> getNext() != nullptr)
				bucket = bucket->getNext();
			if(bucket->getKey() == key)
				bucket->setHashValue(value);
 			else
 				bucket->setNext(new LinkedHashBucket(key, value));
		}
	}
	void remove(int key)
	{
		int hash = key%TABLE_SIZE;
		if(table[hash] != nullptr)
		{
			LinkedHashBucket *prevBucket = nullptr;
			LinkedHashBucket *bucket = table[hash];
			
			while(bucket->getNext() != nullptr && bucket->getKey() != key)
			{
				prevBucket = bucket;
				bucket = bucket->getNext();
			}
			if(bucket->getKey() == key)
			{
				if(prevBucket == nullptr)
				{
					LinkedHashBucket * nextBucket = bucket->getNext();
					delete bucket;
					table[hash] = nextBucket;
				}
				else
				{
					LinkedHashBucket * nextBucket = bucket->getNext();
					delete bucket;
					prevBucket->setNext(nextBucket);
				}
			}
		}
	}
	
	~HashTable()
	{
		for(int i = 0; i < TABLE_SIZE; ++i)
		{
			if(table[i] != nullptr)
			{
				LinkedHashBucket * prevBucket = nullptr;
				LinkedHashBucket * bucket = table[i];
				while(bucket != nullptr)
				{
					prevBucket = bucket;
					bucket = bucket->getNext();
					delete prevBucket;
				}
			}
			delete[] table;
		}
	}

};

hash_table_by_list

Hash Table implementataion by list - Youtube tutorial

#include<iostream>
#include<list> //해쉬 테이블 구현을 위해 linked list활용
#include<cstring> // string c++ header
				//key will be string type, value will be integer type	 
using namespace std;

//HashTable to implement - phone book

class HashTable
{
private:
	static const int hashGroups = 10; //  10개의 list  
	list<pair<int, string>> hash_table[hashGroups]; //key (int), hash_value (string)
public:
	bool isEmpty() const;
	int hashFunction(int key);
	void insertData(int key, string value);
	void removeData(int key);
	string searchTable(int key);
	void printTable();
};

bool HashTable::isEmpty() const//해쉬테이블이 비어있는지 체크 
{
	// 내가 선언한 table 은 list 객체를 가지고 있는 해쉬테이블배열이다
	// 각각의 list객체는 pair를 가지고 있다. 
	int sum = 0;
	for (int i = 0; i <hashGroups; ++i)
	{
		sum += hash_table[i].size();
	} 
	if(!sum)
	{
		return true;
	}
	return false;
}
int HashTable::hashFunction(int key)
{
	return key % hashGroups;
}

void HashTable::insertData(int key, string value)
{
	int hashValue = hashFunction(key);
	auto& slot = hash_table[hashValue];
	auto iter = begin(slot);
	bool keyExists = false;
	for(; iter != end(slot); ++iter)
	{
		if(iter->first == key)
		{
			keyExists = true;
			iter->second = value;
			cout << "[Warning] : Key exitsts, Value replaced" <<endl;
			break;
		}
	}
	if(!keyExists)
	{
		slot.emplace_back(key, value);
	}
	
	return;
}

void HashTable::removeData(int key)
{
	int hashValue = hashFunction(key);
	auto& slot = hash_table[hashValue];
	auto iter = begin(slot);
	bool keyExists = false;
	for(; iter != end(slot); ++iter)
	{
		if(iter->first == key)
		{
			keyExists = true;
			iter = slot.erase(iter);
			cout << "[Info] : Data removed" <<endl;
			break;
		}
	}
	
	if(!keyExists)
	{
		cout << "[Waning] : Key not found. Pair not removed" <<endl;
	}
}

string HashTable::searchTable(int key)
{
	
}

void HashTable::printTable()
{
	for(int i = 0; i < hashGroups; ++i)
	{
		if(hash_table[i].size() == 0)
		continue;
		
		auto iter = hash_table[i].begin();
		for(; iter != hash_table[i].end(); ++iter)
		{
			cout << "Key : " << iter->first << ", Value : " << iter->second << endl;
		}
	}
	return;
}

int main()
{
	HashTable HT;
	if(HT.isEmpty())
	{
		cout << "Hash Table is Empty" <<endl; 
	}
	
	HT.insertData(905, "Jim");
	HT.insertData(702, "Andy");
	HT.insertData(234, "Kylie");
	HT.insertData(406, "Tom");
	HT.insertData(289, "Sally");
	HT.insertData(289, "Judy");
	
	HT.printTable();
	
	HT.removeData(905);
	HT.printTable();
	
	return 0;
}

January 25, 2020SujinLee

Git Blog - create your Blog with GitHub Pages (steps by steps)

link

Jekyll docs for more info on how to get the most out of Jekyll.

Creating Blog with GitHub Pages

create repository with special repo name like “githubId.github.io” in GitHub

mkdir [folder]
cd [folder]
git clone [url] .
- git clone https://github.com/mmistakes/minimal-mistakes.git .
for window users, please delete “.git” folder
git init
git remote add origin [current repository url]
- git remote add origin https://github.com/sujinsjlee/sujinsjlee.github.io
- git remote -v
  - By above command i can check what repository is connected to local environment
git add .
git commit -m “blog start”
git push origin master

Notice

Jekyll Themem should be selected at the repository settings : In order for your site to be published, a Jekyll theme must be chosen, even if you don’t use Jekyll at all.

Posts

Categories

About

Home

To infinity and BEYOND

Data Structure - Tree (Concept and C++ code)

트리 구조

Term

이진트리와 이진 탐색트리

C++ code

tree_code

insert_data_in_tree

search_tree

delete_data_in_tree

이진 탐색 트리 삭제

Case 1. Leaf Node 삭제

Case 2. Child Node가 하나인 Node 삭제

Case 3. Child Node가 두 개인 Node 삭제

C++ 전체 코드

Data Structure - Hash Table (Concept and C++ code)

Hash Table 구조

Term

Hash Table 의 장단점과 주요 용도

충돌해결책

해쉬 함수

시간복잡도

참고 개념

C++ Code

hash_table_with_linear_probing

hash_table_with_chaining

hash_table_by_list

Git Blog - create your Blog with GitHub Pages (steps by steps)

link

Creating Blog with GitHub Pages

Notice