목록2021/11 (1)

개발 및 기술 블로그

[자료구조] 이진탐색, Splay, AVL, BB트리

1. 이진 탐색 트리 -이진 탐색트리 :== 트리에서 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진트리 -특정 데이터를 검색하고, 노드를 삽입/삭제하는 응용 문제에 가장 효과적인 트리 -탐색에 최적화된 이진 트리 -키: 이진 트리 노드의 데이터 이진 탐색 트리의 특징 - 왼쪽 서브트리에 있는 모든 노드의 자식 키값은 작다. - 반대로 서브트리에 있는 모든 노드의 자식 키값은 크다. 이진 탐색 트리의 단점 - BS 트리의 성능은 트리의 구조와 특정 노드에 접근할 확률에 영향을 받음 - 트리의 성능이 구조에 영향을 받기 때문에 최적의 BS 트리구조를 결정하기 어려움 좋은 성능의 BS 트리를 구축하는 방법(휴리스틱) - 자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 놓는다. - 트리가 균형이..
Computer Science 2021. 11. 3. 08:56
이전 Prev 1 Next 다음