반응형 척척학사/자료구조11 BS, Splay, AVL, BB 이진 탐색 트리(BS트리) 이진 탐색트리는 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진트리를 말하고 특정 데이터의 검색과 노드의 삽입, 삭제 처리에 효과적이다. 트리를 구성할 때 데이터의 타색으로 고려하여 구성되므로 탐색에 최적화되어 있다. 이때 키값이라는 값이있는데 탐색, 삽입, 삭제 연산에서 비교 대상이 되는 값이다. 이진트리노드의 데이터를 대표하는 값이나 노드를 특정할 수 있는 값이 키이다. 이진 탐색 트리의 정의에는 노드 Vi의 키를 Ki라고 할때 각 노드 Vi가 2가지를 만족하는 이진트리이다. V의 왼쪽 서브 트리의 모든 노드의 키값이 Vi의 키값보다 작다. V의 오른쪽 서브트리에 있는 모든 노드의 키값은 Vi의 키 값보다 크다. 이러한 이진트리를 중위순회하면 정렬된 순서 숫자가 작.. 2023. 11. 6. 선택트리,숲,이진트리 개수 ::= 자료구조 선택트리 합병정렬 차례로 정렬된 a개의 데이터 목록을 순서를 유지하는 하나의 리스트를 만드는 과정이다. 일반적인 데이터목록이 a개 인경우 a-1번 비교를 통해서 데이터 목록에서 가장 작은 값이나 가장 큰 값을 결정할 수 있다. 선택트리를 이용하여 비교 횟수를 줄일 수 있다. 이러한 합병정렬에서 선택트리는 가장 위에 있는 데이터를 자식노드에 놓고 작은 것을 찾아서 작은 것은 위로 부모로 올라가는 개념으로 생각하면 될 것 같다. 승자 트리라고 하며, 각노드가 두 자식노드의 작은 값을 갖는 완전전이진트리로 작은 값이 승자가 되어 올라가는 토너먼트 경기와 비슷하다. 트리의 각노드는 두 자식노드 값의 승자를 자신의 값으로 하고 결과적으로 루트의 값이 트리에서 가장 작은 값이 된다. 그러면 첫 번째 단계에서의 비교.. 2023. 11. 5. 자료구조 힙(heap) 우선순위 큐 힙은 쌓아 올린 더미라고 생각할 수 있고 항상 가장 위에 있는 것을 우선 꺼내는 구조를 상징한다. 힙을 설명하기 위해 우선 우선순 순위 큐를 알아야 하는데 큐는 배웠듯이 먼저 들어간 데이터가 먼저 삭제되는 자료구조이다. 대기열리스트에서 항상 우선순위가 높은 것을 먼저처리하는 것이고 이것은 항상 꼭대기에 있다고 생각하면 됩니다. 우선순위 큐 역시 큐여서 들어가는 위치인 rear과 나오는 위치인 front가 정해져 있다. 우선순위 큐의 작동방식은 삭제 명령이 실행되면 데이터 중 가장 작은 값 혹은 가장 큰 값이 삭제된다. 나머지 데이터들은 어떤 순서로 저장이 되든 상관은 없다. 힙 힙의 정의 힙은 피라미드 모양으로 쌓아 올린 더미와 유사한 모양이다. 항상 가장 위에 있는 것을 우선 꺼내는 구조이.. 2023. 10. 29. 자료구조, 스레드 트리 스레드 트리 스레드 트리를 이야기하기 앞서 배웠던 원형 연결리스트를 떠올려보면 마지막 노드의 링크노드를 첫 노드를 가리키게 해서 순환하게 했다. 결국 스레드 트리도 잎노드에서 빈 공간으로 있는 NULL링크를 활용하는 것이다. 앞서 이진트리를 순회할 때 방문하지 않고 지나 온 노드들은 스택에 저장하여 관리한다. 이는 컴퓨터가 하는 일을 더 많게 하는데 스트레드 트리는 정해진 순회방법에 따른 방문순서를 유지하는 스레드라는 포인터를 사용하는 방법이다. there : (실등을) 꿰다. 이진트리의 노드 순회는 전위순회, 중위 순회, 후위순회가 있다고 했는데 스레드라는 포인터를 잎노드의 NULL링크에 사용하여 트리순회를 편하게 하는 것이 목적이다. 스레드 : 순회방법에 따라 방문순서를 유지하는 포인터 스레드 트리 .. 2023. 10. 25. 이전 1 2 3 다음 반응형
