[트리]이진 탐색 트리 6/25

*이진 탐색 트리
 1. 특징
  ⓐ 트리의 모든 노드의 키 값은 유일 해야한다.
  ⓑ 왼쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 작아야 한다.
  ⓒ 오른쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 커야한다.
  ⓓ 왼쪽과 오른쪽 서브트리 모두 이진 탐색 트리이다.
  - ⓐ~ⓓ의 특징을 만족해야만 이진 탐색 트리라고 할수 있다.
  - "탐색"이라는 단어가 들어 있을 만큼 자료 탐색에 효율을 두기 위해 만든 자료구조
   ( >특정 키 값에 해당하는 노드를 찾는 것이 기본 기능 )
ex) 

 2. 이진 탐색 트리의 삽입/삭제
  ⓐ 삽입

   Step 1: 추가되는 키 값이 트리에 존재하는지를 탐색한다.(값의 탐색연산)
              (같은 키 값이 존재하면 False / 다른 키 값을 가지면 Step 2 실행)
   Step 2: 추가되는 키 값이 들어갈 위치를 찾는다.(위치탐색연산)
   Step 3: 노드의 연결
   ex)

  ⓑ 삭제 
   삭제 연산은 3가지의 경우로 나눠서 생각을 해줘야한다.
   Case 1 : 삭제 되는 노드가 단말 노드인 경우
    - 부모 노드의 선을 끈고, 삭제
   Case 2 : 삭제 되는 노드의 자식이 1개인 경우
   - 삭제 되는 노드의 부모노드와 자식노드를 연결 해준 뒤에 삭제
   Case 3 : 삭제 되는 노드의 자식 노드가 2개인 경우
   - 왼쪽 서브트리의 가장 큰 키 값을 가진 노드
     또는, 오른쪽 서브트리의 가장 작은 키 값을 가지는 노드가 삭제 되는 노드를 대체 후
     대체된 노드에서의 삭제를 Case1~3에서 해당하는 경우를 반복
ex)

   
----------------------------------------------------------------------------------------------------------

먼가 설명이 잘됬는지는 모르겠지만... 히프와 이진 검색트리를 알아보는 것으로

트리를 마치도록하겠다. 기회가 된다면 나중에 구현한 소스도 올리도록 하겠다~

이해가 안되거나 이건 더 추가 해줬으면 하는 내용 있으면 요청부탁드립니다.

그럼 이만 주말을 만끽하러~ 슈슝~