건빵의 블로그

앞에서 언급했던 Binary Search Tree의 단점을 생각해 보자. 트리가 skewed tree 또는 지그재그 트리 형태로 자라난다면 비효율적인 자료구조가 된다. 우리의 목적은 효율적인 자료구조를 만드는 것이기 때문에 뭔가 보완이 필요하다는 것을 알수가 있다. 그래서 나오는 것들이 Balanced Tree 종류이다. 트리의 Leaf들의 Depth들이 균형 잡힌 형태로 되도록 한다. 그 예로는 B-tree, AVL tree, Red-black tree 등등이 있으며 B-tree와 AVL tree에 대해서 공부해 보았다. B-tree의 성질은 다음과 같다. 1) B-tree는 BST와 같은 Search tree를 구성하되 각 노드가 여러 개의 엔트리를 가진다.(하나의 노드에 값 여러개) 2) 노드의 엔..

트리는 이산수학에서도 다뤘기 때문에 간단히 패스하고 지나간다. 기억을 되새길겸 짚어보자면 Tree는 Acyclic connected graph이다. 그리고 몇가지 특성들을 가지는데 그것은 패쓰~ 트리는 트리 자체도 중요하지만 트리의 응용으로 나오는 다른 트리들이 중요하다. Binary Tree는 각 노드가 차일드 2개를 가지며 left랑 right로 구별되는 트리이다. Full binary Tree는 모든 leaf의 depth가 같은 트리를 말한다. Complete Binary Tree는 Full binary tree에서 맨 오른쪽 leaf부터 순서대로 제거된 형태를 띄는 것을 말한다. 그리고 오늘의 주인공 Binary Search Tree는 각 노드 값이 왼쪽 서브트리의 값들보다 크고, 오른쪽 서브트리..

큐의 정의는 다음과 같다. a linear data structure of ordered entries such that entries can be inserted at one end (called the rear) and removed at the other end (called the front) 즉, 한쪽 끝에서 삽입이 일어나고 반대쪽 끝에서 삭제가 일어나는 선형 자료구조를 의미한다. LIFO(Last-In First-Out) 성질을 띄는 스택과는 다르게 FIFO(First-In First-Out) 성질을 띈다. 먼저 들어온 것이 먼저 나가는 형태를 띄며 일반적으로 줄을 서서 차를 탄다던가 하는 것을 생각하면 된다. 스택과 마찬가지로 응용분야 또한 아주 많다. 회문 인식하는데에 있어서 스택과 같이 ..

스택은 너무나 기본적이지만 유용한 자료구조이다. 스택의 정의는 다음과 같다. a linear data structure of ordered entries such that entries can be inserted and removed at only one end (called the top) 즉, top이라고 불리는 한쪽 끝을 통해 삽입과 삭제가 이루어지는 선형 자료구조이다. 그리고 스택은 ADT로써 어떠한 형태를 가지는(배열 혹은 리스트가 될수 있다) 데이터 엔트리를 가지고 push, pop, top과 같은 operation을 이용해서 해당 자료구조를 접근하고 조작한다. 기본적인 구조 자체는 워낙 간단하기 때문에 응용분야를 살펴보는 것이 중요할 것이다. 스택의 응용분야 중 가장 대표적인 것으로는 함수..