algorithm. Balanced Binary Tree

Balanced Binary Tree

Balanced Binary tree는 연산을 수행하는데 있어서 효율적입니다. Height-balanced trees로도 알려져 있고, HB(k)로 정의 됩니다. 이때 balance factor로 알려진 k는 왼쪽과 오른쪽 서브트리의 높이 차이입니다.

Balanced binary tree 조건:

1. 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이는 1보다 작습니다.
2. 각 노드의 왼쪽 서브트리는 Balanced binary tree입니다.
3. 각 노드의 오른쪽 서브트리는 Balanced binary tree입니다.

예시

balanced binary tree

fully balanced binary tree

참고 사이트

What is a Balanced Binary Tree and How to Check it?
Balanced Binary Tree