Haskell 2-3-4 Tree

Question

우리는 Haskell에서 데이터 타입, 삽입 함수 및 디스플레이 함수를 쓰는 것처럼 2-3-4 트리를 생성하라는 요청을 받았습니다.

저는이 종류의 트리에 대한 정보를 얻는 것이 매우 어렵다는 것을 알고 있습니다. (Java, C++).

내가 지금까지 무엇을 가지고 -

data Tree t = Empty 
    | Two t (Tree t)(Tree t) 
    | Three t t (Tree t)(Tree t)(Tree t) 
    | Four t t t (Tree t)(Tree t)(Tree t)(Tree t) deriving (Eq, Ord, Show) 


leaf2 a = Two a Empty Empty 
leaf3 a b = Three a b Empty Empty Empty 
leaf4 a b c = Four a b c Empty Empty Empty Empty 

addNode::(Ord t) => t -> Tree t -> Tree t 
addNode t Empty = leaf2 t 
addNode x (Two t left right) 
    | x < t = Two t (addNode x left) right 
    | otherwise = Two t left (addNode x right) 

이 컴파일하지만은 3 개 노드 또는 네 개의 노드로 삽입을 쓰기 시작하는 방법이 맞습니다 확실하지만, 확실하지 아니에요.

표시 기능에 대한 "표시 표시"가 충분하지 않아 다이어그램에 일반적으로 나타나는 형식으로 트리를 인쇄해야한다고 지정되어 있습니다. 다시 말하지만, 이걸로가는 길을 모릅니다.

도움이나 조언을 주시면 감사하겠습니다.

Answer 1

나는 2-3-4 나무에 대해 아무것도 몰라,하지만 세 개의 노드, 당신은 다음과 같이 시작합니다 :

addNode t (Three x y left mid right) 
    | cond1 = expr1 
    | cond2 = expr2 
    (etc) 

은 무엇 cond1, cond2, expr1 및 expr2, 정확하게,이다 2-3-4 나무의 정의에 의존한다. show 방법으로

, 일반적인 윤곽이 될 것이다 :

instance (Show t) => Show (Tree t) where 
    show Empty = ... 
    show (Two x l r) = ...show x...show l...show r... 
    show (Three x y l m r) = ... 
    show (Four x y z l m n r) = ... 

구현은 당신이보고 싶은 방법에 따라 달라집니다하지만 비어 있지 않은 경우에, 당신은 아마 모두에 show를 호출합니다 표시되는 트리의 구성 요소 중 하나입니다. 당신이 나무의 중첩 된 부분을 들여 싶은 경우에, 아마 당신은 별도의 방법을 만들어야합니다 : 우리는 2-3-4 트리를 만들도록 요청했습니다

instance (Show t) => Show (Tree t) where 
    show = showTree 0 

showTree :: Show t => Int -> Tree t -> String 
showTree n = indent . go 
    where indent = (replicate n ' ' ++) 
     go Empty = "Empty" 
     go (Two x l r) = (...show x...showTree (n+1) l...showTree (n+1) r...) 
     (etc) 

Answer 2

을

내 애도. 나는 숙제를 위해 한 번만 구현해야했다. 2-3-4 나무는 B- 나무의 모든 단점과 장점이없는 B- 나무입니다. 어린이의 각 수에 대해 개별적으로 사례를 작성하는 것은 단지 2 개의 목록 만 갖는 것만 큼 귀찮습니다 -4 요소.

포인트 : B 트리 삽입 알고리즘이 작동해야하며 크기를 고정해야합니다. Cormen et al. 그들의 책 Introduction to algorithms에 하나의 가상 코드가 있습니다 (심각한 경고 성 경고!).

네 개의 대수 데이터 형식 대신 노드의 크기를 적용하지 않더라도 데이터 요소와 자식 목록을 갖는 것이 더 나을지도 모릅니다. 최소한 노드 크기를 확장하는 것이 더 쉬울 것입니다.