KalelPark's LAB

AVL tree란? - Binary SearchTree의 경우, 한쪽으로 노드가 쏠릴 수 있다. 트리에서 특정 값을 찾으려면 O(N)의 시간이 필요하다. 하지만, biasedTree를 AVL tree로 구성하면, 어떤 노드를 탐색하든 O(logN)에 탐색하는 것이 가능하다. - Binary Search Tree의 속성을 가집니다. - 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다. - 높이 차이가 1보다 커지면 Rotation을 활용하여, 균형을 맞춰, 높이 차이를 최소화합니다. - 삽입, 검색, 삭제의 시간 복잡도가 O(logN) 이다. (N : 노드의 개수) Balance Factor(BF) - AVL트리는 균형이 무너졌는지에 대해 판단할 때, Balance Factor라는 것을 활용합니다. A..

Binary Search Tree 이란? 이진 탐색 트리(binary search tree)란 연결리스트(linked list)를 결합한 자료구조의 일종이다. 이진 탐색(binary search)의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제가 가능합니다. 이진 탐색(binary search)의 경우 탐색에 소요되는 계산복잡성은 O(longN)으로 빠르지만, 입력 및 삭제가 불가능하고, 연결리스트의 경우 입력, 삭제에 필요한 복잡도는 O(1)이지만, 탐색을 하는데, O(N)의 시간이 걸리는데, 탐색과 입력 및 삭제를 효율적으로 활용해보고자 하는 것이, 이진 탐색 트리(Binary Search Tree)입니다. 시간 복잡도 Common case : O(h) Worst case : O(n) ..