완전 이진 트리3 힙 Heap 힙(Heap) 혹은 히프는 완전 이진 트리 종류 중 하나 입니다. 히프는 여태까지 트리를 계속 해서 연결 자료구조로 구현한 것과는 다르게 1차원 배열을 이용해서 구현할 수 있는 자료구조 이기도 합니다. 1. 힙 Heap 힙은 이진 트리의 노드들 중에서 키값이 가장 큰 값또는 가장 작은 값을 찾기 위한 자료구조입니다. 이때 가장 큰 값을 찾으면 최대 힙, 가장 작은 값을 찾으면 최소 힙이라고 합니다. 또 다른 특징은 힙은 같은 키값을 가진 노드를 가질 수 없다는 점 입니다. 그래서 최대 힙에서는 가장 큰 키값을 가진 노드가 루트 노드가 되고, 최소 힙에서는 가장 작은 키값을 가진 노드가 루트 노드가 됩니다. 힙을 1차원 배열로 구현하기 때문에 배열의 인덱스를 통해 트리간의 부모 자식관계를 쉽게 알 수 있다.. 2021. 10. 2. AVL 트리 이진 탐색 트리는 트리 구조마다 연산시간이 천차만별입니다. 다음 그림처럼 같은 노드를 가져도 구조에 따라서 연산시간이 다르게 됩니다. 같은 3개의 노드, 같은 요소인데도 8이라는 요소를 탐색 할 때 왼쪽 편향 트리는 노드를 2번 거치는 연산을 하고, 오른쪽 그림의 이진 트리는 오른쪽으로 한 번 이동하는 연산만을 수행하면 됩니다. 이처럼 노드가 늘어날수록 그 차이가 커집니다. 이처럼 노드가 늘어나서 불균형해질수록 이진 트리의 연산횟수가 증가하는 단점이 있는데, 이 단점을 보완한 트리를 균형 이진 탐색 트리 혹은 균형 트리라고 합니다. 이 균형 트리에는 B 트리, AVL 트리 2-3-4 트리 등이 있는데 오늘은 이 중에서 AVL 트리에 대해서 알아보려고 합니다. 1. AVL 트리 Adelson-Velskii.. 2021. 10. 1. 이진 트리 Binary Tree 1. 이진 트리 트리마다 자식 노드 수가 제각각이라면, 연산에 대해서 오버헤드가 굉장히 버겁고, 구현도 복잡해지게 됩니다. 그래서 이런 문제를 해결하기 위해 트리의 구조를 일정하게 만드는데, 그 구조 중 대표적인 것이 이진 트리입니다. 이진 트리란, 모든 노드의 차수를 2 이하로 제한 시켜 트리의 차수가 2차 이하인 트리를 의미합니다. 이진 트리는 노드의 차수가 2이하 이므로, 자식 노드가 0개, 1개, 2개까지는 모두 허용이 됩니다. 여기서 트리의 모든 노드의 차수가 2인 트리를 완전 이진 트리라고 하고, 차수가 2미만인 트리가 하나라도 있으면 이진 트리라고 합니다. 다음 그림을 이진 트리라고 합니다. 모든 노드의 차수가 2이하임을 볼 수 있습니다. 2. 일반 트리를 이진 트리로 바꾸기 일반 트리는 이.. 2021. 9. 20. 이전 1 다음 300x250
