트리 순회( tree traversal ) 순회 방법

• 트리 순회( tree traversal )는 트리 구조에서 각각의 노드를 한 번씩만 체계적으로 방문하는 과정을 말합니다. 그리고 노드를 순회하는 순서에 따라서 후위 순회, 전위 순회, 중위 순회가 있습니다.

후위 순회( postorder traversal )

• 후위 순회(postorder traversal)는 자식들 노드를 방문하고 자신의 노드를 방문하는 것을 말합니다.

후위 순회 pseudo code

postorder( node )
    if (node.visited == false)
        postorder( node->left )
        postorder( node->right )
        node.visited = true

전위 순회( preorder traversal )

• 전위 순회( preorder traversal )는 먼저 자신의 노드를 방문하고 그 다음 자식 노드들을 방문하는 것을 말합니다.

전위 순회 pseudo code

preorder( node )
    if (node.visited == false)
        node.visited = true
        preorder( node->left )
        preorder( node->right )

중위 순회( inorder traversal )

• 중위순회(inorder traversal)는 왼쪽 자식 노드를 먼저 방문 그다음의 자신의 노드를 방문하고 그 다음 오른쪽 자식 노드를 방문하는 것을 말합니다.

• 이진 탐색 트리에서 오름 차순으로 접근할 때 중위 순회를 사용합니다.

중위 순회 pseudo code

inorder( node )
    if (node.visited == false)
        inorder( node->left )
        node.visited = true
        inorder( node->right )

이진 트리( Binary Tree )란?

• 각각의 노드의 자식노드 수가 2개 이하로 구성되어있는 트리를 의미합니다.

이진 트리의 종류

• 정이진 트리(full binary tree): 자식 노드가 0 또는 2개인 이진 트리를 의미합니다.

• 완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리를 의미합니다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있습니다.

• 변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리를 의미합니다.

• 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리를 의미합니다.

• 균형 이진 트리(balanced binary tree): 모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 높이 차이가 1이하인 트리입니다. map, set을 구성하는 레드블랙트리는 균형이진트리 중 하나입니다.

이진 탐색 트리( BST, Binary Search Tree )

• 이진트리의 일종으로 노드의 오른쪽 하위 트리에는 "부모 노드의 값보다 큰 값"이 있는 노드만 포함되고 왼쪽 하위트리에는 "부모 노드의 값보다 작은값"이 들어있는 트리를 말합니다. 이러한 특징 덕분에 값을 검색하기 유용하며 균형이 잘 이루어져 있다면 O(logN)의 시간복잡도를 가집니다.

이진 탐색 트리와 삽입 순서

• 이진 탐색 트리를 3, 2, 1을 순서대로 삽입했다면은 선형적인 구조가 됩니다. 이럴 경우 O(N)의 검색 시간 복잡도를 가지게 됩니다. 이러한 문제를 해결하기 위해 삽입, 삭제 시마다 동적으로 트리의 균형을 잡는 AVL 트리, 레드-블랙 트리가 있습니다.

자료 참조 : https://blog.naver.com/jhc9639/222289089015