트리, maxheap, minheap, 동적 배열, 해싱

정의

• 자식 부모 이렇게 트리를 형성하는데 트리에서 정의는 정점끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프입니다.

헷갈려던 개념

• 리프노드
  • 리프노드는 자식노드인 줄 알았습니다. 그러나 자식을 갖고 있지 않은 노드를 의미합니다.
• 차수
  • 자식의 갯수를 의미합니다 (특정 노드에 대해서)

이진트리

• 이진트리의 루트노드는 레벨이 1, .. , 레빌이 D인 이진트리의 노드의 갯수는 D <= n <= 2^d -1이다.
• 완전이진트리는 왼쪽노드부터 차례대로 채워지는 것이다. 그래서 공간을 효율적으로 사용할 수 있다.
• 완전이진트리는 꼭 자식이 모두 2개가 있어야만 완전이진트리가 아니다.

배열을 이용한 이진트리 표현 방법

• 배열을 이용해서 이진트리를 만들어도 되고, 포인터를 이용해서 이진트리를 만들어도된다..

위의 그림에서 부모를 인덱스로 하여 자식을 표현하는 방법

    부모  [1] [2] [3] [4] [5] [6] [7]


왼쪽자식   2   4   6   0   0   0   0

오른쪽자식 3   5   7   0   0   0   0

• 위에서 부모의 배열하나 두고, 자식 배열을 왼쪽 자식, 오른쪽 자식 배열을 각각 하나씩 두면된다.

자식을 인덱스로 하여 부모를 표현

    자식  [1] [2] [3] [4] [5] [6] [7]

    부모   0  1    1   2   2   3   3

maxheap, minheap

• maxheap이나 minheap이 만들어질 때는 최대 O(NlogN)의 시간이 걸린다. 왜냐? heap을 만드는 과정에서 삽입, 삭제는 logN이 걸리는데 배열의 원소가 n개있다고 가정하면 이러한 과정을 n번해야해서 => NlogN이걸리게된다.
• heapfiy 한 과정에서 최대 logN번 발생하기때문에
• heapfiy ->
  • 현재 노드랑 자식 노드들 중에서 가장 큰 값을 찾는다
  • 자식이 더 큰 값이라면 현재 노드A와 자식노드 B랑 교체한다
  • 교체 이후 다시 큰 값에서 다시 heapify를 진행한다
  • 만약 현재노드가 가장 큰 값이라면 heapify 종료
  • n / 2 에서 1번노드까지 실행
• 힙만들기는 -> o(nlogn)이 걸린다
• 삽입
  • 값을 삽입 할때는 일단 맨 밑에 넣는다고 가정한다.
  • 그후 heapify 과정을 통해서 자신의 부모 노드와 비교 후 값이 부모가 작다면 교체작업을 한다(max heap기준)
  • 이렇게하면 최대 O(logN)이 걸리게된다.
• 삭제
  • 일반적으로 값이 100% 존재 하는 것은 루트 노드
  • 여기서 맨밑의 노드를 루트 노드로 당긴다.
  • 그후 heapify(1)로 1번 노드에 대해서 max-heap과정을 수행한다

동적 배열

• 동적 배열은 정적배열에서의 삽입, 삭제 탐색 i번째 원소의 조회 역시 모두 O(1)의 시간복잡도를 가집니다.
• 배열의 길이가 고정된 경우, 같은 양의 데이터를 저장할 시 동적배열은 정적배열보다 더 많은 메모리를 사용하게된다.

해싱

• 해시 검색은 상수 검색시간이 상수시간이다.

• 실생활에서 우편번호로 우편물을 분류하는 기법이 해시 검색법과 비슷한 형태이다..

• 기본 용어

  • 키 또는 인덱스 : 해시 테이블에서 레코드를 찾기 위한 값

  • 해시 값 : 정보를 해시 테이블에 저장하기 위한 위치 값

  • 해시 함수 : 키를 해시 값으로 바꿔주는 함수

  • 해시 테이블 : 버킷의 집합

  • 버킷 : 레코드를 저장하는 공간으로 한 버킷은 하나 이상의 레코드를 수용 가능

  • 충돌 현상 : 서로 다른 2개 이상의 레코드가 같은 해시 값을 갖는 현상