Programming/Data Structure10 [C++] 이진탐색트리 (BS트리) Feat. Splay, AVL, BB 트리 이번 포스트에서는 탐색에 최적화된 이진탐색트리의 개념과 성질, 그리고 코드 구현 방법까지 알아보려 한다. ▣ 이진탐색트리 Binary Search Tree (BS 트리) 트리에서 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진트리 형식의 자료구조다. 특정 데이터 검색, 노드 삽입, 삭제에 가장 효과적인 이진트리다. 탐색에 최적화된 이진트리다. key: 이진 트리에서 노드의 데이터 ● 규칙 왼쪽 서브트리에 있는 모든 노드의 key값은 내 key값보다 작다. 오른쪽 서브트리에 있는 모든 노드의 key값은 내 key값보다 크다. ● 특성 같은 순서 데이터로 BS 트리를 여러가지 만들 수 있다. 루트 노드를 뭐로 잡느냐에 따라 다양하게 구성된다. ● 노드 struct KNode{ struct KNode.. 2020. 9. 29. [개념] 선택트리 selection tree - 승자트리 winner tree, 패자트리 loser tree 선택트리에 대해 알아보겠습니다. ▣ 선택 트리 선택트리는 합병 정렬에 사용하는 특수한 구조를 가지는 트리 자료구조다. 그럼 합병정렬이란 어떤 알고리즘인가? ● 합병정렬 각각 차례로 정렬된 n개의 데이터 리스트들을 완전한 순서를 유지하는 하나의 리스트로 병합하는 과정이다. 각 리스트의 최솟값(최댓값)들을 비교해야 하기 때문에 한 번 합칠때마다 (n-1)번의 비교횟수가 필요하다. -> 낭비 그!래!서! 선택 트리를 이용하여 비교횟수를 줄인다. 누군가가 선택트리 중 하나인 승자트리라는 것을 고안해냈다. 선택트리에는 승자트리와 패자트리가 있다. 각각의 개념에 대해 알아보자. ● 승자 트리 winner tree (선택 트리 중 하나) 부모 노드가 두 자식 노드보다 작은 값을 가지는 완전이진트리다. 작은 값이 승자.. 2020. 9. 23. [C++] 힙 코드 구현 방법 heap heap에 대해 배우기 전에 우선순위 큐 개념부터 잡고 가야한다. ▣ 우선순위 큐 priority queue ● 큐 먼저 들어간 데이터가 먼저 삭제되는 자료구조 형태다. 먼저 줄을 선 사람이 먼저 서비스를 받는 구조다. ● 우선순위 큐 대기 리스트에서 항상 우선순위가 높은 사람이 먼저 서비스를 받는 구조다. 삭제할 때만 우선순위를 고려해서 삭제한다. 먼저 들어온 순서 상관없이. 예를 들어서, 버스를 타려고 줄 서 있는데, 다리가 불편한 아이에게 양보해서 먼저 탈 수 있게 하는 방법이다. ● 우선순위 큐 배열 구현 ▶ 작동방식 삭제 명령이 실행되면 큐의 대기열(저장된 데이터) 중 우선순위가 가장 높은 데이터가 삭제된다. 나머지 데이터들이 어떤 순서로 저장되는 지는 문제가 되지 않는다. ▶ 데이터 삭제(De.. 2020. 9. 22. [C++] 이진트리 코드 구현 방법 binary tree ▣ 트리 ● 트리의 특징 검색이 편리하다. 논리적 계층을 이루고 있다. 계급적 특성을 가진다. ● 트리의 구조 ▷ 노드 트리의 항목으로 트리에 저장되는 데이터들을 말한다. ▷ 부모노드-자식노드 상하 계층구조로 이루어지고 직접 연결된 노드 관계를 가진다. 상위계층 - 부모노드, 하위계층 - 자식노드 ▷ 루트노드 트리에서 최상위 노드 ▷ 서브트리 부모노드 삭제하면 생기는 트리들 ▷ 리프노드 트리의 맨 아래에 위치한, 자신의 서브트리가 없는 노드 ● 차수 루트노드의 진입차수 = 0 리프노드의 진출차수 = 0 루트노드 외의 모든 노드의 진입차수 = 1 ● 레벨 노드의 레벨: 루트부터 해당 노드까지 이어지는 간선의 길이 루트노드의 레벨 = 0 ● 높이 트리의 높이 = 루트로부터 가장 멀리 있는 노드까지 이어진 간.. 2020. 9. 21. [C++] 원형 연결 리스트 코드 구현 방법 Circular linked list ▣ 연결리스트 종류 ● 단순 연결 리스트 (Simply linked list) ▷ 하나의 링크만 있고, 각각 노드의 링크는 후행 노드만을 가리키는 구조다. 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 문제점이 있다. 자세한 코드 구현 방법 등 단순 연결 리스트 관련 포스트는 아래 링크를 참고하세요. 2020/09/10 - [Programming/Data Structure] - [C++] 연결리스트 Linked list 코드 구현 방법 [C++] 연결리스트 Linked list 코드 구현 방법 리스트가 뭘까? 리스트는 '일정한 순서'의 나열로 어떤 정의에 의해서 결정된 '논리적인 순서'의 나열이다. 리스트의 순서는 데이터가 저장되는 .. 2020. 9. 11. [C++] 이중연결리스트 코드 구현 방법 Doubly linked list 이 포스트에서는 이중연결 리스트를 C++ 코드로 구현하는 방법을 다룬다. ▣ 연결리스트 종류 ● 단순 연결 리스트 (Simply linked list) ▷ 하나의 링크만 있고, 각각 노드의 링크는 후행 노드만을 가리키는 구조다. 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 문제점이 있다. 자세한 내용은 아래 포스트를 참고하세요. 2020/09/10 - [Programming/Data Structure] - [C++] 연결리스트 Linked list 코드 구현 방법 [C++] 연결리스트 Linked list 코드 구현 방법 리스트가 뭘까? 리스트는 '일정한 순서'의 나열로 어떤 정의에 의해서 결정된 '논리적인 순서'의 나열이다. 리스.. 2020. 9. 10. 이전 1 2 다음 반응형
