자료구조/트리(Tree) (6) 썸네일형 리스트형 [자료구조] 레드 블랙 트리(Red Black Tree) - 코딩밥상 레드 블렉 트리란? 앞서 공부한 것처럼 순수한 이진 탐색 트리는 가지들이 불균형하게 자라는 경우가 많고 이는 이진 탐색 트리의 높이를 높여서 검색 효율을 심각하게 저하시키기 때문에 문제가 됩니다. 데이터가 아무리 많이 입력되어도 이진 탐색 트리가 균형 있게 성장해서 그 높이가 최소한으로 유지되도록 하는 특별한 이진 탐색 트리가 바로 레드 블렉 트리입니다. 그 방법으로 노드를 빨간색과 검은색으로 구분하여 이러한 이름이 붙여진 것입니다. 이 특별한 트리의 구조체 먼저 알아보자면, typedef struct tagRBTNode{ struct tagRBTNode* Parent; struct tagRBTNode* Left; struct tagRBTNode* Right; enum {RED, BlACK} Color;.. [자료구조] 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리란? '이진 탐색'을 위한 트리이자 탐색을 위한 '이진 트리'입니다. 다시 말해 이진 탐색 트리는 '이진 탐색'을 위한 '이진 트리'입니다. 앞 서 배운 이진 탐색으로는 배열에만 사용 가능한 알고리즘입니다. 데이터의 처음과 끝을 알아야 하고 순식간에 데이터의 중앙 요소를 계산할 수 있어야 하며 중앙 요소에 접근 할 수 있어야 합니다. 하지만 링크드 리스트는 위와 같은 작업들이 불가능한 자료구조입니다. 헤드와 테일 사이의 '중앙 요소'는 알 수 없기 때문입니다. 이러한 문제를 해결하여 링크드 리스트처럼 동적으로 노드를 추가하거나 제거할 수 있으면서 이진 탐색 알고리즘도 사용할 수 있도록 하는 자료구조가 바로 '이진 탐색 트리' 입니다. 이진 탐색 트리의 표현은 생각보다 간단합니다. 이진 트리.. [자료구조] 분리 집합(Disjoint Set) - 코딩밥상 분리 집합이란? 집합의 정의는 특정 조건에 맞는 원소의 모입입니다. 그 중 분리 집합은 서로 공통된 원소를 갖지 않는, 즉 교집합을 갖지 않는 복수의 집합을 뜻합니다. 따라서 분리 집합에는 교집합이 존재 할 수 없습니다(공집합). 때문에 분리 집합은 소속 관계가 분명해야 하는 데이터를 다룰 때 아주 유용합니다. 예들들어 원소 또는 개체가 어느 집합에 소속되어 있는지 정보를 바탕으로 무언가를 하는 알고리즘에 유용합니다. 분리 집합 구현하기 앞 서 살펴본 분리 집합을 트리를 활용하여 구현해 보겠습니다. 주의할 점은 보통의 트리는 부모가 자식을 가리키는 포인터를 갖는 것과 다르게 반대로 자식이 부모를 가리키는 포인터를 갖습니다. 즉 뿌리 노드는 집합 그 자체이고, 뿌리 노드 자신을 포함한 트리 내의 모든 노드.. [자료구조] 수식 트리(Expression Tree) - 코딩밥 수식 트리란? 그 이름 그대로 수식을 표현하는 이진 트리이므로 수식 이진 트리라고 부르기도 합니다. 하나의 연산자당 2개의 피연산자가 필요하기 때문에 수식 트리는 다음 두 가지 규칙을 가집니다. 피연산자는 잎 노드이다. 연산자는 뿌리 노드 또는 가지 노드이다. 또한 이러한 방식으로 뿌리 노드를 연산자로, 왼쪽 서브 트리의 결과값과 오른쪽 서브 트리의 결과값을 파연산자로 하여 마지막 연산을 해주면 답이 됩니다. 즉 수식 트리는 하위 수식 트리의 계산 결과값을 피연산자로 삼아 계산하여 결과를 얻습니다. 이러한 수식 트리의 성질에 적합한 노드 순회 방법은 후위 순회입니다. 수식 트리 구현하기 -알고리즘 수식을 뒤에서부터 앞쪽으로 읽어나가며 토큰을 취한다. 수식에서 제일 마지막에 있는 토큰으로 뿌리 노드를 생성.. [자료구조] 이진 트리(Binary Tree) - 코딩밥상 이진 트리(Binary Tree)란? 앞서 트리에 대한 기본적인 이론을 공부했으니 가장 중요하게 쓰이는 특정 트리들을 정리해보겠습니다. 먼저 이진 트리입니다. 한 문장으로 정의하자면, 하나의 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리입니다. 즉 모든 노드의 자식 노드 수는 0,1,2 중 하나입니다. 이진 트리의 종류 -포화 이진 트리(Full Binary Tree) 잎 노드를 제외한 모든 노드가 자식을 둘씩 가진 이진 트리. 따라서 포화 이진 트리는 잎 노드들이 모두 같은 깊이에 위치합니다 -완전 이진 트리(Complete Binary Tree) 잎 노드들이 트리의 왼쪽부터 차곡차곡 채워진 트리. 직관적으로 설명하면, 포화 이진 트리가 되기 전 단계에서 노드가 왼쪽 순서로 차곡차곡 채워진 트.. [자료구조] 트리(Tree) - 코딩밥상 트리의 개념 트리는 이름 그대로 나무를 닮은 자료구조입니다. 뿌리가 있고 뿌리에는 가지가 뻗어 나오며 가지 끝에는 잎이 달립니다. 이러한 구조는 우리들의 일상생활 뿐만 아니라 컴퓨터 과학에서도 활용도가 매우 높습니다. 운영체제의 파일 시스템과 문서를 다룰 때 사용하는 DOM등이 트리 구조로 이루어져 있습니다. 또한 검색 엔진이나 데이터베이스도 트리 자료구조에 기반해서 구현됩니다. 트리 구조의 용어 정리 -구성요소 트리는 뿌리(Root),가지(Branch),잎(Leaf) 세 가지 요소로 이루어져 있습니다. 모두 또같은 노드이지만 트리에서 어디에 위치하는가에 따라 불리는 이름이 달라질 뿐입니다. 가장 위에 있는 노드가 뿌리, 뿌리와 잎 사이에 있는 모든 노드가 가지 그리고 끝에 매달린 노드를 잎이라고 부릅.. 이전 1 다음
