avl트리1 [비선형 자료구조] - 균형 이진탐색트리 앞서 이진 탐색 트리는 O(logN) 이라는 시간 복잡도를 가져, 탐색 측면에서 이점이 있는데, 삽입 순서에 따라 한쪽으로 치우친 사향트리가 될 경우, O(N)의 시간 복잡도를 갖게 되어, 이점이 사라진다. 따라서 이러한 케이스에 대한 이진 탐색 트리의 단점을 보완하기 위해, 균형을 잡는 여러 방법들 중 AVL 트리에 대해 학습해보고자 한다. 이진 탐색 트리의 기본적인 특징은 여기서 참고! 🌳 균형 이진 탐색 트리란? ▪ 노드의 삽입과 삭제을 진행하면서, 균형을 자동으로 맟춰주도록 동작한다. ▪ 모든 노드의 좌우 서브 트리 높이가 2이상 차이 나지 않는 트리 ▪ 트리의 양쪽 높이 차이가 2이상 날 경우 : 삽입, 삭제, 탐색 등의 시간 복잡도 증가 ex. 사향트리 - 시간복잡도 : O(N) ▪ 종류에는 .. 2023. 12. 26. 이전 1 다음
