대엉코딩

* 이진 탐색 트리?

 - 검색에 많이 사용이 되는 형태입니다.

 - 중위 순회 (Inordered traversal)를 할 경우 key값에 따라 sorting된 결과를 얻을 수 있습니다.

    # 구조 조건

     - 각 노드들은 자식노드를 기껏해야 두 개만을 가질 수 있습니다.

    # 순서 조건

     - 각 노드들의 왼쪽 서브트리에 있는 노드들은 각 노드보다 작은 값을 가집니다.(key)

     - 각 노드들의 오른쪽 서브트리에 있는 노드들은 각 노드보다 큰 값을 가집니다.(key)

    # 중위 순회

구조 조건과 순서 조건을 만족하는 이진탐색트리를 구성(construct) 하였다면

위와 같이 inordered traversal을 하면 key값을 기준으로 정렬이 됩니다.

(30,40,50,55,60,70)

 * 탐색연산(search)

 - root 노드 부터 시작하여 탐색하고자 하는 값 n 과 비교를 하며

   비교하는 노드보다 n값이 작다면 왼쪽 서브트리로 가서 왼쪽 서브트리의 루트노드와 다시 비교.

   비교하는 노드보다 n값이 크다면 오른쪽 서브트리로 가서 오른쪽 서브트리의 루트노드와 다시비교를 하면 됩니다.

* 삽입연산(insert)

 - 삽입연산은 탐색연산과 같이 내려가다가 자기 자리를 찾아서 들어가면 됩니다

 - 위의 저의 예시는 나름 예쁜? 모양이지만 이진탐색트리의 구조 조건과 순서 조건만 만족 하면서 구성해 나가면됩니다.

 - 같은 노드들의 값과 수 여도 다양한 모양의 이진탐색트리가 나올 수 있습니다.

 - 역시나 이와 같은 경우에도 순서와 구조 조건이 모두 맞습니다 --> 중위순회를 하여도 결과가 그대로 나옵니다.

 * 삭제연산(delete)

 - 이진탐색트리는 어떠한 노드를 삭제연산을 수행하여 제거 하여도 그 결과의 트리 역시 이진탐색트리여야 합니다.

    (당연하죠? ㅎ)

 - 두 경우로 나누어서 보겠습니다.

    1.) 삭제하려는 노드의 두 자식노드가 leaf노드인 경우입니다. --->그냥 삭제해버리면 됩니다.

    2.) 삭제하려는 노드의 자식이 하나는 leaf노드이고 한쪽은 서브트리(노드)를 가지는 경우

       - 삭제하려는 노드의 자리에 한쪽 서브트리를 연결 해주면 됩니다.

    3.) 두 자식이 모두 leaf노드가 아닌 값을 가진 노드 들( 즉, 두개의 서브트리를 가지는) 일 경우

        -- 본 예에서 60을 삭제 하고자 한다고 가정 하겠습니다. delete(40)

        -- 위의 예에서 보고 이렇게 하면되지 , 쉽게 보일 수 있지만 아래의 예를 보면 약간은 생각보다 복잡합니다.

        -- 두가지 방법이 있습니다(succesor를 삭제노드위치에 위치, predecessor을 삭제 노드 위치에 위치)

           더 금방 찾을 수 있는 (왼쪽 서브트리의 첫번째 노드) succesor를 이용합시다.

        -- succesor를 찾아서 삭제하려는 노드의 위치에 위치 시키고 부모노드와

        -- 삭제한 노드의 subtree들과 successor를 연결 시켜 주시면 됩니다.

        -- 위와 같이 삭제 연산을 수행 한 뒤에도 이진탐색트리가 나오게 되었습니다.

 * 성능분석

 - search, insert, delete (탐색, 삽입, 삭제) 연산 모두 O(n) 입니다.

 - worst case는 편향된(즉, 한쪽으로만 쭉쭉 뻗어있는 ) 트리입니다. 

 - tree에서의 연산들은 tree의 depth와 연관이 되어있는데 이럴경우 depth가 n(n-1) 이기 때문입니다.

 - average case의 경우 O(log n) 인데 worst case도 O(log n ) 을 맞추고 싶을 경우

 - depth를 맞추어주기 위해서 어느정도 균형이 잡혀 있는(예뿌장한?) 트리를 만들어 주어야 합니다.

 - 대표적인 균형이진트리들은 AVL TREE, RED-BLACK TREE 등이 있습니다.