Data structures (with python) - 8.Tree - 8.6 Unbalanced Tree

Data structures (with python) - 8.Tree - 8.5 Unbalanced Tree

 

An unbalanced binary tree is one that is not balanced.

 

https://www.programiz.com/dsa/balanced-binary-tree

 

 

데이터 구조에서 트리는 노드들이 계층적으로 연결된 구조를 말합니다. 

 

저번 장에서 말한 균형 트리(Balanced Tree)는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 일정한 범위 내에 있는 트리를 말합니다. 

 

이번에 살펴볼 불균형 트리(Unbalanced Tree)는 이런 조건을 만족하지 않는 트리를 의미합니다.

예를 들어, 이진 탐색 트리(Binary Search Tree, BST)는 모든 노드에서 왼쪽 서브트리에 있는 노드들의 값이 해당 노드의 값보다 작고, 오른쪽 서브트리에 있는 노드들의 값이 해당 노드의 값보다 크다는 조건을 만족하는 트리입니다. 이런 트리에서 삽입이나 삭제 연산이 반복적으로 일어나면 높이 차이가 점점 커져서 결국 불균형 트리가 될 수 있습니다. 이런 트리에서는 탐색 연산의 성능이 떨어지게 됩니다.

하지만, 불균형 트리는 탐색 성능이 떨어지므로 실제로는 잘 사용하지 않습니다. 대신에 AVL 트리나 레드-블랙 트리 등의 균형 트리를 사용하면, 트리의 균형을 유지하면서도 효율적인 탐색 성능을 보장할 수 있습니다. 이런 균형 트리도 불균형 트리를 기반으로 하되, 삽입이나 삭제 연산 후에 트리의 균형을 복원하는 추가적인 연산을 수행합니다.

이렇게 균형 트리를 사용하면, 탐색, 삽입, 삭제 연산의 시간 복잡도를 일정하게 유지할 수 있어서 데이터베이스 시스템이나 파일 시스템 등에서 많이 사용됩니다. 

따라서 실제로는 균형 트리를 구현하고 활용하는 방법을 배우는 것이 더 유용합니다.