tree3 [자료구조] 탐색 트리 (Search Tree) 탐색 트리: 탐색을 위한 트리 기반의 자료 구조 일상생활이나 컴퓨터에서 탐색은 매우 중요한 역할을 한다. 우리가 원하는 데이터를 찾을 때 반드시 거쳐야 하는 과정이 탐색이다. 앞서 이진 탐색을 배웠지만, 레코드의 삽입과 삭제가 빈번히 일어나는 테이블에 대해서는 그다지 효율적이라고 말할 수 없었다. 해싱을 사용하면 매우 효율적이지만 메모리를 많이 사용할 뿐더러 해시 충돌과 오버플로 문제를 처리해야 하므로 매우 복잡하다는 단점이 있다. 그래서 고안된 방안이 탐색에 트리 구조를 이용하는 것이다. 즉 탐색을 위한 이진 트리 기반의 자료 구조가 고안되었는데, 이를 이진 탐색 트리라고 한다. 이진 탐색 트리의 특성 모든 노드는 유일한 키를 갖는다. 왼쪽 서브 트리의 키들은 루트의 키보다 작다. 오른쪽 서브 트리의 .. 2024. 1. 8. [자료구조] 트리 3. 힙 트리 힙 트리: 여러 개의 값들 중에서 가장 크거나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조 힙은 최대 힙과 최소 힙으로 나눌 수 있으며, 모든 힙 트리는 아래의 두 성질을 만족해야 한다. 모양 성질: 완전 이진 트리의 모양을 나타내야 한다. 힙 성질: 최대 힙 또는 최소 힙의 특성을 갖는다. 최대 힙의 특성: 각 노드에 저장된 값은 그 자식 노드에 저장된 값보다 크거나 같다. 최소 힙의 특성: 각 노드에 저장된 값은 그 자식 노드에 저장된 값보다 작거나 같다. 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 이번에는 최대 힙을 가지고 다뤄보도록 하겠다! 최대 힙의 구현 최대 힙.. 2024. 1. 8. [자료구조] 트리 2. 이진 트리의 활용 앞서 이진 트리의 개념과 표현법에 대해 간략하게 공부했다. 그럼 이렇게 이진 트리를 만들고 난 후, 어떻게 트리의 데이터에 접근할 수 있을까? 바로 순회를 이용하는 것이다. 순회란 트리에 속하는 모든 노드들을 한 번씩 방문하여 트리의 데이터에 접근하는 것으로, 트리에서 가장 기본적인 연산이다. 이진 트리의 표준 순회에는 전위 순회, 중위 순회, 후위 순회 3가지 방법이 있다. 이들은 루트의 왼쪽 서브 트리, 오른쪽 서브 트리를 각각 어떤 순서로 방문하느냐에 따라 구분된다. 루트를 방문하는 작업을 V, 왼쪽과 오른쪽 서브 트리를 방문하는 작업을 각각 L과 R이라고 할 때, 각 순회들을 구현하는 방법들은 아래와 같다. 전위 순회: VLR 중위 순회: LVR 후위 순회: LRV 순회의 구현 def preord.. 2024. 1. 8. 이전 1 다음 반응형
