red_black_tree.go

package main

import "fmt"

type Node struct {
    Key int
    Value int
    Left *Node
    Right *Node
    Level int
}

func NewNode(key int, value int) *Node {
    return &Node{
        Key: key,
        Value: value,
        Left: nil,
        Right: nil,
        Level: 1,
    }
}

func (n *Node) Search(key int) int {
    fmt.Println(n.Key)
    if n.Key == key {
        return n.Value
    }
    if key > n.Key {
        return n.Right.Search(key)
    } else {
        return n.Left.Search(key)
    }
}

func (n *Node) Skew() *Node {
    if n.Left == nil {
        return n
    }
    if n.Left.Level != n.Level {
        return n
    }
    lft := n.Left
    n.Left = lft.Right
    lft.Right = n
    return lft
}

func (n *Node) Split() *Node {
    if n.Right == nil || n.Right.Right == nil {
        return n
    }
    if n.Level != n.Right.Right.Level {
        return n
    }
    rgt := n.Right
    n.Right = rgt.Left
    rgt.Left = n
    rgt.Level += 1
    return rgt
}

func (n *Node) Insert(key int, value int) *Node {
    if n.Key == key {
        n.Value = value
        return n
    }
    if key > n.Key {
        if n.Right == nil {
            n.Right = NewNode(key, value)
        } else {
            n.Right = n.Right.Insert(key, value)
        }
    } else {
        if n.Left == nil {
            n.Left = NewNode(key, value)
        } else {
            n.Left = n.Left.Insert(key, value)
        }
    }

    current := n
    current = current.Skew()
    current = current.Split()

    return current
}

func main() {
    main := NewNode(120, 500)
    var n int = 1000000
    for i := 0; i < n; i++ {
        main = main.Insert(i, i*2)
    }

    fmt.Println("Result: ", main.Search(3000))
}