본문 바로가기

개발/자료구조

(3)
[자료구조] B 트리 안녕하세요.오늘은 B 트리 에 대해 포스팅 합니다.B 트리 는 이진 탐색 트리의 일종으로 탐색 성능을 높이기 위해 균형있게 높이를 유지하는 균형 트리 입니다.균형 이진 탐색 트리는 대표적으로 RedBlackTree, AVL 트리 같은것이 있습니다. 두 트리가 독특한 규칙으로 높이를 유지 하는것처럼 B 트리도 자신만의 규칙이 존재합니다.특이한점은, 이진 트리가 아니라는 점 입니다. 규칙에 따라 노드의 자식 노드 개수는 2개 이상이 될 수 도 있습니다. B 트리 장점B 트리의 장점은 크게 3가지가 존재합니다.균형 트리데이터 로드 효율성 균형 트리의 장점은 이진 탐색 트리 에서도 살펴봤다시피, 노드들이 한쪽으로 치우쳐 연결 리스트의 형태가 되는것을 방지하여 검색 효율을 높일 수 있다는 장점이 있습니다. 데이터..
[자료구조] 이진탐색트리 안녕하세요. 오늘은 이진 탐색트리 에 대해 포스팅 합니다. 이진 탐색트리 란이진 탐색트리 는 이진 탐색(Binary Search)의 아이디어를 채용한 자료구조 입니다. 이진 탐색은 원소가 정렬되어 있다는 조건아래, 정렬된 특징을 이용해 반씩 쪼개가며 검색을 합니다. 그러므로, 검색 횟수가 획기적으로 낮아지는 특징이 있습니다. 이는, 이진 탐색트리도 똑같이 원소가 정렬된 형태로 지니고 있어야 하고 반씩 쪼개가며 검색을 할 수 있는 구조를 갖추고 있어야 함을 의미합니다. 그러면... 이진 탐색 사용하면 되는거 아닌가요?그렇다면, 이진 탐색트리는 이진 탐색을 사용하는 배열 자료구조보다 나은점이 무엇일까요? 아시다 시피, 배열은 조회에 강점이 있는 자료구조 입니다. 그렇다 보니, 검색만 한다고 가정할 때는 트리..
[자료구조] 트리(Tree) 안녕하세요.오늘은 자료구조 트리(Tree)에 대해 포스팅 합니다.필수적으로 알아야 할것들만 정리하였습니다.트리구조에 대해 대략적으로 설명하므로, 특정 용어나 개념들은 따로 찾아봐야 합니다. 트리(Tree) 란위 본문의 그림과 같이 노드 와 간선으로 이루어진 것을 그래프(Graph) 라고 합니다.트리는 이러한 그래프 의 일종 입니다. 아래의 규칙을 따르는 그래프를 트리라고 일컫습니다.사실 규칙을 외울 필요는 없고, 이런 형태구나 정도로 기억하면 될 거 같습니다. 트리 규칙특정 노드는 오직 하나의 조상 노드와 N 개의 자식 노드와 연결됩니다.특정노드에서 조상노드, 자식노드는 레벨의 차이가 반드시 1이어야 합니다.C 노드는 하나의 조상 노드인 A와 2개의 자식 노드인 G , H와 연결됩니다. 여러 노드가 한 ..