이진 탐색 트리
이진 탐색 트리(binary search tree)는 효율적인 탐색을 지원하는 특별한 트리이다.
이진 탐색 트리에서는 각 노드가 자식을 최대 두개까지만 가질수 있다.
노드의 위치는 노드의 키-값에 의해 결정이 된다.
부모 노드의 왼쪽 자식 노드는 부모 노드보다 키-값의 크기가 작아야 하고, 오른쪽 자식 노드는 부모 노드보다 키-값의 크기가 커야한다.
트리를 이러한 방식으로 구성해두면 특정 키-값을 가진 노드를 쉽게 탐색할수있다.
각 단계마다 크기를 비교하며 바로 찾을수있다는 뜻이다.
트리는 균형을 잡아줄 필요가 있는데,
이진 탐색 트리에 노드를 너무 많이 추가하면, 자식이 하나뿐인 노드가 많이 생기면서, 트리의 높이가 터무니 없이 높아져버린다.
예를 들어 새로 추가하는 노드의 키-값이 항상 이전 노드의 값보다 크다면
이건 탐색 트리라고 만든 구조가 어느새 링크드 리스트화가 되는 것이다.
이럴ㄹ 때에는 트리의 높이가 줄어들게끔 노드를 재배열 해야한다.
완전히 균형이 잡힌 트리는 높이가 최소한으로 작은 트리이다
이진 힙
이진 힙(binary heap)은 최대(또는 최소) 항목을 즉시 구할수 있는 특별한 이진 탐색 트리이다.
특히 우선순위 큐를 구현할때 매우 유용하다.
힙에서는 최대(또는 최소) 항목을 구하는 비용이 O(1)인데,
힙의 최대(또는 최소) 항목이 항상 트리의 루트이기 때문.
노드의 탐색, 추가 비용은 여전히 O(log n)이다.
힙의 노드 배치 규칙은 이진 탐색 트리와 동일한데,
제약이 하나 더 추가가 된다.
부모 노드가 반드시 두개의 자식 노드보다 값이 커야한다는 것이다.
항목들 사이에서 최대,최솟값을 빈번하게 다뤄야 한다면 이진 힙을 사용하자
그래프
그래프는 트리와유사한 데이터 구조이다.
트리와 다른 점이라면 자식,부모 노드라는 개념이 없으며, 따라서 루트 노드도 없다.
그래프에서는 데이터가 노드와 엣지로 자유롭게 되열되게 된다.
모든 노드는 다른 노드를 가르키는 엣지를 여러개 가질수있다.
그래프는 수많은 데이터 스트럭쳐중에서 가장 유연한 구조이다
거의 모든 유형의 데이터를 표현하는데 사용할수있다.
ex)소셜 네트워크를 다루어야 한다고 치면
노드로 사람을 엣지로 친구관계를 나타낼수있는 그래프가 이상적이다.
해시 테이블
해시 테이블은 항목의 탐색을 O(1)비용으로 수행할수있는 자료구조이다.
해시테이블에서는 전체 항목의 수가 열개밖에 안되든, 수천만개에 달하든
항목 하나를 찾는 비용이 상수 시간으로 동일하다.
해시 테이블을 이용하려면 대량의 연속적 메모리를 미리 할당해야 한다.
이점은 배열과 유사한데 항목을 순차적으로 저장하지 않다는 것이
배열과의 차이점이다.
해시 테이블에서 항목이 자리잡는 위치는 해시 함수에 의해 랜덤으로 정해진다.
해시 함수는 저장하려는 데이터를 입력받아 의미없고 불규칙한 수로 출력해준다.
그리고 이렇게 출력된 수를 이용하여 메모리에 저장을 한다.
해시 함수를 이용하면 구하는 항목에 바로 접근할수있다.
해시 테이블에서 어떤 값을 조회할때는, 먼저 그값을 해시함수에 입력한다.
해시 함수는 메모리 속에서 항목이 저장되어 있을 정확한 위치를 출력해준다.
다만 해시함수는 한가지 문제가 있는데
가끔씩 해시 한수가 서로 다른 두 입력값에 대해 동일한 메모리 위치를 반환한다는것.
이러한 현상을 해시충돌이라고 한다.
그렇기에 해시충돌을 최소화 시키는 것이 올바른 해시테이블을 만드는 방법이다.
