AVL Tree

AVL Tree

• Data structure
• 2020년 10월 23일

BST (이진 탐색 트리)를 기반으로 둔 Tree. 어떤 노드를 기준으로 하더라도 왼쪽자식의 깊이와 오른쪽 자식의 깊이 차이가 1을 넘지 않는 트리 1. 용어 개념 정리 균형치 (Balance factor) : 자식노드의 깊이 차이 ( 왼쪽 서브트리의 높이 – 오른쪽 서브트리의 높이 ) BF는 -1, 0, 1이 기준이며, 이 범위를 벗어난다면, 그 트리의 균형은 깨진것이다. 2. 특징 BST의 모든 특징을 갖는다...