ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 5639 이진 검색 트리
    알고리즘 문제 2018. 10. 26. 23:06

    문제보기

    https://www.acmicpc.net/problem/5639


    이진 검색 트리를 전위 순회한 결과를 이용해 트리 모양을 유추하고 후위 순회를 출력하는 문제이다.

    전위 순회는 (루트 - 왼쪽 - 오른쪽) 이므로 입력값이 이전 입력값보다 작으면 반드시 왼쪽으로 다리를 뻗어 있는 것다. 만약 크다면 이전 입력 노드에 대한 successor 노드(해당 노드보다 큰 key를 가진 노드들 중 가장 작은 노드) 보다 큰지 작은지 판단하여, 만약 successor 보다 작다면 이전 입력 노드의 우측 child로 들어가면된다. 만약 successor 보다 크다면 successor의 우측 subtree 로 가거나 아니면 successor에 대한 successor의 우측 subtree로 가는지 반복적으로 체크해줘야할 것이다. (또는 재귀적.) successor는 parent이거나 right subtree의 min node임을 기억하자. 여기 문제에서는 successor 는 항상 parent 일 것이다. 왜냐하면 전위 순회 중이기 때문에 절대 최근 입력된 노드는 자신의 우측 subtree를 아직 입력값으로 받지 않기때문이다. 

    이진검색 트리에 대한 정리보기

    http://ingyeoking13.tistory.com/224

    소스보기

    https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/5639.cc


    '알고리즘 문제' 카테고리의 다른 글

    백준 5639 이진 검색 트리  (0) 2018.10.26
    백준 1922 네트워크 연결  (0) 2017.08.26

    댓글 0

Designed by Tistory.