728x90
이진 탐색 트리
2

[Programmers]Python_길 찾기 게임

문제 문제 설명 전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다. 라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다. 그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다. 라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다. 트리를 구성하는 모든 노..

[Python] 이진 탐색 트리(BST)와 트리 순회

■ 이진 탐색 트리 (Binary Search Tree) 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이뤄져 있는 반면, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있는 트리 위 그림을 보면 이진 탐색 트리가 어떻게 생겨먹은 것인지 이해할 수 있을 것이다. 대충 어떤 것인지 알았다면 이제 이 그림에서 원하는 값을 찾는 과정을 살펴볼 것이다. ■■ 위 이진 탐색 트리에서 우리는 '7'을 찾아 볼 것이다. 당연하지만 루트인 '15'부터 시작한다. 1. '7'은 '15'보다 작기 때문에 왼쪽 자식 노드로 탐색이 진행된다. 2. '10' 또한 마찬가지로 '7'이 더 작기 때문에 왼쪽 자식 노드로 탐색이 진행된다. 3. 여기서부터 '7'은 '5'보..

728x90