Red Black Tree 레드 블랙 트리 레드블랙 트리는 자가균형이진탐색 트리(self-balancing binary search tree)로써, 대표적으로 연관배열(associative array) 등을 구현하는데 쓰이는 자료구조이다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을때 Θ(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다. 모든 노드가 빨간색 혹은 검은색인 이진 탐색 트리 모든 속성은 Extended Binary Search Tree*를 기반으로 한다 : 각 Null 포인터는 외부 노드(External node)로 바뀜 Black child(외부 노드 포함)에 대한 포인터는 검은..

이진검색트리는 저장과 검색에 평균 Θ(log n)시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다. 균형이 많이 깨지면 Θ(n)에 근접한 시간이 소요될 수도 있다. 그래서 고안해 낸 것이 **균형잡힌 이진검색트리(Balanced Binary Search Tree)**이다. 균형잡힌 이진검색트리는 최악의 경우에도 이진트리의 균형이 잘 맞도록 유지한다. 균형잡힌 이진검색트리로 대표적인 것은 AVL트리와 레드블랙트리다. AVL Tree Adelson-Velsky and Landis Tree 극단적으로는 n개의 노드가 크기 순으로 일렬로 늘어뜨려져 높이 또한 n이 되는 경우도 이진 탐색 트리에 해당된다. 결과적으로 이진 탐색 트리의 계산복잡성은 O(n)이 되는데, 이것으로는 탐색 속도가 O(..

💡 이진 탐색 트리는 이름에서 알 수 있듯이, 삽입이나 삭제보다는 탐색에 주 목적을 둔 자료구조이다. Search Tree 탐색 트리 skip lists와 hash table들과 같거나 그 이상의 성능을 가짐 사전을 구현하는 데에 이상적인 구조 순차적 또는 등급별 데이터 접근에 이상적 💡 빈출! 이진 트리와 이진 탐색 트리의 차이점 - 이진 트리 : 노드의 최대 Branch가 2인 트리 - 이진 탐색 트리 : 이진 트리에 추가적인 조건이 있는 트리 ⇒ 조건 : 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음. Binary Search Tree 이진 탐색 트리 이진 탐색 트리는 트리가 비어있지 않은 경우 다음과 같은 속성을 만족한다. 모든 노드 x에 대하여,오른쪽 서..

Threaded Binary Tree의 특징 트리의 노드는 순서대로 채워진다. 트리의 다른 노드에 대한 thread라는 포인터로 null 링크를 변경한다 자식 노드와 연결되지 않는 링크는 중위 선행자 (Inorder Predecessor) 또는 중위 후행자 (Inoder Successor)와 연결된다. 중위 선행자 또는 중위 후행자가 없는 노드의 링크는 가상의 노드 head를 가리킨다. 장점 : 트리 전체의 모든 링크를 활용한다. 중위 순회의 편의성이 증대된다. Thread의 이용 ptr -> leftChild = null인 경우, ptr → left_child를 ptr의 중위 선행자를 가리키도록 변경 중위 선행자(Inorder Predecessor): 해당 노드 바로 앞에 나온 노드 ptr -> rig..

📌 Questions BST와 Binary Tree에 대해서 설명하세요. (N사 전화면접) Tree가 무엇인가? 이진검색트리에서 검색속도가 가장 느린케이스는 데이터가 어떻게 저장되어 있는 경우인가? Tree의 개념 비선형 구조로, 원소들 간에 1:n 관계를 가지는 자료구조 💡 데이터를 어떻게 삽입하고 삭제할 것인지에 대해 관심이 많았던 선형 자료구조에 비해 비선형 자료구조는 데이터의 삽입/삭제보다는 '표현'에 포커스가 맞춰져있다. 트리를 이용해서 무엇인가를 저장하고 꺼내기 보다 트리는 '무엇인가를 표현하는 도구'로 자주 사용되기 때문이다. 드디어 큐를 마지막으로 선형(linear)자료구조 내용이 마무리되고 이제부터는 비선형 자료구조에 대한 내용이 시작된다. 비선형 자료구조의 대표적인 자료구조는 바로 트리..

본 포스팅은 하냥이의 개발일지 스터디에 참여하며 정리한 문서입니다. 📌기술면접 질문 Q. Linked List에 대해 설명해보세요. 더보기 A. Linked List는 데이터와 다음 데이터를 가리키는 정보를 저장하고 있는 자료구조입니다. 데이터를 추가 하기에 좋지만 데이터를 찾을(탐색) 때 순차적으로 찾아야 하기 때문에 검색 하는 것은 느립니다. 그래서 데이터의 입출력이 많을 때 Linked List를 사용 하는 것이 좋습니다. Q. Array와 Linked List의 차이가 무엇인가요? (N사 전화면접) 더보기 Array List는 데이터들이 순서대로 늘어선 배열의 형식을 취하고 있지만, Linked List는 자료의 주소값으로 서로 연결된 형식을 가지고 있다. - Array List - 원하는 데이터..

Questions Stack과 Queue의 차이점은 무엇인가요? (N사 전화면접) Priority Queue의 동작 원리가 어떻게 되나요? (N사 전화면접) 큐 / 우선순위 큐의 개념에 대해 설명해보세요. 큐 삽입(enqueue) / 삭제(dequeue) 함수를 배열 / 링크드리스트로 구현하라. 스택 2개로 큐 1개를 구현한 MyQueue 클래스를 구현하라. 큐(Queue)의 개념 큐는 배열과 함께 가장 쉬운 자료 구조 중 하나이다. 큐는 컴퓨터에서 가장 핵심적인 소프트웨어 중 하나인 운영체제에서도 많이 쓰인다. 또, 인터넷에서 네트워크 기능에서도 많이 사용된다. Queue의 사전적 의미는 1. (무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미한다. 즉, 가장 먼저 넣은 데..

📌기술면접 질문 Q. 스택(Stack)에 대해 설명하고 예제소스를 구현해보아라 Q. 스택과 큐의 차이는 무엇일까요? Q. 화이트보드에 큐로 스택을 구현해 보라. (넥슨) Q. 스택과 링크드리스트와 리스트의 차이점을 설명해 보세요. (네이버) Q. 스택 오버플로우가 왜 일어나는가? Stack 스택 : 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조 가장 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out)방식을 사용 스택공간이 가득찼을 때 데이터를 더 넣으려고 할 경우 프로그램에 오류가 발생하는 것을 Overflow 상태라고 하며, 반대로 스택 저장공간에 데이터가 없는데 프로그램에서 스택에서 데이터를 꺼내려고 할 경우 프로그램에 오류가 발생하는 것을 Underflow..