트리 - week3

신병규·2023년 3월 17일

SW Jungle

목록 보기

4/4

트리

트리(tree)는 계층적인 데이터를 표현하기 위한 비선형 자료구조로, 그래프의 일종입니다. 일반적으로 루트(root) 노드가 존재하고 각 노드는 하나 이상의 자식(child) 노드를 가질 수 있습니다. 자식 노드는 부모(parent) 노드로부터 상속받은 속성을 갖는 경우가 많습니다.

트리는 계층 구조를 갖는 데이터를 저장하고 관리하기 위해 사용됩니다. 예를 들어, 파일 시스템의 폴더 구조, 조직도, 계층적인 디렉토리 구조 등이 트리 자료구조를 이용하여 표현됩니다. 또한 검색 트리(search tree)라는 특별한 종류의 트리 자료구조를 이용하여 데이터를 저장하고 검색할 수 있습니다. 검색 트리의 예로 이진 검색 트리(binary search tree)가 있습니다.

트리 자료구조의 특징

계층적 구조를 가진다.

루트 노드는 오직 하나만 존재한다.

각 노드는 하나 이상의 자식 노드를 가질 수 있다.

각 노드는 부모 노드를 가질 수 있다.

노드 간의 연결은 일방향으로만 가능하다(부모->자식).

기본 용어

루트(Root) : 트리의 최상위 노드로, 트리의 시작점입니다. 루트 노드는 부모가 없는 유일한 노드입니다.

노드(Node) : 트리를 구성하는 기본 요소로, 트리의 각 구성 요소에 대한 정보를 저장합니다. 노드는 다른 노드와의 관계를 통해 트리 구조를 형성합니다.

부모(Parent) : 어떤 노드의 상위 노드를 그 노드의 부모 노드라고 합니다. 각 노드는 하나의 부모 노드를 가질 수 있습니다(루트 노드 제외).

자식(Child) : 어떤 노드의 하위 노드를 그 노드의 자식 노드라고 합니다. 노드는 여러 개의 자식 노드를 가질 수 있습니다.

형제(Sibling) : 같은 부모를 가지는 노드들은 서로 형제 노드입니다.

리프(Leaf) 또는 단말 노드(Terminal Node) : 자식 노드가 없는 노드를 리프 노드 또는 단말 노드라고 합니다. 트리의 가장 아래쪽에 위치한 노드들입니다.

내부 노드(Internal Node) 또는 비단말 노드(Non-Terminal Node): 리프 노드가 아닌 노드를 내부 노드 또는 비단말 노드라고 합니다. 이들 노드는 최소한 하나의 자식 노드를 가지고 있습니다.

레벨(Level) : 루트 노드로부터 노드까지의 경로 길이를 노드의 레벨이라고 합니다. 루트 노드의 레벨은 0입니다.

높이(Height) : 트리의 높이는 트리의 가장 깊은 노드의 레벨입니다. 루트 노드만 있는 경우 트리의 높이는 0입니다.

Python3 tree

파이썬에서는 tree 자료 구조를 다루기 위한 내장 함수들을 제공합니다.

ET.Element(tag, attrib={}) : xml.etree.ElementTree 모듈에서 제공하는 함수로, tag와 attrib을 인자로 받아 새로운 Element 객체를 생성합니다.

ET.SubElement(parent, tag, attrib={}) : xml.etree.ElementTree 모듈에서 제공하는 함수로, parent 노드에 tag와 attrib을 인자로 받아 새로운 Element 객체를 생성합니다.

ET.ElementTree(element=None, file=None) : xml.etree.ElementTree 모듈에서 제공하는 함수로, Element 객체를 인자로 받아 새로운 ElementTree 객체를 생성합니다. 또는 file 인자를 지정하여 파일에서 XML 문서를 읽어 ElementTree 객체를 생성할 수도 있습니다.

ET.SubElement(parent, tag) : xml.etree.ElementTree 모듈에서 제공하는 함수로, parent 노드에 tag를 인자로 받아 새로운 Element 객체를 생성합니다.

ET.dump(elem) : xml.etree.ElementTree 모듈에서 제공하는 함수로, elem 인자로 받은 Element 객체를 출력합니다.

node.clear() : ElementTree의 노드에서 해당 노드의 자식 노드와 속성 정보를 모두 제거합니다.

node.find(tag) : ElementTree의 노드에서 해당 tag와 일치하는 첫 번째 하위 노드를 반환합니다.

node.findall(tag) : ElementTree의 노드에서 해당 tag와 일치하는 모든 하위 노드를 반환합니다.

node.text : ElementTree의 노드에서 해당 노드의 텍스트를 반환합니다.

node.tag : ElementTree의 노드에서 해당 노드의 태그를 반환합니다.

node.attrib: ElementTree의 노드에서 해당 노드의 속성 정보를 담은 딕셔너리를 반환합니다.

node.get(key) : ElementTree의 노드에서 해당 key와 일치하는 속성 값을 반환합니다.

node.set(key, value) : ElementTree의 노드에서 해당 key와 value를 인자로 받아 속성 값을 설정합니다.

이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조입니다.
이진 트리는 완전히 정렬되지 않은 상태로 데이터를 저장할 수 있습니다.
이진 트리의 노드에는 키 값, 왼쪽 자식 노드 참조, 오른쪽 자식 노드 참조가 포함됩니다.

장점
이진 트리는 계층적 구조를 가지기 때문에, 배열이나 연결 리스트보다 효율적인 데이터 저장 및 검색이 가능합니다.
트리 순회를 통해 데이터를 정렬된 순서로 처리할 수 있습니다.

단점
이진 트리의 균형이 유지되지 않으면 검색, 삽입 및 삭제 작업의 성능이 저하될 수 있습니다.
균형을 유지하기 위한 추가 작업이 필요합니다.

이진 검색 트리 (Binary Search Tree)

이진 탐색 트리는 이진 트리의 특수한 형태로, 각 노드의 키 값이 왼쪽 서브트리의 키 값보다 크고, 오른쪽 서브트리의 키 값보다 작은 규칙이 적용된 트리입니다.
이 규칙 덕분에 이진 탐색 트리는 탐색, 삽입 및 삭제 작업을 빠르게 수행할 수 있습니다.

장점
정렬된 순서가 유지되기 때문에 이진 탐색을 사용하여 빠르게 데이터를 검색할 수 있습니다.
평균적인 경우, 삽입 및 삭제 작업의 시간 복잡도가 O(log N)으로 효율적입니다.

단점
최악의 경우(완전히 불균형한 트리), 이진 탐색 트리의 성능이 저하되어 O(N)의 시간 복잡도를 가집니다.
균형을 유지하기 위한 추가 작업이 필요합니다(예: AVL 트리, 레드-블랙 트리).

이진 검색 트리(Binary Search Tree)는 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드는 해당 노드의 값보다 작은 값을 가지고, 오른쪽 자식 노드는 해당 노드의 값보다 큰 값을 가지는 이진 트리입니다.

즉, 이진 검색 트리에서는 왼쪽 서브 트리의 모든 노드의 값이 해당 노드의 값보다 작고, 오른쪽 서브 트리의 모든 노드의 값이 해당 노드의 값보다 큽니다. 이러한 성질 때문에 이진 검색 트리는 빠른 탐색이 가능합니다.

이진 검색 트리에서는 노드를 탐색할 때, 탐색하려는 값과 현재 노드의 값을 비교하여, 값이 작으면 왼쪽 자식 노드로 이동하고, 값이 크면 오른쪽 자식 노드로 이동합니다. 이러한 방식으로 원하는 값을 탐색할 수 있습니다.

이진 검색 트리에서는 새로운 노드를 삽입할 때, 적절한 위치를 찾아 해당 위치에 노드를 추가합니다. 새로운 노드를 추가할 때는 노드의 값을 기준으로 삽입할 위치를 결정합니다.

이진 검색 트리는 데이터를 삽입하거나 삭제할 때, 트리의 균형을 유지하기 위해 재귀적인 방법으로 구현되는 AVL 트리, 레드-블랙 트리 등의 자료 구조와 함께 사용됩니다.

차이점

이진 트리는 데이터의 정렬에 대한 제약이 없지만, 이진 탐색 트리는 특정 규칙(왼쪽 자식 노드의 키 값 < 부모 노드의 키 값 < 오른쪽 자식 노드의 키 값)에 따라 데이터가 정렬됩니다.

이진 탐색 트리는 이진 트리의 특수한 형태로, 이진 탐색을 사용하여 빠르게 데이터를 검색할 수 있는 장점이 있습니다.
이진 트리는 깊이 우선 탐색을 사용하여 데이터를 정렬된 순서로 처리할 수 있지만, 이진 탐색 트리는 데이터가 이미 정렬된 상태로 저장되어 있어 중위 순회를 사용하여 정렬된 데이터를 얻을 수 있습니다.

이진 탐색 트리의 삽입 및 삭제 작업은 평균적으로 O(log N)의 시간 복잡도를 가지지만, 이진 트리는 균형 여부에 따라 성능이 크게 달라질 수 있습니다. 최악의 경우, 이진 트리의 삽입 및 삭제 작업은 O(N)의 시간 복잡도를 가집니다.

결론적으로, 이진 트리와 이진 탐색 트리는 각각 서로 다른 사용 사례에 적합합니다. 이진 트리는 계층적 구조를 표현하는 데 유용하며, 이진 탐색 트리는 데이터를 정렬된 상태로 저장하고 빠르게 검색하는 데 적합한 자료구조입니다. 이진 탐색 트리는 이진 트리의 확장된 형태이기 때문에, 효율적인 검색, 삽입 및 삭제 작업을 원하는 경우 이진 탐색 트리를 사용하는 것이 좋습니다.

이진 트리 순회

전위 순회(preorder traversal)
루트 노드를 먼저 출력하고, 왼쪽 서브트리를 전위 순회한 후에 오른쪽 서브트리를 전위 순회합니다.
#  전위 순회
def preorder(node):
  print(node.item, end="")
  if node.left != '.':
    preorder(tree[node.left])
  if node.right != '.':
    preorder(tree[node.right])    

중위 순회(inorder traversal)
왼쪽 서브트리를 중위 순회한 후에 루트 노드를 출력하고, 오른쪽 서브트리를 중위 순회합니다.
#  중위 순회
def inorder(node):
  if node.left != '.':
    inorder(tree[node.left])
  print(node.item, end="")
  if node.right != '.':
    inorder(tree[node.right])

후위 순회(postorder traversal)
왼쪽 서브트리를 후위 순회한 후에 오른쪽 서브트리를 후위 순회하고, 마지막으로 루트 노드를 출력합니다.
#  후위 순회
def postorder(node):
  if node.left != '.':
    postorder(tree[node.left])
  if node.right != '.':
    postorder(tree[node.right])
  print(node.item, end="")

신병규

이전 포스트