기록하는 공간

자료구조 - Tree 정리

27 Dec 2019

Tree

비선형 자료구조로 node(vertex)와 link(edge)로 구성되어 있다. 노드는 정보를 포함하고 링크는 두 노드 간의 연결 관계이다. Tree는 최상위 노드인 root가 하나 존재해야 한다. 그리고 루트를 제외한 모든 노드는 하나의 부모를 갖게 된다.

용어

  • 노드 차수(node degree): 자식 수

  • 경로(path): 한 노드(부모)에서 다른 노드(자식)에 이르는 노드들의 순서

  • 경로 길이(node length): 한 노드에서 다른 노드로 가는 간선의 수. 시작 노드와 끝 노드가 같다면 경로의 길이는 0이다.

  • 형제 노드(sibling node): 부모가 같은 두 노드

  • 외부 노드/말단 노드(extended node): 자식이 없는 노드(차수가 0인 노드)

  • 내부 노드/가지 노드(internal node): 자식이 있는 노드(차수가 0이 아닌 노드)

  • 노드 깊이(node depth): 루트 노드에서 어떤 노드로 가는 경로의 길이. 루트 노드의 깊이는 0

  • 노드 레벨(node level): 루트 노드에서 어떤 노드로 가는 경로의 길이에 1을 더한 값. 루트 노드의 레벨은 1이며 같은 레벨을 가지느 노드의 집합을 레벨이라 함

  • 노드 높이(node height): 한 노드와 단말 노드 사이의 최대 경로 길이

  • 크기(size): 모든 노드의 수

Binary Tree

이진 트리(binary tree)는 각 노드가 자식이 없거나 두 개 이하의 자식을 가질 때를 가리킨다. 비어 있는 트리도 포함된다. 트리는 루트와 왼쪽 트리, 오른쪽 트리로 구성된다.

종류

  • Strict binary tree: 모든 노드가 두 개의 자식을 가지거나 자식이 없을 때
  • Full binary tree: 모든 노드가 두 개의 자식을 가지고, 자식이 없는 노드가 같은 레벨에 있을 때
  • Complete binary tree: 모든 자식이 없는 노드가 높이 h나 h-1에 있고 순열에서 빠진 숫자가 없을 때

구현하기

이진 트리를 구현하는 가장 간단한 방법은 리스트를 이용하는 것이다. 리스트에 루트, 왼쪽 트리, 오른쪽 트리가 들어간다. insertLeft는 왼쪽 트리에, insertRight는 오른쪽 트리에 추가하게 된다.

def BinaryTreeList(r):
  return [r, [], []]

def insertLeft(root, newBranch):
  t = root.pop(1)
  if len(t) > 1:
    root.insert(1, [newBranch, t, []])
  else:
    root.insert(1, [newBranch, [], []])
  return root

def insertRight(root, newBranch):
  t = root.pop(2)
  if len(t) > 1:
    root.insert(2, [newBranch, [], t])
  else:
    root.insert(2, [newBranch, [], []])
  return root

def getRootVal(root):
  return root[0]

def setRootVal(root, newVal):
  root[0] = newVal
  
def getLeftChild(root):
  return root[1]

def getRightChild(root):
  return root[2]
참조

파이썬 자료구조와 알고리즘 다양한 예제로 학습하는 데이터 구조와 알고리즘

Related Posts