Algorithm/KBro Study

Binary Search Tree란? Binary(이진) Search(탐색) Tree(트리)가 합쳐진 것으로, 즉, 이분화된 탐색을 위한(혹은 특화된) 트리 자료구조라는 뜻이다. 그렇다면 트리가 무엇일까? 위와 같은 구조를 Tree 구조라고 하는데, 거꾸로 보면 나무같이 생겨서 그렇게 부른다고 한다. 여기서 몇 가지 알아야 할 것이 있는데, 그 부분은 아래와 같다. 부모 노드(parent node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 높은 노드를 의미 (ex. F의 부모노드 : B) 자식 노드(child node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 낮은 노드를 의미 (ex. C의 자식노드 : G, H) 루트 노드 (root node) : 일명 뿌리 노드라고 하며 루트 노드는..

LinkedList란 말그대로 각 노드들이 한줄로 연결되어있는 구조리스트(자료의 주소값으로 서로 연결되어있는 구조)를 말한다. 여기서 노드들은 데이터와 포인터를 가지고 있는데, 이때 노드의 포인터가 이전노드와 다음 노드와의 연결을 담당한다. 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있다. 그러므로 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋다. LinkedList를 그림으로 나타내면 아래와 같다.(파란색 부분이 포인터,..