잡초의 일지

ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/ 이진탐색트리(Binary Search Tree) · ratsgo's blog 이번 글에서는 자료구조의 일종인 이진탐색트리(Binary Search Tree)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님, 그리고 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정 ratsgo.github.io 이진 탐색 트리는 Heap과 혼란이 올 수 있다. 이진탐색 트리는 말 그대로 "탐색" Search 하는데에 적합하다. 이런 식으로 오른쪽에는 노드보다 큰값, 왼쪽에는 작은값을 써서 찾고자 하는것을 빠르게 찾을 수 있다.

연결 표현 방법 ( linked representation )과 연결 리스트 ( linked list ) 순차 (sequential) 표현의 문제점은 연결 표현으로 해결할 수 있다. 순차표현 : 연속된 리스트의 원소들이 일정한 거리만큼 떨어져 저장. 원소들의 저장 순서가 리스트에 표현된 순서와 동일 연결 표현 : 각 원소들이 메모리 내 어떤 곳에나 위치 가능. 원소들의 저장 순서가 리스트에 표현된 순서와 반드시 똑같을 필요가 없다. 연결 표현 방법에서는 각 리스트의 원소들에 대하여 다음 원소를 가리키는 포인터(pointer) 또는 링크(link)가 연관되어 있다. 일반적으로 연결 리스트는 노드들을 포함하는데, 이 노드들은 데이터 필드와 링크 필드로 이루어져 있다. 주로 이런 구조로 이루어진다. link ..

힙 (Heap) Heap은 완전 이진트리 (complete binary tree)를 기본으로 한다. 완전 이진트리란 이런 식으로 왼쪽정렬된 모습을 하는 트리이다. 자식이 추가되면, 오른쪽에 들어온다. 최대힙, 최소힙 ( Max_Heap , Min_Heap ) 힙에는 최대힙과 최소힙이 있다. 최대힙은 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 한다. 최소힙은 그 반대이다. 이것이 최대힙의 예시이다. 이진 탐색 트리 (Binary Search Tree)와 헷갈릴 수 있으니, 조심해야 한다. 힙의 표현 힙은 배열이나 linked list로 만들 수 있다. 힙 노드 추가 (insert) 노드를 추가할 땐 오른쪽으로 추가한다. 이런 방식이다. 힙 노드 삭제 (delete) 힙 노드를 삭제할 때는 root..