4.2 최소 트리

문제 

오름차순으로 정렬된 배열이 있다. 이 배열 안에 들어 있는 원소는 정수이며 중복된 값이 없다고 했을때 높이가 최소가 되는 이진탐색트리를 만드는 알고리즘을 작성하라. 

 

접근법

이진탐색트리는 '모든 왼쪽 자식들 <=  N <모든 오른쪽 자식들' 의 속성을 가지고 있으며, 높이가 최소가 되는 이진 탐색트리는 루트 노드가 배열의 중앙에 오도록 해야할 것이다. 따라서 배열 가운데 원소를 트리에 삽입하고 왼쪽 하위 트리에는 왼쪽 절반 배열원소를, 오른쪽 하위 트리에는 오른쪽 절반 배열원소를 전달하며 재귀 호출을 진행하는 방식으로 구현해야한다. 

def make_tree(sorted_list, start, end):
    if start >= end :
        return null
    center = (start+end)/2
    node = Node(sorted_list[center])
    node.left = make_tree(sorted_list, start, center)
    node.right = make_tree(sorted_list, center+1, end)
    return node

def Solution(sorted_list):
    return make_tree(sorted_list, 0, len(sorted_list))