전체 글 (79) 썸네일형 리스트형 이진탐색트리(Binary Search Tree) 지금가지 트리(Tree)와 이진트리(Binary Tree)를 설명했다. 이번에 설명 할 이진탐색트리는 이진트리로 자료가 구성되는 트리중 하나인데 이진트리는와 다른점은 특정 규칙(rule)에 의해 자료가 저장되어 진다. 이전에 설명한 이진트리는 왼쪽 자식 노드(left node)와 오른쪽 자식 노드(right node)를 추가 할 때 추가될 데이터 정보와 상관없이 넣고 추가하고 싶은대로 추가하였다. 사실 어떻게 보면 이진트리 모양을 만들기 위해 중구난방으로 자료를 추가했던 것이다. 이렇게 되면 자료의 탐색(or 검색)이 비효율적으로 된다. 자료를 탐색할 규칙이 없으니 당연히 복잡해지고 오래 걸리 수 밖에 없는 것이다. 반면 이진탐색트리는 이름에서 유추할 수 있듯이 탐색을 위한 트리 자료구조이라 자료 검색에.. 이진트리(Binary Tree) 트리(Tree) POST에서는는 자식노드의 개수에 상관없이 계층적으로 구성되어 있는것을 구현해보았다. 이런 트리중 좀 특별한게 있는데 바로 이진트리(Binary Tree)이다. 이진트리란 노드가 최대 2개이하의 자식노드를 가지는 트리 자료구조로 자식노드는 각각 왼쪽 자식 노드(left child node)와 오른쪽 자식 노드 (right child node)로 구성된다. ▲[출처] https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm 위 그림은 A 노드는 왼쪽에 B노드 오른쪽에 C 노드를 자식으로 가지고 있으며 B노드는 왼쪽에 D노드를 오른쪽에 E노드를 자식으로 가지고 있고 모든 노드의 자식노드는 2개이하로 구성.. 우선순위큐(Priority Queue) 스택(Stack)은 가장 늦게 들어간 자료가 가장 빨리 나오게되는(LIFO) 구조이고 큐(Queue)는 가장 먼저 들어간 자료가 가장 빨리 나오게 되는 (FIFO) 구조를 가진다고 각 POST에서 설명했었다. 그럼 우선순위큐는 무엇일까 ? 우선순위큐는 말 그대로 큐에서 자료를 빼는데 우선순위가 높은 것부터 빼내기 위한 자료구조이다. 우선순위큐가 실생활(real worl)에서 어떤 경우에 필요할까? 예를들어 은행(bank)에서 업무 처리 프로세스를 기준으로 설명해보겠다. 은행에서는 일반적으로 업무 처리는 먼저온 손님부터 처리를 해준다. 즉, 은행에 도착해서 순서표를 뽑은 순서대로 손님을 처리해주니 업무처리를 위한 프로그래밍 자료구조로 큐가 적당해 보인다. 하지만 예외가 있는데 은행장과 친분이 있거나 거금의.. 힙(Heap) 이진트리(Binary Tree)와 이진탐색트리(Binary Search Tree)차이가 노드 추가시 노드의 왼쪽 서브트리에는 그 노드의 키값 보다 작은 값들이 오른쪽 서브트리는 노드의 키값보다 큰 값들이 와야하는 규칙이 있었던 것처럼 힙도 이진트리 중 -> 완전이진트리(complete binary tree)로 노드가 구성되어야 하고 노드 추가시 몇 가지 규칙이 있다. 완전이진트리(complete binary tree)란 마지막 레벨을 제외한 나머지 노드가 꽉 차 있어야 하며(마지막 레벨을 제외하고 포화이진트리이어야 하며), 마지막 레벨의 노드는 왼쪽 부터 차있어야 한다고 이진트리(Binary Tree)에서 설명한 적이 있다. 원래 힙은 데이터 원소 중에서 최대값(MAX) 및 최소값(MIN)을 찾아내는 연.. 트리(Tree) 트리(Tree)는 자료를 부모와 자식관계로 표현할 수 있는 자료구조이다. 그 모양이 마치 나무가 자라 가지를 친 모양과 비슷하다 하여 트리라 부른다. 그래프(Graph)의 일종이기도 하고 용도나 저장하는 구조에 따라 다양한 변종들이 있다. 다양한 변종들을 알아보기 전에 트리의 개념을 파악하고 구현해 볼 것이다. 우리 주변에 트리 자료구조를 가진 것은 무엇이 있을까 ? 대표적으로 회사의 조직도를 생각해 볼수 있다. 그리고 탐색기나 파인터(MAC)처럼 폴더와 파일 구조도 일종의 트리이다. 컴퓨터에서 이런 트리 자료구조에 사용되는 용어(terms)는 아래와 같다. 루트(root)노드 : 최상위노드 (ex : A) 단말(leaf) or 터미널(terminal) 노드 : 자식노드가 없는 최하단 노드 이다. (ex.. 스택(Stack) 배열(Array)과 연결리스트(LinkedList)를 잘 이해했으면 스택을 이해하고 구현하는데 어렵지 않다. 위키백과(https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D)에 보면 스택에 대해 이렇게 설명하고 있다. 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이이다. 그 접근 방법은 언제나 목록의 끝(last)에서만 일어난다. (자료접근시 중간에 접근하는 일이 없고 항상 끝에서만 일어난다는 소리다.)스택은 한 쪽 끝에서만 자료를 넣거나(push) 뺄 수(pop) 있는 구조로 되어 있고 이런 걸 선형 구조(LIFO - Last In First Out)으로 되어 있다라고 말한다. 자료를 넣는 것을 '밀어넣는다' 하여 푸시(push)라고 하고 반대로 넣어둔 자료를.. 큐(Queue) 배열(Array)과 연결리스트(LinkedList)를 잘 이해했으면 큐(Queue)를 이해하고 구현하는데 어렵지 않다. 위키백과에 보면 큐 자료구조에 대해 다음과 같이 설명하고 있다. 큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는(LIFO) 스택과는 반대되는 개념이다. 너무 정확하게 설명해서 더 이상 설명할 것이 없다. 스택과 다른점은 먼저 들어간 놈이 먼저 나온다는 것이다. 일상적으로 이런.. 이전 1 ··· 7 8 9 10 다음
