Heap

여러개의 값중에서 가장 크거나 작은값을 빠르게 찾기위한 이진트리
완전 이진 트리의 형태를 띠어야함,
부모의 값은 자식값보다 크거나 작아야함

데이터의 삽입과 삭제는 모두 O(logN) 이 소요됨
트리의 레벨이 늘어날수록 노드의 수는 두배씩 증가함

Trie

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
주로 문자열이 키인 경우가 많다
이진탐색 트리와 달리 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않음

사용하는 목적?
단순하나 하나씩 비교하면서 탐색을 하는것보다 효율적이다.
빠르게 탐색이 가능하지만 각 노드에서 자식들에 대한 포인터들을 배열로모두
저장하고 있다는 점에서 저장공간의 크기가 작다는 단점도있음

시간복잡도
제일 긴 문자열의 길이를L , 총 문자열들의 수를 M
=> O(M*L)

탐색시 시간복잡도:O(L)

AVL Tree

스스로 균형을 잡는 이진탐색 트리

트리의 높이가 h일때 시간 복잡도는 O(h)

특징

• 이진 탐색 트리의 속성을 가짐
  -왼쪽, 오른쪽 서브 트리의 높이차이가 최대1
  -어떤 시점에서 높이 차이가1보다 커지면 회전을 통해 균형을 잡아 높이 차이를 줄임
• 높이를 logN으로 유지하기때문에 삽입, 검색,삭제의 시간 복잡도는 O(logN)

Red-Black Tree

자가 균형 이진 탐색 트리

다음과 같은 조건을만족함
1.모든 노드는 빨간색 혹은 검은색이다
2.루트 노드는 검은색이다
3.모든 리프노드(NIL)들은 검은색이다( NIL:null leaf,자료를 갖지않고 트리의끝을 나타내는 노드)
4.빨간색 노드의 자식 노드는 검은색