tree2 [자료구조] Red-Black 트리 [ 이진 탐색 트리(BST, Binary Search Tree)의 단점 ] 균등 트리 : 노드 개수가 N개일 때 O(logN) 편향 트리 : 노드 개수가 N개일 때 O(N) 이진 탐색 트리는 최악의 경우 한쪽으로 편향된 트리일 때 O(N) 시간이 걸린다. 이 말은 모든 노드를 한 번씩 다 확인해줘야 한다는 의미이다. 이러한 단점을 개선한 균형 트리인 Red-Black 트리에 대해서 알아보자. 🔴 Red-Black 트리 ⚫️ 이진 탐색 트리의 단점을 개선하기 위한 자료구조 이진 탐색 트리(BST)의 한 종류 스스로 균형(balancing) 잡는 트리 BST의 worst case의 단점을 개선해서 모든 경우에 O(logN) 모든 노드는 red 혹은 black ✔️ 5가지 속성 모든 노드는 red 혹은 bla.. 2023. 3. 2. [자료구조] 트리 (Tree) 비선형 구조, 그래프의 특수한 형태 중 하나이다. 1. 개념 그래프 정점(vertex)과 간선(edge)로 이루어져 있는 자료구조 방향이 있는 간선을 포함한 그래프를 유향 그래프 처음 시작한 정점으로 다시 돌아오는 경로를 '사이클' 트리 특별한 성질을 갖는 그래프를 트리로 각 노드가 하나의 부모 노드와 간선으로 연결되어있는 자료구조 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개. • 트리의 간선들은 모두 방향성을 갖는다. • 어떤 정점을 가리키는 정점의 개수는 최대 1개이다. • 어떤 정점에서 다른 정점으로 이동할 수 있는 경로는 1개다. • 트리는 사이클을 갖지 않는다. 디렉터리(폴더) -> 트리 구조 예시 이진 탐색 트리 (Bi.. 2022. 7. 29. 이전 1 다음 반응형
