关于golang:红黑树未验证

package main

import "fmt"

const (
    RED bool = true
    BLACK bool = false
)

type RBTree struct {root *Node}

func NewRBTree() *RBTree {return &RBTree{}
}

func (t *RBTree) Search (v int64) *Node {
    n := t.root
    for n != nil {
        if v < n.v {n = n.l} else if v >n.v {n = n.r} else {return n}
    }
    return nil
}

func (t *RBTree) Insert(v int64) {
    if t.root == nil {t.root = &Node{v:v, c:BLACK}
        return
    }
    n := t.root
    
    addNode := &Node{v:v, c:RED}
    
    var np *Node
    
    for n != nil {if (v == n.v) {return}
        
        np = n
        if v < n.v {n = n.l} else {n = n.r}
    }
    addNode.p = np
    if v < np.v {np.l = addNode} else {np.r = addNode}
    
    // 验证规定
    t.insertFix(addNode)
}

func (t *RBTree) insertFix(n *Node) {for !isBlack(n.p) {uncle := n.p.getBrother()
        if !isBlack(uncle) {
            n.p.c = BLACK
            uncle.c = BLACK
            uncle.p.c = RED
            n = n.p.p
            t.root.c = BLACK
            continue
        }
        if n.p == n.p.p.l {
            if n == n.p.l {
                n.p.p.c = RED
                n.p.c = BLACK
                n = n.p.p
                n.rTurn(t)
                t.root.c = BLACK
                continue
            }
            n = n.p
            n.lTurn(t)
            t.root.c = BLACK
            continue
        }
        if n == n.p.r {
            n.p.p.c = RED
            n.p.c = BLACK
            n = n.p.p
            n.lTurn(t)
            t.root.c = BLACK
            continue
        }
        n = n.p
        n.rTurn(t)
        t.root.c = BLACK
    }
}

func (t *RBTree) Del(v int64) {n := t.Search(v)
    np := n.p
    
    if n == nil {return}
    
    var revise string
    
    if n.l == nil && n.r == nil {revise = "none"} else if np == nil {revise = "root"} else if n == np.l {revise = "left"} else if n == np.r {revise = "right"}
    
    // 内含递归
    n.del(t)
    
    if isBlack(n) {
        if revise == "root" {t.delFix(t.root)
        } else if revise == "left" {t.delFix(np.l)
        } else if revise == "right" {t.delFix(np.r)
        }
    }
}

func (t *RBTree) delFix(n *Node) {
    var b *Node
    
    for n != t.root && isBlack(n) {
        
        // 删除节点为左节点，存在兄弟节点
        if n.p.l == n && n.p.r != nil {
            b = n.p.r
            if !isBlack(b) {
                b.c = BLACK
                n.p.c = RED
                n.p.lTurn(t)
            } else if isBlack(b) && b.l != nil && isBlack(b.l) && b.r != nil && isBlack(b.r){
                b.c = RED
                n = n.p
            } else if isBlack(b) && b.l != nil && !isBlack(b.l) && b.r != nil && isBlack(b.r) {
                b.c = RED
                b.l.c = BLACK
                b.rTurn(t)
            } else if isBlack(b) && b.r != nil && !isBlack(b.r) {
                b.c = RED
                b.r.c = BLACK
                b.p.c = BLACK
                b.p.lTurn(t)
                n = t.root
            }
        } else if n.p.r == n && n.p.l != nil {
            b = n.p.l
            if !isBlack(b) {
                b.c = BLACK
                n.p.c = RED
                n.p.rTurn(t)
            } else if isBlack(b) && b.l != nil && isBlack(b.l) && b.r != nil && isBlack(b.r) {
                b.c = RED
                n = n.p
            } else if isBlack(b) && b.l != nil && isBlack(b.l) && b.r != nil && !isBlack(b.r) {
                b.c = RED
                b.r.c = BLACK
                b.lTurn(t)
            } else if isBlack(b) && b.l != nil && !isBlack(b.l) {
                b.c = RED
                b.l.c = BLACK
                b.p.c = BLACK
                b.p.rTurn(t)
                n = t.root
            }
        } else {return}
    }
}

func (t *RBTree) min(n *Node) *Node {
    if n == nil {return nil}
    
    for n.l != nil {n = n.l}
    return n
}

func (t *RBTree) max(n *Node) *Node {
    if n == nil {return nil}
    for n.r != nil {n =n.r}
    return n
}

// 获取前驱节点
func (t *RBTree) getPredecessor(n *Node) *Node {
    if n == nil {return nil}
    // 小分支里的最大节点
    if n.l != nil {return t.max(n.l)
    }
    // 如果不存在又节点就从父节点中找
    for {
        if n.p == nil {break}
        if n == n.p.r {return n.p}
        n = n.p
    }
    return nil
}

// 获取继承节点
func (t *RBTree) getSuccessor(n *Node) *Node {
    if n == nil {return nil}
    
    // 大分支里的最小节点
    if n.r != nil {return t.min(n.r)
    }
    // 如果不存在又节点就从父节点中找
    for {
        if n.p == nil {break}
        if n == n.p.l {return n.p}
        n = n.p
    }
    return nil
}

/////////////////////////////////////

func isBlack(n *Node) bool {
    if n == nil {return true}
    return n.c == BLACK
}

func setColor(n *Node, color bool) {
    if n == nil {return}
    n.c = color
}

////////////////////////////////////////////////////////////

type Node struct {
    l, r, p *Node
    v int64
    c bool
}

func (n *Node) lTurn(t *RBTree) {
    if n == nil || n.r == nil {return}
    
    np := n.p
    nr := n.r
    
    // 父节点解决
    if np != nil {
        if n == np.l {np.l = nr} else {np.r = nr}
    } else {t.root = nr}
    
    
    // 解决本人关系
    n.p = nr
    n.r = nr.l
    if n.r != nil {
        // 左孙节点解决
        n.r.p = n
    }
    // 右子节点解决
    nr.l = n
    nr.p = np
}

func (n *Node) rTurn(t *RBTree) {
    if n == nil || n.l == nil {return}
    
    nl := n.l
    np := n.p
    
    // 父节点解决
    if np != nil {
        if n == np.l {np.l = nl} else {np.r = nl}
    } else {t.root = nl}
    
    // 解决本人关系
    n.p = nl
    n.l = nl.r
    if n.l != nil {
        // 右孙节点解决
        n.l.p = n
    }
    // 左子节点解决
    nl.r = n
    nl.p = np
    
}

func (n *Node) getBrother() *Node {
    if n.p == nil {return nil}
    if n.p.l == n {return n.p.r}
    if n.p.r == n {return n.p.l}
    return nil
}

func (n *Node) del(t *RBTree) {
    np := n.p
    
    if n.l == nil && n.r == nil {
        // 节点为尾部节点（不存在子节点）// 根节点、左尾节点、右尾节点
        if n == t.root {t.root = nil} else if np.l == n {np.l = nil} else {np.r = nil}
    } else if n.l != nil && n.r == nil {
        // 存在左子节点
        if n == t.root {
            // 根节点
            n.l.p = nil
            t.root = n.l
        } else {
            n.l.p = np
            if np.l == n {np.l = n.l} else {np.r = n.l}
        }
    } else if n.l == nil && n.r != nil {
        // 存在右子节点
        if n == t.root {
            n.r.p = nil
            t.root = n.r
        } else {
            n.r.p = np
            if np.l == n {np.l = n.r} else {np.r = n.r}
        }
    } else {
        // 存在两个节点
        successor := t.getSuccessor(n)
        n.v = successor.v
        n.c = successor.c
        
        // 递归删除
        successor.del(t)
    }
}

func main() {btree := NewRBTree()
    
    btree.Insert(1)
    btree.Insert(21)
    btree.Insert(3)
    btree.Insert(4)
    btree.Insert(5)
    btree.Insert(6)
    btree.Insert(7)
    btree.Insert(8)
    btree.Insert(9)
    btree.Insert(10)
    btree.Insert(1)
    
    fmt.Println(btree.Search(11))
    fmt.Println(btree.Search(10))
    fmt.Println(btree.Search(9))
    fmt.Println(btree.Search(8))
    fmt.Println(btree.Search(7))
    fmt.Println(btree.Search(6))
    fmt.Println(btree.Search(5))
    fmt.Println(btree.Search(4))
    fmt.Println(btree.Search(3))
    fmt.Println(btree.Search(21))
    fmt.Println(btree.Search(1))
    fmt.Println(btree.root)
}