Data Structure

Red-Black 트리는 이진 탐색 트리(Binary Search Tree, BST)의 한 종류로, 각 노드의 추가적인 색깔 정보(빨강 또는 검정)를 부여하고 이를 이용해 트리의 균형을 유지하는 자가균형 이진 탐색 트리이다.    Red-Black 트리의 표현Red-Black 트리는 다음과 같은 규칙을 이용해서 트리의 균형을 유지한다.모든 노드는 빨간색 또는 검은색이다.루트 노드는 검은색이다.리프 노드(NIL)는 검은색이다. (NIL, Null Leaf : 아무 데이터도 갖고 있지 않지만 색만 검은색인 더미 노드)빨간색 노드의 자식노드는 모두 검은색이다. (검은색 노드는 빨간색과 검은색 모두 자식으로 가질 수 있다.)루트 노드와 모든 리프 노드 사이에 있는 검은색 노드의 수는 모두 동일하다.  여기서 주..

AVL 트리(Adelson-Velsky and Landis Tree)는 이진 탐색 트리(Binary Search Tree, BST)의 한 종류로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1이 되도록 유지하는 자가 균형 이진 탐색 트리이다.  AVL 트리의 표현AVL 트리는 기본적으로 이진 탐색 트리의 조건을 모두 만족해야 하며, 모든 노드의 균형 인수(Balance Factor)가 -1, 0, 1 중 하나의 값을 가져야 한다. 균형 인수는 왼쪽과 오른쪽 서브 트리의 높이 차이를 의미한다.  Balance Factor = Height(Left Subtree) - Height(Right Subtree)    AVL 트리의 특징1. 트리의 높이 균형 유지트리가 항상 균형을 유지하도록..

이진 탐색 트리(Binary Search Tree, BST)는 트리 자료구조의 한 형태로, 이진 탐색 알고리즘의 원리를 적용한 자료구조이다. 즉, 이진 탐색 트리는 이진 트리(Binary Tree)의 특성을 기반으로 하여 데이터의 효율적인 탐색, 삽입, 삭제를 가능하게 한 구조입니다. 그러나 트리의 균형이 맞지 않으면 성능이 저하될 수 있어 AVL 트리, 레드-블랙 트리와 같은 자가 균형 이진 탐색 트리가 사용되기도 한다.   이진 탐색 트리의 표현이진 탐색 트리(Binary Search Tree)는 트리 자료구조의 한 형태로 다음 조건을 만족하는 트리이다.중복 데이터를 허용하지 않는다.노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값의 노드들만 포함된다.노드의 오른쪽 서브트리에는 해당 노드의 값보다..

트리(Tree)는 데이터의 계층적인 관계를 표현하는 비선형 자료구조로 그래프(Graph)의 특별한 형태이다. 이진 트리, 이진 검색 트리, AVL 트리, 레드-블랙 트리, 힙 등 다양한 특수화된 형태의 트리가 존재하며  검색 알고리즘, 파일 시스템, 데이터베이스 등 다양한 분야에서 유용하게 활용된다.   트리의 표현 트리는 그래프의 특별한 형태로 다음과 같은 조건 만족해야 한다.사이클(Cycle)이 없는 비순환 구조 (한 노드에서 출발하여 다시 자신으로 돌아오는 경로가 존재하지 않는다.)하나의 루트(Root) 노드와 N개의 서브 트리(Sub Tree)로 구성모든 노드는 하나의 부모(Parent) 노드만 가진다.트리의 모든 노드를 순회하기 위해서는 반드시 루트(Root) 노드를 거쳐야한다.노드가 N개인 트..

스택(Stack)은 한쪽 끝에서만 요소의 삽입과 삭제가 이루어지는 선형 자료구조이다. 스택은 데이터를 바닥에서부터 쌓아 올리는 구조로 되어 있으며, 가장 마지막에 삽입된 요소가 가장 먼저 삭제된다(FIFO, First In Frist Out).  스택의 표현스택(Stack)은 데이터를 바닥에서부터 쌓아 올리는 구조로 되어 있으며, 가장 마지막에 삽입된 요소가 가장 먼저 삭제된다(FIFO, First In Frist Out). 스택에 가장 마지막에 삽입된 요소를 'Top'이라 한다.  스택의 주요 연산스택(Stack)의 주요 연산은 아래와 같다.삽입(Push) : 삭제(Pop) : 이미지 추가 예정  배열 기반 스택내용을 추가해 주세요.  리스트 기반 스택내용을 추가해 주세요.