為簡單起見，鍵值均為整型。
定義接口(tree.go)：
type Tree interface {
Put(k, v int) //新增或修改
Get(k int) int //查詢
Delete(k int) //刪除
Size() int //樹的大小
Min() int //最小鍵
DeleteMin() //刪除最小鍵
}
二叉查找樹(binary_tree.go)：
//二叉查找樹
type BinaryTree struct {
root *node
n int
}
//創(chuàng)建節(jié)點
func newNode(k, v int) *node {
return &node{k: k, v: v, sz: 1}
}
//創(chuàng)建二叉查找樹
func NewBinaryTree() *BinaryTree {
return &BinaryTree{}
}
//增加或修改
func (bt *BinaryTree) Put(k, v int) {
bt.root, _ = put(bt.root, k, v)
}
//查找
func (bt *BinaryTree) Get(k int) int {
return get(bt.root, k)
}
//樹的大小
func (bt *BinaryTree) Size() int {
return size(bt.root)
}
//選出最小鍵
func (bt *BinaryTree) Min() int {
return min(bt.root).k
}
//刪除最小鍵
func (bt *BinaryTree) DeleteMin() {
bt.root = deleteMin(bt.root)
}
//刪除
func (bt *BinaryTree) Delete(k int) {
bt.root = delete(bt.root, k)
}
節(jié)點(node.go)：
//節(jié)點
type node struct {
k, v, sz int //鍵拣帽，值，大小
left, right *node //左右子節(jié)點
}
//在以nd為根節(jié)點的樹下增加或修改一個節(jié)點
//如果創(chuàng)建了新節(jié)點驹闰，第二個參數返回true芹关，
//如果只是修改，第二個參數返回false
func put(nd *node, k, v int) (*node, bool) {
if nd == nil {
return newNode(k, v), true
}
hasNew := false //檢測是否創(chuàng)建了新節(jié)點
if k < nd.k {
nd.left, hasNew = put(nd.left, k, v)
} else if k > nd.k {
nd.right, hasNew = put(nd.right, k, v)
} else {
nd.v = v //僅修改呜呐，不會增加增加節(jié)點就斤，就不更新節(jié)點大小
}
if hasNew { //如果創(chuàng)建了新節(jié)點就更新樹的大小
updateSize(nd)
}
return nd, hasNew
}
//在以nd為根節(jié)點的樹中獲取鍵為k的值
func get(nd *node, k int) int {
if nd == nil {
return -1
}
if k < nd.k {
return get(nd.left, k)
} else if k > nd.k {
return get(nd.right, k)
} else {
return nd.v
}
}
//獲取以nd為根節(jié)點的樹的大小
func size(nd *node) int {
if nd == nil {
return 0
}
return nd.sz
}
//更新以nd為根節(jié)點的樹的大小
func updateSize(nd *node) {
if nd == nil {
return
}
nd.sz = size(nd.left) + size(nd.right) + 1
}
//選出以nd為根節(jié)點的樹的最小鍵節(jié)點
func min(nd *node) *node {
if nd == nil {
return nil
}
if nd.left != nil {
return min(nd.left)
}
return nd
}
//刪除以nd為根節(jié)點的樹的最小鍵節(jié)點
//返回被刪除的節(jié)點
func deleteMin(nd *node) *node {
if nd == nil {
return nil
}
if nd.left == nil { //找到最小節(jié)點
nd = nd.right //用右子節(jié)點代替自己
} else { //還有更小的
nd.left = deleteMin(nd.left)
}
updateSize(nd)
return nd
}
//刪除以nd為根節(jié)點的樹并且鍵為k的節(jié)點
func delete(nd *node, k int) *node {
if nd == nil {
return nil
}
if k < nd.k {
nd.left = delete(nd.left, k)
} else if k > nd.k {
nd.right = delete(nd.right, k)
} else { //命中要刪除的節(jié)點
//只有一個或零個子節(jié)點
if nd.right == nil {
return nd.left
}
if nd.left == nil {
return nd.right
}
//同時具有兩個子節(jié)點
//先找出大于本節(jié)點的最小節(jié)點作為后繼節(jié)點
t := nd
nd.k = min(t.right).k
//刪除
deleteMin(t.right)
//用后繼節(jié)點代替本節(jié)點
nd.left = t.left
}
updateSize(nd)
return nd
}
