package main

import "fmt"

type node struct {
    left *node
    right *node
    key int
    value int
}
type BST struct {
    head *node
    n int
}

func (this *BST) put(key,value int){
    tmpNode := this.head
    if tmpNode == nil{
        this.head = new(node)
        this.head.key = key
        this.head.value = value
        return
    }
    for tmpNode != nil{
        if key<tmpNode.key{
            if tmpNode.left == nil{
                tmpNode.left = new(node)
                tmpNode.left.key = key
                tmpNode.left.value = value
                return
            }
            tmpNode = tmpNode.left
        }else if key>tmpNode.key{
            if tmpNode.right == nil{
                tmpNode.right = new(node)
                tmpNode.right.key = key
                tmpNode.right.value = value
                return
            }
            tmpNode = tmpNode.right
        }else{
            tmpNode.value = value
            return
        }
    }
}

func (this *BST) get(key int)int{
    tmpNode := this.head
    for tmpNode != nil{
        if key<tmpNode.key{
            if tmpNode.left == nil{
                return 0
            }
            tmpNode = tmpNode.left
        }else if key>tmpNode.key{
            if tmpNode.right == nil{
                return 0
            }
            tmpNode = tmpNode.right
        }else{
            return tmpNode.value
        }
    }
    return 0
}

func (this *BST) min()int{
    return this.getMin(this.head).value
}

func (this *BST)getMin(node *node)*node{
    if node.left != nil{
        node = this.getMin(node.left)
    }
    return node
}

func (this *BST)floor(key int)int{
    res := this.getFloor(this.head,key)
    if res == nil{
        return 0
    }
    return res.key
}

func (this *BST)getFloor(node *node,key int)*node{

    if node == nil{
        return node
    }
    if key>node.key{
        returnNode := this.getFloor(node.right,key)
        if returnNode == nil{
            return node
        }else{
            return returnNode
        }
    }else if key < node.key{
        return this.getFloor(node.left,key)
    }else{
        return node
    }
    return nil

}

func (this *BST)print()[]int{
    var nodeList []int
    this.printBST(this.head,&nodeList)
    return nodeList
}

func (this *BST)printBST(node *node,nodeList *[]int){
    if node.left != nil{
        this.printBST(node.left,nodeList)
    }
    *nodeList = append(*nodeList,node.key)
    if node.right != nil{
        this.printBST(node.right,nodeList)
    }
}

func (this *BST)delete(key int){
    tmpNode := this.head
    var isleft bool
    var parentNode *node
    for tmpNode != nil{
        if key<tmpNode.key{
            if tmpNode.left == nil{
                return
            }
            parentNode = tmpNode
            tmpNode = tmpNode.left
            isleft = true
        }else if key>tmpNode.key{
            if tmpNode.right == nil{
                return
            }
            parentNode = tmpNode
            tmpNode = tmpNode.right
            isleft = false
        }else{
            break
        }
    }
    //这里已经找到要删除的节点
    if tmpNode.left == nil && tmpNode.right == nil{
        if isleft{
            parentNode.left = nil
        }else{
            parentNode.right = nil
        }
        return
    }
    if tmpNode.left == nil{
        if isleft{
            parentNode.left = tmpNode.right
        }else{
            parentNode.right = tmpNode.right
        }
        return
    }
    if tmpNode.right == nil{
        if isleft{
            parentNode.left = tmpNode.left
        }else{
            parentNode.right = tmpNode.left
        }
        return
    }
    var parentNode2 *node
    tmpNode2 := tmpNode.right
    for {
        if tmpNode2.left != nil{
            parentNode2 = tmpNode2
            tmpNode2 = tmpNode2.left
        }else{
            break
        }
    }
    if isleft{
        parentNode.left = tmpNode2
    }else{
        parentNode.right = tmpNode2
    }
    parentNode2.left = tmpNode2.right
    tmpNode2.left = tmpNode.left
    tmpNode2.right = tmpNode.right
    return
}

func main(){
    var bst BST
    bst.put(100,100)
    bst.put(90,90)
    bst.put(110,110)
    bst.put(80,80)
    bst.put(95,95)
    bst.put(105,105)
    bst.put(115,115)
    bst.put(70,70)
    bst.put(85,85)
    bst.put(93,93)
    bst.put(97,97)
    //bst.put(91,91)
    bst.put(94,94)
    bst.put(92,92)

    //bst.delete(70)
    fmt.Println(bst.print())
}