나무 | 아름다운 데이터 구조

데이터 구조의 숲에서 여행하는 동안 나는 나무를 보았고 그것을 좋아했습니다 :D 가벼운 농담을 실례합니다.
하지만 네, 오늘 저는 트리 데이터 구조에 대해 조금 이야기하고 싶습니다.

소셜 미디어 플랫폼을 사용해 본 적이 있다면 트리 데이터 구조를 많이 사용하는 시스템에 노출된 적이 있을 것입니다. 어떤 사람들은 그것을 이해하기 어려운 것으로 분류하지만 나는 그것이 매혹적이며 많은 경우에 우리의 삶을 더 쉽게 만들어 준다고 생각합니다.

튜토리얼 타임라인은 다음과 같습니다.

트리란 무엇입니까?

왜 존재합니까?

나무의 종류?

실제 사례

구현

나무 - 뭐야?

노드와 에지로 구성된 비선형 계층 데이터 구조입니다. 따라서 새로운 단어가 많으므로 먼저 새로운 용어를 방해하지 않도록 합시다.

비선형 계층: 배열이나 연결 목록과 달리 이 데이터 구조는 계층 방식으로 연결된 데이터를 보유하도록 설계되었습니다. 계층적이란 내부에 상위 하위 관계가 있는 데이터를 보유할 수 있음을 의미합니다.

노드: 노드는 하위 노드에 대한 키 또는 값과 포인터를 포함하는 엔티티입니다.

에지: 두 노드 사이의 링크를 에지라고 합니다.

참고: 트리는 데이터 구조이고 이진 트리는 이 데이터 구조의 유형입니다. 모든 이진 트리는 트리이지만 모든 트리는 이진 트리가 아닙니다.

나무 - 왜?

간단히 말해서 효율적인 방식으로 데이터에 액세스할 수 있는 무언가가 필요했습니다. 트리 액세스 시간은 연결된 목록보다 낫습니다.

또 다른 이유: 트리는 자연스럽게 계층적 관계를 형성하는 데이터를 저장하고자 할 때 정말 유용합니다. 가장 간단한 공통 세계 예는 가계도가 될 수 있으며 다소 사소한 기술 예는 하나의 데이터베이스 인덱싱이 될 수 있습니다.

실제 사례

데이터베이스 인덱싱은 B-트리 또는 B+ 트리라는 특별한 종류의 트리를 사용하여 사용됩니다.

DNS - 트리 데이터 구조도 사용합니다.

일부 기계 학습 알고리즘에서는 결정 트리 기반 학습이 사용됩니다.

XML 구문 분석기는 트리를 사용합니다.

이진 검색 트리, 힙, 힙 정렬, 허프만 코딩 트리, 구문 트리도 트리가 사용되는 몇 가지 예입니다.

구현

충분히 장황하게 구현을 시작하겠습니다.
우리가 알다시피 트리는 가장자리를 가진 서로 관련된 노드의 모음입니다. 트리 노드는 어떻게 생겼습니까?

class Node():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

아래와 같은 트리를 만들고 싶다고 합시다. 어떻게 할 수 있습니까?

#     1
#    / \
#   2   3
#  / \
# 4   5

한 가지 방법은 수동으로 루트/부모 노드를 생성하고 자식을 추가하는 것이지만 더 나은 방법을 공유하고 싶습니다. 배열에서 재귀적으로 트리를 생성하는 함수를 작성할 수 있습니다.

nodes = [1,2,3,4,5]

위의 배열은 우리가 말하는 트리의 표현이며, 만약 i가 부모 노드라면 왼쪽 자식은 2i+1이고 오른쪽 자식은 2i+2입니다. 이를 사용하여 트리를 생성하는 함수를 쉽게 작성할 수 있습니다.

nodes = [1,2,3,4,5]

def createTree(nodes, i):
    if i >= len(nodes):
        return None

    root = Node(nodes[i])
    root.left = createTree(nodes, 2 * i + 1)
    root.right = createTree(nodes, 2 * i + 2)
    return root

흠, 이제 트리를 만들었지만 어떻게 볼 수 있습니까? 또는 좀 더 공식적으로 말하면 트리의 모든 노드를 어떻게 방문할 수 있습니까?
이를 트래버스라고 합니다. 나처럼 영어가 모국어가 아닌 경우 트래버스는 "횡단 또는 통과"를 의미합니다. 또는 단순히 "앞뒤로 또는 옆으로 이동"합니다.
어떻게 할 수 있습니까?
순회는 주로 세 가지 유형이며 루트 노드에 따라 다릅니다.

선주문

후주문

순서대로

Photo by Rodrigo Santos