Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset
Kokeilin tehdä Haskellilla splay-puun, mutta sen toiminta ei vaikuta mitenkään superjärkevältä :) Tosin se toimii, eli splayTo:lla saa juureen aina haluamansa alkion, mutta en ole kovin vakuuttunut siitä, miten puun rakenne muuttuu. Ja lisäksi tämä toimii tavalla, jossa luodaan väliaikaisia puun juuria vain sitä varten, että tuloksen voisi taas antaa splay:lle takaisin.
data Tree v = Empty | Node v (Tree v) (Tree v) deriving (Show, Eq) single v = Node v Empty Empty splay :: Ord v => v -> Tree v -> Tree v splay v (Node o (Node m (Node n lll llr) lr) r) | v < o && v < m = Node n lll (Node o (Node m llr lr) r) splay v (Node o (Node n ll (Node m lrl lrr)) r) | v < o && v > n = Node m (Node n ll lrl) (Node o lrr r) splay v (Node n l (Node m rl (Node o rrl rrr))) | v > n && v > m = Node o (Node n l (Node m rl rrl)) rrr splay v (Node n l (Node o (Node m rll rlr) rr)) | v > n && v < o = Node m (Node n l rll) (Node o rlr rr) splay v (Node n l (Node m rl rr)) | v > n && v >= m = Node m (Node n l rl) rr splay v (Node m (Node n ll lr) r) | v < m && v <= n = Node n ll (Node m lr r) splay _ tr = tr splayTo v tr = if tr == tr' then tr else splayTo v tr' where tr' = splay v tr toList Empty = [] toList (Node v l r) = toList l ++ (v : toList r) depth Empty = 0 depth (Node _ l r) = 1 + max (depth l) (depth r) ex = Node 1 Empty $ Node 3 (single 2) (single 4) ex2 = Node 6 ex $ Node 9 (single 7) (single 10) ex3 = Node 15 ex2 $ Node 20 (single 16) (single 23)