Tree search

Study/알고리즘2018.08.28 11:33

블로그를 방치해둔지 오래된 것 같았다. 원래 웹사이트로 옮길려고 Squarespace 에서 웹사이트 만들려고

공부하다가 매달 돈내는 것이 부담되었다. 한달에 2만원 정도를 내야 하다니.. 흑..

결국, 티스토리를 쓰기로 했다. 졸려서 잠을 깨기 위해 Brillaint 에서 공부중인 내용을 정리하고자 한다.


https://brilliant.org/wiki/tree-search/


트리는 계층 데이터를 나타내는 데 사용되는 모델입니다. 자연 나무와 비슷하게, 그것은 노드, 잎, 가지를 가지고 있습니다.

일반적으로 언급되는 트리는 각 노드가 두 개의 다른 노드를 포함하는 이진 트리입니다.



위의 예에서 각 버블은 '노드'(node)를 나타냅니다. 한 버블에서 다른 버블을 가리키는 화살표를 '에지'(edge) 라고 합니다.
가장자리가 없는 최상위 노드("컴퓨터 하드웨어")를 '루트'라고 합니다. 노드에서 바로 이어지는 하나 이상의 노드를 '하위'라고 합니다.
또 다른 중요한 용어는 루트 노드에서 해당 노드까지의 경로의 길이로 정의된 노드의 깊이 (depth of a node) 입니다.
이진 트리는 연결된 목록을 사용하여 프로그래밍 언어로 표시됩니다. 예를 들어 C에서 트리는 노드 로부터 커집니다.

1
2
3
4
5
6
7
8
 
struct node 
{
     struct node* l;
     struct node* r;     /*two pointers ,one pointing to node to 
                         the right and one to left ( both below the current node) */
     int d;
};
cs

트리 검색이 루트에서 시작되고 노드에서 노드를 탐색하여 문제에 언급된 조건을 충족하는 특정 노드를 찾습니다.
선형 데이터 구조와는 달리 여러 가지 방법으로 요소를 횡단할 수 있습니다. 노드를 통과/횡단하기 위해
서로 다른 순서를 사용하는 많은 알고리즘이 있습니다.

그러한 방법 중 하나는 깊이 초기검색이다.

깊이 초기검색 (Depth first search) : 루트로부터 시작해서 역추적하기 전에 각 분기를 따라 가능한 한 멀리(더 깊이) 갑니다.



이 예에서 노드 7을 찾으면

노드 1 -> 노드 8 -> 노드 6 -> 노드 10 -> 노드 6 (백트랙) -> 노드 7의 알고리즘 트레이스입니다.

'Study > 알고리즘' 카테고리의 다른 글

Depth First Search 코드로 만들기  (0) 2018.08.28
Tree search  (0) 2018.08.28
LongestWord - C++  (2) 2018.02.20
문자가지고 순서대로 정열했는지 판정하기  (0) 2018.01.11
Binary Search with example  (0) 2016.11.19
Linear Search 1  (0) 2016.11.19

작성자

Posted by 비타오백

관련 글

댓글 영역

티스토리 툴바