검색 알고리즘
BST, Hash가 가장 좋음.
Binary Search Tree
삭제
자식이 없을 때 : 그냥 삭제
자식이 1개 있을 때 : 자식과 부모를 연결한 후 삭제
자식이 2개 있을 때 : 손자를 자신의 위치로 대치 후 삭제
참고 : https://www.delftstack.com/ko/tutorial/data-structure/binary-search-tree-delete/#%EC%82%AD%EC%A0%9C%ED%95%A0-%EB%85%B8%EB%93%9C%EC%97%90%EB%8A%94-%EC%99%BC%EC%AA%BD%EA%B3%BC-%EC%98%A4%EB%A5%B8%EC%AA%BD-%EC%9E%90%EC%8B%9D%EC%9D%B4-%EB%AA%A8%EB%91%90-%EC%9E%88%EC%8A%B5%EB%8B%88%EB%8B%A4
AVL 트리
Balance Factor를 이용하여 트리의 균형을 유지
BST와 동일한 방식으로 삭제, 이후 다시 균형 작업
Red-Black Tree
2-3-4트리의 개선
5개의 규칙을 회전과 색 변환을 통해 유지
1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.
참고 : https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC#%ED%8A%B9%EC%84%B1(Properties)
BST의 정리
BST는 검색 속도 향상을 위해 사용(log2n).
트리 규형이 깨질 경우 성능 저하가 발생
이를 막기 위해 AVL, Red-Black 트리 사용.
Hashing
Hash 충돌이 심하다면 Hash index 내부에 LinkedList 대신 Hash를 한번 더 해주는 것도 좋은 해결책이 될 수 있음.
Hash의 공간을 실제 데이터의 양보다 2~3배정도 늘려서 충돌을 최소화시키고 검색 속도를 최대화 하는 방법도 있음
STL의 경우 ordered한 자료구조(map, set)의 경우는 BST로 구현되어 있고, unordered한 자료구조(unordered_map, unordered_set)의 경우 Hash로 구현되어 있음.
