Удаление из красно-черное дерево в F#


Да я очень медленно сделать мой путь через чисто функциональных структур данных. Поэтому я пошел через раздел на красно черные деревья. Что он представляет-это удивительно лаконичный, за исключением того, что он не включил функцию "Удалить". Поиск вокруг не много функциональных методов удалить, ну только два пока. Один в Haskell другой в Racket (вариант схемы я думаю). В Хаскеле код довольно непроницаема для меня, чтобы я пошел с пытаясь грокнуть ракетки версию Мэтт может. Мой опыт схема довольно ржавый, но мои знания Хаскелл Нилл.

Приведенный ниже код-это то, что я придумал. Вы можете увидеть полную реализацию RedBlackTree.FS здесь. Я уверен, что есть еще проблемы в этой реализации, так как я еще не полностью протестировал. Мой основной вопрос для более опытных парней делает то, что Мэтт выложил здесь действительно имеет смысл? И ты думаешь, как я пытался реализовать это в F# будет работать?

Если Вы читаете блог Мэтта вы увидите описание того, как он приближается к проблеме. Он добавляет два новых цвета (двойной черный и отрицательный черный) в дереве временно в удалить. Он также имеет представление о двойной черный лист, и именно там мое основное заблуждение кроется. После удаления двойной лист иногда остается позади (когда элемент удаляется, нет детей). Получается, что двойной черный лист это не временно. Это не для меня ясно, основываясь на его описание, если это то, что было задумано или у меня еще есть некоторые проблемы в моей логике.

Спасибо за взглянуть на это,

Дерек

// BB = double-black
// NB = negative-black
type Color = R | B | BB | NB
type Tree<'e when 'e :> IComparable> =
    | L | BBL               // BBL = double-black leaf
    | T of Color * Tree<'e> * 'e * Tree<'e>

module RedBlackTree =
    let empty = L
...
let addBlack c =
    match c with
    | B -> BB
    | R -> B
    | NB -> R
    | BB -> failwith "BB Nodes should only be temporary"

let subBlack c =
    match c with
    | B -> R
    | R -> NB
    | BB -> B
    | NB -> failwith "NB Nodes should only be temporary"

let redden n =
    match n with
    | L | BBL -> n
    | T(_,l,v,r) -> T(R,l,v,r)

let blacken node =
    match node with
    | BBL        -> L
    | T(_,l,v,r) -> T(B,l,v,r)
    | _          -> node

let rec balanceNode clr tl e tr =
    match clr, tl, e, tr with
    | BB,T(R, T(R,a,x,b),y,c), z, d 
    | BB,T(R,a,x, T(R,b,y,c)), z, d 
    | BB,a,x, T(R, T(R,b,y,c),z,d)  
    | BB,a,x, T(R,b,y, T(R,c,z,d)) 
    | B,T(R, T(R,a,x,b),y,c), z, d 
    | B,T(R,a,x, T(R,b,y,c)), z, d 
    | B,a,x, T(R, T(R,b,y,c),z,d)  
    | B,a,x, T(R,b,y, T(R,c,z,d))  -> 
        T((subBlack clr), T(B,a,x,b), y, T(B,c,z,d))
    | BB,a,x,T(NB,T(B,b,y,c),z,(T(B,_,_,_) as d)) ->
        T(B,T(B,a,x,b),y, balanceNode B c z (redden d))
    | BB,T(NB,(T(B,_,_,_) as a),x,T(B,b,y,c)),z,d ->
        T(B, (balanceNode B (redden a) x b), y, T(B,c,z,d))
    | _,_,_,_ -> T(clr,tl,e,tr)

let bubble t =
    match t with
    | T(c,(T(lc,ll,lv,lr) as lt),v, (T(rc,rl,rv,rr) as rt)) ->
        if lc = BB || rc = BB then
            balanceNode (addBlack c) (T(subBlack lc,ll,lv,lr)) v (T(subBlack rc,rl,rv,rr))
        else
            t
    | _ -> t

let isLeaf node =
    match node with
    | L | BBL -> true
    | _       -> false

let rec getMax node =
    match node with
    | L | BBL -> None
    | T(c,l,v,r) -> 
        match (isLeaf l), (isLeaf r) with
        | false, true
        | true,true -> Some(v)
        | _,_       -> getMax r

let rec remove node =
    match node with
    | L | BBL -> node
    | T(nc, lchild, nv, rchild) ->
        match (isLeaf lchild),(isLeaf rchild) with
        | true,true ->
            match nc with
            | R -> L
            | B -> BBL
            | _ -> failwith "Illegal black node"
        | true,false ->
            match nc,rchild with
            | R,T(rc,rl,rv,rr) -> rchild
            | B,T(rc,rl,rv,rr)-> 
                match rc with
                | R -> T(B,rl,rv,rr)
                | B -> T(addBlack rc,rl,rv,rr)
                | _ -> failwith "Illegal black node"
            | _ -> failwith "Illegal black node"
        | false,true ->
            match nc,lchild with
            | R,T(lc,ll,lv,lr) -> lchild
            | B,T(lc,ll,lv,lr) -> 
                match lc with
                | R -> T(B,ll,lv,lr)
                | B -> T(addBlack lc,ll,lv,lr)
                | _ -> failwith "Illegal black node"
            | _ -> failwith "Illegal black node"
        | false,false ->
            let max = (getMax lchild).Value
            let t = removeMax lchild
            bubble (T(nc,t,max,rchild))

and removeMax node =
    match node with
    | T(c,l,v,r) -> 
        if isLeaf r then
            remove node
        else
            bubble (T(c,l,v, removeMax r))
    | _ -> node

let delete key node =
    let rec del (key : IComparable) node =
        match node with
        | T(c,l,v,r) ->
            match key.CompareTo v with
            | -1 -> bubble (T(c,(del key l),v,r))
            |  0 -> remove node
            |  _ -> bubble (T(c,l,v,(del key r)))
        | _ -> node

    blacken (del key node)


Комментарии
1 ответ

Google для "левого толка красный черный деревья"; они Седжвик (существенная) упрощение деревьев РБ и бумага включает в себя весь код, в том числе и удалить. Добавляя ограничение, что все "три узла" наклон влево, в ряде случаев нужно учитывать резко уменьшается.

Надеюсь, что это помогает.

4
ответ дан 18 июля 2011 в 02:07 Источник Поделиться