Binary Search Tree

[devLupin]

• child node를 최대 2개 갖는 계층적 구조
• 특성
  • 어떤 node의 좌측 child node의 모든 값이 더 작고,
  • 어떤 node의 우측 child node의 모든 값이 더 큼.
  • 즉, 원소가 크기별로 정렬되었다고 할 수 있다.
• 그래서 왜 사용하는지?
  • insert, erase, find, update가 전부 $O(lgN)$
  • 배열에서 제일 뒤에 insert하면 $O(1)$이지만, erase는 중간에 원소를 제거하게 되면 $O(N)$이 된다.
  • find, update 또한 $O(N)$
  • 해시에서 N보다 큰 최초의 원소가 무엇인지 알아내야 한다면?
  • 해시는 효율적으로 알아낼 방법이 없음.
    • 값을 크기 순으로 저장하지 않기 때문

[devLupin]

node의 삭제 과정

• 삭제가 구현이 가장 까다롭다.

• 세가지 경우가 있다.

  • child node가 0개인 경우
  • 그냥 삭제하면 된다.
  • child node가 1개인 경우
  • 삭제할 노드의 위치에 child node를 올리면 된다.
  • child node가 2개인 경우
  • right child node에서 가장 작은 값을 삭제할 위치로 옮김.
  • 실제 구현에서는 right child node에서 왼쪽의 최대 depth로 가면 된다.

• 즉, 높이에 따라 시간 복잡도가 차이 난다.

  • 트리가 편향되면 효율이 안 좋음

[devLupin]

C++ STL

• set, multiset, map
  • hash는 앞에 unordered가 붙는다.

[devLupin]

set method

• 대부분의 method는 hash 자료구조와 비슷
• 순서대로 정렬되기 때문에 STL 함수의 사용 가능(멤버함수 X)
  • prev(iterator, n)
  • iterator n칸 전의 위치 반환
  • n을 인자로 넘겨주지 않으면 1
  • next(iterator, n)
  • iterator n칸 뒤의 위치 반환
  • n을 인자로 넘겨주지 않으면, 1
  • lower_bound(target)
  • target 이상의 값이 있는 최초의 위치
  • upper_bound(target)
  • target 초과의 값이 있는 최초의 위치
  • advance(iterator, n);
  • iterator의 위치 변경
  • 음수인 경우 뒤로, 양수인 경우 앞으로 이동
  • find(target)

[devLupin]

multiset method

• 중복을 허용하는 multiset에서 find(target)을 사용한다면?
  • 여러 개가 있을 시 그 중에서 아무거나 반환된다.
• 처음으로 등장하는 원소를 찾으려면 lower_bound를 사용
• upper_bound 주의사항
  • 원소가 {1, 100, 100}이 있을 때, 100의 upper_bound를 찾게 되면
  • end()를 반환하게 된다.
  • 해당 iterator를 출력하면 런타임 에러가 발생하니 주의하자