Data structures (with python) - 8.Tree - 8.3 Full Binary Tree

Data structures (with python) - 8.Tree - 8.3 Full Binary Tree

 

💡 A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no children. It is also known as a proper binary tree.

정이진 트리는 모든 부모 노드/내부 노드가 두 개의 자식을 갖거나 전혀 갖지 않는 특별한 유형의 이진 트리입니다. 적정 이진 트리라고도 합니다.

 

정 이진 트리(Full Binary Tree)는 모든 노드가 0개 또는 2개의자식 노드를 가지는 이진 트리를 말합니다.

즉, 한 노드가 자식 노드를 가진다면, 그것은 반드시 두 개의 자식 노드를 가져야 합니다. 이러한 특징 덕분에 정이진 트리(Full Binary Tree)는 균등하게 분포된 트리 구조를 가집니다.

 

 

In Python

정 이진 트리를 파이썬에서 구현하는것은 이진 트리 구현과 그다지 다르지  않습니다.

노드 클래스 제작, 트리를 구성하는 노드를 연결하는 방식으로 마찬가지이다.

다만, 정 이진 트리의 조건에 맞게 모든 노드가 0개 또는 2개의 자식 노드를 가져야 한다는 점을 주의해야 한다.

 

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

# 노드 생성
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

위의 코드는 1을 루트 노드로 가지는 정 이진 트리(Full Binary Tree)를 만드는 예시입니다.

 

활용

정이진 트리(Full Binary Tree)는 이진 힙(binary heap)과 같은 자료 구조의 구현에 사용됩니다.

이진 힙 은 정이진 트리(Full Binary Tree)를 기반으로 하여, 데이터의 최소값 또는 최대값을 빠르게 찾는 데 사용하는 자료구조 입니다.

 

(차후추가)