BinarySearchTree1 [Algorithm] 6-2. Binary Search Tree 저번 시간에는 어려운 개념인 amortized analysis라는 알고리즘 분석 방법에 대한 내용에 대해 알아보았다. 이번 시간에는 binary search tree, 그 중에서도 Red-Black Tree에 대해 알아보도록 하겠다. ● Binary Search Trees - binary search tree는 주로 dictionary라는 추상 자료형을 표현하기 위해 주로 사용된다. 임의의 key를 가진 원소를 삽입, 삭제, 탐색할 수 있고, 최악수행시간은 O(n)이다. - 하지만 balanced binary search tree일 경우에는 최악수행시간이 O(log(n))일 것이다. - 순서가 있는 집합에서의 key를 가지는 노드를 가진 트리이고, 자식은 최대 2개이다. - 왼쪽 서브트리의 모든 키들은 .. 2020. 4. 28. 이전 1 다음
