이진 탐색 트리(Binary Search Tree)

• 이진트리의 일종
• 효율적인 탐색 가능
• 규칙
  • 노드의 키는 유일해야한다
  • 왼쪽 자식노드는 부모노드 보다 값이 작다
  • 오른쪽 자식노드는 부모노드 보다 값이 크다
  • 왼쪽, 오른쪽 자식 노드도 이진 탐색 트리 형태이다
• 탐색은 O(logn)의 시간복잡도를 갖는다
• 삽입
  • 루트 노드에서 시작하여 단말 노드에 도달할 때까지 규칙에 맞게 진행하여 삽입
• 삭제
  • 자식이 없을 시는 그냥 삭제
  • 자식이 1개 있을 시 해당 자식을 올림
  • 자식이 2개 있을 때 
    • 왼쪽자식 중 가장 큰값 또는 오른쪽 자식 중 가장 작은값을 올림