6.md

Tree, Binary Tree, BST, AVL Tree에 대해서 설명해주세요.

트리(Tree)는 계층적인 자료를 표현하는 데 이용되는 자료구조입니다.

이진 트리(Binary Tree)는 모든 노드가 최대 2개의 서브 트리를 가지고 있는 트리를 말하며, 서브 트리 또한 모두 이진 트리입니다. 이진 탐색 트리(Binary Search Tree)는 데이터 탐색에 이용하기 위해 이진 트리를 조금 변형한 것으로, 노드에 key-value 형태로 데이터가 저장되며 key를 기준으로 정렬되어 있습니다. 이진 탐색 트리는 보통의 경우 O(log2N)의 시간 복잡도를 가지지만 편향된 이진 탐색 트리의 경우 O(N)의 시간 복잡도를 가질 수 있습니다.

높이 균형 이진 트리(AVL Tree)는 이진 트리의 높이 불균형 문제를 해결하고자 나온 자료구조로, 두 서브 트리의 높이 차이가 2 이상일 수 없다는 특징을 가집니다. 따라서 O(log2N)의 시간 복잡도를 가집니다.

참고 자료

• https://kpuls.tistory.com/39
• https://en.wikipedia.org/wiki/AVL_tree
• https://en.wikipedia.org/wiki/Binary_search_tree
• https://stackoverflow.com/questions/2734692/avl-tree-vs-b-tree

💬 크루들의 질문

트리랑 그래프의 차이는?

트리는 그래프의 서브셋입니다.

트리는 일반 그래프와 다르게

• 두 개의 노드 사이에 딱 하나의 간선을 가집니다.
• 사이클이 존재하지 않는 방향 그래프입니다.
• 부모-자식의 계층 관계를 가집니다.

AVL Tree를 사용해본 경험이 있나요?

직접적으로 AVL Tree를 사용해본 경험은 없는 것 같습니다.