2022.06.16 - [자료구조] - 트리(Tree) 개념 및 구현 트리(Tree) 개념 및 구현 트리는 말 그대로 나무와 유사한 자료구조를 말한다. 이는 사회나 컴퓨터공학에서 흔히 사용되고 있다. 예를 들어보자면 회사 조직도가 있다. 회사의 사장이 나무의 뿌리에 해당한다고 하면, 사 rooftoproom-whale.tistory.com 우리는 앞서 트리에 대한 기본적인 내용에 대해 알아봤다. LCRS 트리는 N개의 자식을 가지는 트리였는데 지금 알아볼 이진 트리는 자식을 최대 2개까지 가질 수 있는 트리이다. 그래서 이름도 이진(Binary) 이다. 자식이 많으면 좋은게 아닌가? 왜 2명으로 제한을 둘까? 라는 의문이 생기는데 이 이진트리를 통해 탐색과 수식 처리하는 알고리즘이 존재하기때문에 이진 트..
트리는 말 그대로 나무와 유사한 자료구조를 말한다. 이는 사회나 컴퓨터공학에서 흔히 사용되고 있다. 예를 들어보자면 회사 조직도가 있다. 회사의 사장이 나무의 뿌리에 해당한다고 하면, 사장 밑에 있는 각 부서의 부장들은 뿌리에서 뻗어 나온 가지라고 할 수 있다. 부장 밑에 있는 차장, 과장, 대리 등은 부장이라는 가지에서 뻗어 나온 잔 가지가 된다. 컴퓨터 공학에서도 활용도가 높은 자료구조인데 우선 운영체제의 파일 시스템이 트리 구조로 이루어져 있고, HTML이나 XML 문서를 다룰 때 사용하는 DOM(Document Object Model)도 트리 구조이다. 이뿐만 아니라 검색 엔진이나 데이터베이스도 트리 자료구조에 기반해서 구현된다. 트리의 구성 요소 트리는 그림과 같이 뿌리(Root), 가지(Bra..
스택은 데이터의 입력과 출력이 이루어지는 공간이 top 하나뿐이고 FILO or LIFO 인 자료구조이다. 큐는 이와 반대로 입력과 출력 공간이 따로 존재하고 제일 먼저 들어간 데이터가 제일 먼저 나오는(FIFO) 자료구조이다. 그렇다면 큐를 왜 사용하는 것일까? 데이터 입력이 폭주하는 경우를 생각해보자. 먼저 입력받은 데이터의 처리가 안 끝났는데 그 뒤에 새로운 데이터가 계속 입력되면 그 데이터는 보관할 곳이 없기때문에 모두 버리게 된다. 이때 밀려드는 데이터를 저장하기위해 큐를 쓴다. 우리는 이런 구조를 자바에서 쉽게 찾아볼 수 있다. 바로 버퍼(Buffer)가 큐를 사용한다. 큐의 주요 기능 : 삽입과 제거 큐의 기본적인 구조는 아래와 같다. 큐는 삽입은 후단(rear), 제거는 전단(front) ..
스택이란 스택은 뭔가를 아래에서부터 위로 쌓아 얹어 올리도록 하는 자료구조이다. 스택은 오직 top에서 삭제, 추가가 이루어지기 때문에 중간 인덱스에 데이터 변경을 할 수 없다. 특정위치의 데이터를 추가/삭제 하고싶다면 해당 위치까지 pop을 해야한다. 따라서 스택은 가장 마지막에 들어간 데이터가 제일 먼저 나오고(Last In - First Out) 가장 먼저 들어간 데이터는 가장 나중에 나오게(First In - Last Out)된다. 스택의 주요 기능 삽입 제거 스택의 대표적인 기능은 위와 같이 2가지 연산이 있다. 먼저 삽입은 스택 위에 새로운 요소를 쌓는 작업이다. 제거는 스택에서 최상위 요소를 걷어내는 작업이다. 스택 구현 방식 스택을 구현하는 방식으로는 아래와 같이 2가지가 있다 배열을 이용..
더블 링크드리스트란? 링크드리스트의 탐색 기능을 개선한 자료구조이다. 링크드리스트는 노드를 찾으려면 헤드에서 테일 방향으로만 탐색할 수 있었는데 더블 링크드리스트는 양방향으로 탐색이 가능하다. 아래는 더블 링크드리스트의 노드 구조이다. class Node { private Object data; private Node prevNode; private Node nextNode; public Node(Object newData) { this.data = newData; this.prevNode = null; this.nextNode = null; } } 주요 연산 링크드리스트와 동일하며 이전 노드를 처리하기 위한 구현이 더 추가될 뿐이다. 노드 생성 Node CreateNode(Object newData) ..
링크드리스트란 기본적으로 배열을 선언할 때 new int [10]으로 크기를 지정해서 선언한다. 허나 배열의 용도에 따라 계속 크기가 변할 수 있다면 결과를 예상해 크기를 선언하기엔 메모리 낭비가 발생하여 애매모호합니다. 이때 유연하게 크기를 바꿀 수 있는 자료구조를 사용해야 하는데 그중에 하나가 링크드리스트이다. 노드 링크드리스트 내의 각 요소는 노드(Node)라고 부른다. 이 노드에는 데이터를 보관하는 필드와 다음 노드와의 연결고리 역할을 하는 포인터로 이루어져 있다. 링크드리스트는 아래처럼 리스트의 첫 번째 노드인 헤드와 마지막 노드인 테일을 갖고 있다. 이런 구조라면 데이터의 크기를 미리 알지 못해도 된다. 데이터가 늘어날 때마다 노드를 만들어 테일에 붙이면 되기 때문이다. 리스트 사이에 노드를 ..
