728x90 이진탐색트리2 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. AVL 트리 (AVL Tree) AVL 트리란 무엇일까?AVL 트리는 이진 탐색 트리의 불균형 문제를 해결하고자 고안된 트리다.최초로 고안된 균형 이진 탐색 트리이며, 회전을 통해 불균형 문제를 해결한다.완벽히 균형 잡힌 트리는 아니며, 최대 1의 높이 차가 발생할 수 있다. 왜 AVL 트리를 배울까?현재는 최적화된 다른 이진 탐색 트리가 많아 AVL 트리는 자체는 잘 사용되지 않는다.하지만, 현재 자바의 트리 자료구조인 Red-Black Tree 등 다양한 균형 이진 탐색 트리들이AVL 트리에서 최초로 고안된 회전이라는 개념을 사용하고 있다. 결론적으로, 회전이라는 개념을 이해하기 위해 AVL 트리를 배운다. AVL 트리의 조건0. 이진 탐색 트리의 조건을 상속받는다.1. 어떤 노드도 Balance Factor의 절댓값이 1을 초.. 2024. 6. 21. 이전 1 다음 728x90