sundori DevStory

ㅊ2023.11.14 - [알고리즘] - [알고리즘] 트리 5 - 균형 이진 탐색 트리(AVL) [알고리즘] 트리5 - 균형 이진 탐색 트리(AVL) 목차 2023.11.13 - [알고리즘] - [알고리즘] 트리 4 - 이진 탐색 트리 [알고리즘] 트리4 - 이진 탐색 트리 이진 탐색 트리 이진트리는 트리를 효율적으로 구현하고 관리하기 위해서 일정한 조건으로 정 sun-dori.tistory.com 목차 히프 히프는 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키잡이 가장 작은 노드를 찾을 때 필요한 자료구조이다. 키값이 가장 큰 노드를 찾기 위한 히프를 최대 히프(Max Heap), 키값이 가장 작은 노드를 찾기 위한 히프를 최소 히프(Min Heap)라 한다. 히프의 개념 최대 히프 최..

목차 스레드 이진트리(Thread Binary Tree) 이전 글 이진 트리의 순회에서는 부모 노드와 자식 노드의 이진트리 기본 구조에서 각 레벨에서 순환적으로 반복되어 전체 트리가 구성되는 구조이다 보니 각 노드에서의 순회 연산을 재귀호출을 이용하여 순환적으로 반복하여 전체 트리에 대한 순회를 처리하였다. 이러한 방식은 함수 구현을 함에 있어서 간단하지만, 수행의 성능 측면에서는 시스템적으로 스택을 사용하여 호출과 복귀를 관리해야하고 이진트리의 하위 레벨로 내려갈수록 재귀호출의 깊이가 깊어지므로(스택에 쌓이는 양이 많아짐) 매우 비효율적일 수 있다. 따라서 이러한 문제점들을 생각하여 재귀호출이 없어도 순회가 가능토록한 것이 스레드 이진트리이다. 스레드 이진트리의 특징 스레드 (Thread) 스레드 이진..

목차 01 트리의 이해 트리(Tree)는 자료들이 리스트, 스택 큐와 같은 1:1 관계의 선형 구조가 아니라 1:n 관계의 비선형 자료구조이며, 계층 자료구조이다. 트리의 구성 요소 노드 Node: 트리를 구성하는 원소(자료)를 노드(Node)라고 한다. 간선 Edge: 노드를 연결하는 선. 루트 Root 노드, Level 0: 트리의 시작 노드. 형제 Sibling 노드: 같은 부모 노드를 가진 자식 노드들. 조상 Ancestor 노드: 루트 노드까지 이르는 경로에 있는 노드는 모두 그 노드의 조상. (노드 K의 조상은 F, B, A) 서브 트리 Subtree: 자식 노드들은 독립하여 새로운 트리 구성이 가능 따라서 각 노드는 자식 노드 수만큼 서브트리를 가짐. (노드 B의 자손 노드는 서브트리 E의 ..