728x90 트리3 2-3 트리 (2-3 Tree) 2-3 트리란 무엇일까?2-3 트리는 이진 탐색 트리의 불균형 문제를 해결하고자 고안된 트리다.한 노드가 3개의 자식 노드를 가질 수 있기 때문에 이진 탐색 트리는 아니다.분할(Split)과 병합(Merge)을 통해 불균형 문제를 해결한다.항상 양쪽 서브트리 간 높이 차가 0인, 완전 균형 탐색 트리다. 왜 2-3 트리를 배울까?2-3 트리 또한 AVL 트리와 마찬가지로 그 자체로는 현재 잘 쓰이지 않는다.하지만, 2-3 트리의 균형을 유지하는 방식은 현재 데이터베이스 관리를 위해 주로 사용하는 B 트리에서도 사용된다. 결론적으로, 분할과 병합을 통한 트리 균형 유지 방법을 학습하기 위해 2-3 트리를 배운다. 2-3 트리의 조건0. 트리의 조건을 상속받는다.1. 왼쪽 서브트리의 모든 노드는 현재 노드의.. 2024. 7. 9. 이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리(binary search tree)란 무엇일까?이진 탐색 트리는 이진 검색을 사용할 수 있도록 노드가 연결된 트리 자료구조다. 왜 이진 탐색 트리를 사용할까?이진 탐색 트리는 이진 검색을 사용하여 빠르게 데이터를 찾을 수 있기 때문에 검색, 범위 검색을 위해 사용된다. 배열 또한 이진 검색을 사용할 수 있다. 그러나, 왜 굳이 이진 탐색 트리를 사용할까? 배열은 데이터 삽입, 삭제 시마다 오름차순이 깨질 수 있기 때문에 이진 검색을 사용하기 전 항상 정렬이 필요하다. 하지만 이진 탐색 트리는 항상 정렬 상태를 유지하고 있기 때문에 정렬 없이 이진 검색을 사용할 수 있다. 따라서 데이터의 삽입, 삭제가 많은 환경에서 이진 검색을 사용하기 위해 추가적인 정렬이 필요없는 이진 색 트리를 사용한.. 2024. 6. 19. 트리 (Tree) 트리(Tree)란 무엇일까?트리(Tree)는 데이터를 계층적으로 표현하는 자료구조다. 왜 트리를 사용할까?트리는 주로 검색 연산을 많이 해야 할 경우에 사용된다.트리가 검색에 특화된 이유는 계층 구조를 사용하기 때문이다. 트리의 조건1. 하나의 루트 노드를 가진다.2. 사이클이 존재하지 않는다.3. 모든 노드는 하나의 부모 노드를 가진다.4. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.트리에서 사용되는 용어앞으로의 편리한 설명을 위해 알아둘 용어이며, 시간을 들여 따로 외울 필요는 없다.용어설명노드 (Node)데이터를 저장하는 공간간선 (Edge)노드 간의 연결최상위 노드 (Root node)부모가 없는 트리의 최상위 노드내부 노드 (Interior node)최상위 노드도 말단 노드도 아닌 .. 2024. 6. 18. 이전 1 다음 728x90