카샤의 만개시기

2-3 트리는 노드 하나에 2개의 값이 있을수 있으며 링크는 3개가 있을수 있다. 2-3 트리는 다음과 같은 특징을 가지고 있다. 각 노드는 2개 이하의 아이템과 3개 이하의 링크로 구성된다. 노드 안의항목은 Item1 < Item2 크기로 정렬된다. 각 링크는 SubTree1 < Item1 < SubTree2 < Item3 < SubTree3 와 같은 순서로 링크된다. AVL 트리가 총 6개의 노드를 나타낼때 높이는 2이지만 2-3트리를 이용하여 나타낼때는 높이가 1이 된다. 따라서 AVL트리와 2-3트리의 시간복잡도를 나타내자면 각각 O( log2(N) ), O( log3(N) )이 되어 2-3트리가 성능이 더 높음을 알수 있다. 하지만 2-3트리가 여러 가지 트리 중 성능이 최고라고 할수만은 없다...

이진트리는 한쪽으로 치우친 형태로 트리 구조가 만들어 질수 있는데 그렇게 되면 트리 구조가 아닌 일반적인 연결 리스트와 별 차이가 없게 되기 때문에 이진 트리의 장점이 사라지게 된다. AVL 트리는 이러한 전체 트리의 구조가 균형이 맞도록 하는 트리다. 즉, 쏠린 트리처럼 트리 구조가 한쪽으로 쏠리는 것을 막아 트리 구조의 균형을 맞춤으로써 조회 성능을 O(logN)으로 유지할수 있는것이다. AVL 트리는 다음과 같은 특징이 있다. 균형도(Balance Factor)라는 개념이 있는데, 이는 각 노드의 왼쪽 노드와 오른쪽 노드의 차이를 말한다. 리프 노드의 균형도는 0이다. 균형도는 '왼쪽 자식 트리의 높이 - 오른쪽 자식 트리의 높이'로 계산한다. 왼쪽 자식 노드와 오른쪽 자식 노드의 균..

트리 순회 알고리즘 (Tree Traversal Algorithm) 전위 순회(Pre-order traversal) : ABDECFG 중위 순회(In-order traversal) : DBEACFG 후위 순회(Post-order traversal) : DEBFGCA 단계 순회(Level-order traversal) : ABCDEFG