이진트리1 이진검색트리 자료구조 : 이진검색트리 (Binary Search Tree) 이진트리(Tree)의 특수한 형태로 자주 사용되는 트리로서 이진검색트리 (Binary Search Tree)가 있다. 이진검색트리는 이진트리의 모든 속성을 가짐과 동시에 중요한 또 하나의 속성을 가지고 있는데, 그것은 특정 노드에서 자신의 노드보다 작은 값들은 모두 왼쪽에 있고, 큰 값들은 모두 오른쪽에 위치한다는 점이다. 또한 중복된 값을 허락하지 않는다. 따라서 전체 트리가 소트되어 있는 것과 같은 효과를 같게 되어 검색에 있어 배열이나 이진트리처럼 순차적으로 모든 노드를 검색하는 것(O(n))이 아니라, 매 검색마다 검색영역을 절반으로 줄여 O(log n)으로 검색할 수 있게 된다. 하지만 노드들이 한쪽으로 일렬로 기울어진 Skewed .. 2013. 4. 25. 이전 1 다음