10000COW

2-3-4 트리란? 탐색트리 중 하나로, 이진 트리가 아니다. 즉, 자식 노드가 2개보다 많을 수 있다. 특징으로 1. 이름처럼 자식 노드의 개수는 2개 또는 3개 또는 4개를 가질 수 있다. (즉, 최소 2개 ~ 최대 4개) 2. 모든 leaf 노드가 같은 level에 존재한다. 3. 삽입 시, leaf 노드에 삽입한다. 삽입 추가할 key가 root부터 leaf 노드까지 내려가면서, 4-노드이면 split하면서 내려간다. split할 때 중간 값은 부모 노드로 무조건 올라갈 수 있는데, 그 이유는 key가 내려오면서 4-노드인 경우 split을 이미 해놨기 때문이다. split하는데 O(1)이 걸리고, 최악의 경우 leaf노드까지 내려가면서 매번 split 해야하므로(log n번), 삽입 시의 시간복..