알고리즘 2-3 Tree(2-3 트리)
페이지 정보
작성일 23-03-19 22:48
본문
Download : 23트리(09).hwp
자식이 둘이면 2-노드 그리고 자식이 3이면 3-노드라고 한다.
알고리즘 2-3 Tree(2-3 트리)
1. 2-3-Tree 란?
(1) 모든 중간 노드들의 자식 수가 2또는 3이 되어야 한다. 이의 성립을 위해서는 세가지 조건을 만족하여야 한다.
(2) 모든 단말노드가 같은 레벨에 있어야 한다. 또한 노드에 있는 큰 값은 중간 부분트리에 있는 노드들의 값보다는 크고, 오른쪽 부분트리에 있는 노드들의 값보다는 작아야 한다.
4. 2-3-Tree의 검색과 코드
-9504_01.jpg)
-9504_02_.jpg)
-9504_03_.jpg)
-9504_04_.jpg)
알고리즘 2-3 Tree(2-3 트리)
설명
알고리즘 2-3 Tree(2-3 트리)
순서
AVL-Tree가 균형 트리(Balaced Tree)를 지향하였다면, 2-3-Tree는 완벽 균형 트리(Perfect Binary Tree)를 지향한다. AVL-Tree와 마찬가지로 효율적인 검색을 위한 균형 트리의 구조를 지닌다.
2. AVL-Tree와의 차이
AVL-Tree는 높이 부분에 있어서 거의 최소의 높이를 유지시켜 준다는 advantage(장점) 을 지니고 있지만 복잡도의 면에서 생각해 보면 삽입과 삭제는 어렵게 다가올 수도 있다 이러한 AVL-Tree에 비해 2-3-Tree는 간단하게 이의 구현이 가능하다.
(3) 자식 수가 둘이라면 노드에 있는 값은 왼쪽 부분트리에 있는 노드들의 값보다 크고, 중간 부분트리에 있는 노드들의 값보다는 작아야 한다. 물론 각 연산의 시간 복잡도는 O(logn)을 유지한다.
Download : 23트리(09).hwp( 91 )
5. 2-3-Tree의 삽입
알고리즘, 트리, 23트리, tree, 23tree, 균형 트리, 단말노드
2. AVL-Tree와의 차이
레포트 > 공학,기술계열
3. 2-3-Tree의 형태
1. 2-3-Tree 란?
다. 자식 수가 셋인 경우에는 노드에 있는 작은 값은 왼쪽 부분트리에 있는 노드의 값보다는 크고, 중간 부분트리에 있는 노드들의 값보다는 작아야 한다.
