本文已参加 「新人创造礼」 活动,一同敞开创造之路。

写在前面

二叉树是 树形结构核算的一种特例，二叉平衡树是其间的佼佼者，当咱们使用有序的办法刺进节点到树时，相比链表的查询，操作大量数据时 咱们可以省却在链表中查找的繁琐。

二叉搜索树是 红黑树的基础红黑树 R-B tree， 全称 Red-Black Tree 本身是一个 二叉查找树，在其基础上附加了两个要求树中每个热点增加一个用于存储颜色的 标志域。

树中没有一个 路径比其他任何路径长出两倍，整个树要接近于 平衡 状态。 本文试着使用树形结构存储运势核算中数据的存储使命。

1 怎么开始

咱们需求一个树，这个树的结点需求可以记得自己的key和数据payload， 左右子节点，父节点等信息。所以咱们先规划节点，记得把平衡因子带上。

    type TreeNode struct {
            Key           int
            Payload       string
            LeftChild     *TreeNode
            RightChild    *TreeNode
            Parent        *TreeNode
            balanceFactor int
    }

如此，咱们开始了万里长征（其实是只要3大步的战略）第一步，万事开头难，也没有那么难，不是吗？

可是只要这些节点并不能完结咱们的使命，咱们需求一个办理它们的办法，也便是咱们将要把这些节点，组织成树的方式。

而且在此基础上，咱们需求增加一些信息，比如左数多大，右树多大，总共多大（感觉有些多余，可是为了便利取得，仍是记载吧），由于每个节点都知道其周围的信息，办理树只需求记载根节点信息。

// 树办理
type BinarySearchTree struct {
        Root      *TreeNode //根节点
        Size      int       //本树总巨细 包含根节点
        LeftSize  int       //左子树巨细
        RightSize int       //右子树巨细
}

1.1 咱们还需求什么？

关于树的每个节点，咱们需求一系列办法以知晓其周围的信息，比如左子节点有没有？ 是什么？ 是不是叶子节点？ 同样的包含右子节点也是如此，另外咱们还需求对整个树有个了解，所以需求有办法对其进行遍历 和核算。

    func (tn *TreeNode) HasLeftChild() *TreeNode {
            return tn.LeftChild
    }
    func (tn *TreeNode) HasRightChild() *TreeNode {
            return tn.RightChild
    }
    func (tn *TreeNode) IsLeftChild() bool {
            /// 是否左子 节点
            if tn.Parent != nil && tn.Parent.LeftChild == tn {
                    return true
            }
            return false
    }
    func (tn *TreeNode) IsRightChild() bool {
            // 是否 右子节点
            if tn.Parent != nil && tn.Parent.RightChild == tn {
                    return true
            }
            return false
    }
    func (tn *TreeNode) IsRoot() bool {
            // 是否根节点
            if tn.Parent == nil {
                    return true
            } else {
                    return false
            }
    }
    func (tn *TreeNode) IsLeaf() bool {
            // 是否叶子节点
            if tn.RightChild == nil && tn.LeftChild == nil {
                    return true
            } else {
                    return false
            }
    }

1.2 再进一步的

咱们还需求对树进行遍历以核算和分析，
咱们还需求对树进行查找和删去
….
这样吧，咱们可以开辟一个缓存，用以存储这些信息

   // 缓存队列，用于存放 二叉树的 中序遍历结果
type CacheChan struct {
        Size  int /// cache 巨细标记
        Read  <-chan *TreeNode
        Input chan<- *TreeNode
}
func NewCacheChan(size int) *CacheChan {
        if size <= 0 {
                panic("size must bigger than 0")
        }
        Chans := make(chan *TreeNode, size)
        return &CacheChan{
                Size:  size,
                Read:  Chans,
                Input: Chans,
        }
}

对缓存的操作

    // 增加一个节点到缓存
    func (ch *CacheChan) Putin(td *TreeNode) int {
            MutilLock.Lock()
            defer MutilLock.Unlock()
            if len(ch.Input) < ch.Size {
                    ch.Input <- td
                    return ch.Size
            }
            return 0
    }
    // 按序取出一个node 节点
    func (ch *CacheChan) GetNode() *TreeNode {
            MutilLock.Lock()
            defer MutilLock.Unlock()
            if len(ch.Read) > 0 {
                    td := <-ch.Read
                    return td
            }
            return nil
    }
    func (ch *CacheChan) IsTreeNodeIn(key int) bool {
            isIn := false
            if ch.Size <= 0 {
                    return isIn
            }
            t := ch.Size
            for i := 0; i < t; i++ {
                    td := ch.GetNode()
                    ch.Putin(td)
                    if td.Key == key {
                            isIn = true
                    }
            }
            return isIn
    }

咱们供给一种办法，以便知道该树的某个节点所有的子节点， 中序遍历 二叉树节点的子节点 并存储到channel 回来指向 channel的指针

    func (tn *TreeNode) IterCache(size int) *CacheChan {
            cacheCahn := tn.MakeCacheChan(size)
            if tn != nil {
                    tnLeft := tn.HasLeftChild() //  左子树
                    if tnLeft != nil {
                            cacheCahn.Putin(tnLeft)
                            cacheCahn = IterCacheLeftNode(cacheCahn, tnLeft)
                    } 
                    Logg.Printf("%+v\n", tn)
                    cacheCahn.Putin(tn)
                    tnRight := tn.HasRightChild() // 右子树
                    if tnRight != nil {
                            cacheCahn.Putin(tnRight)
                            cacheCahn = IterCacheRightNode(cacheCahn, tnRight)
                    } 
            }
            return cacheCahn
    }

现在咱们供给办法，写入节点到树中

    // 刺进节点
    func (bst *BinarySearchTree) Put(key int, val string, cNode *TreeNode) {
            if key < cNode.Key {
                    // 假如参数key比当时节点key 小，进入树的左子树进行递归刺进
                    if cNode.HasLeftChild() != nil {
                            bst.Put(key, val, cNode.LeftChild) /// 递归左子树 刺进
                    } else {
                            cNode.LeftChild = &TreeNode{Key: key,
                                    Payload: val, Parent: cNode} //树的左子节点
                    }
            } else { /// 假如参数 key的值 大于当时节点key，进入树的右子树进入递归刺进
                    if cNode.HasRightChild() != nil {
                            bst.Put(key, val, cNode.RightChild) /// 递归右子树
                    } else {
                            cNode.RightChild = &TreeNode{Key: key,
                                    Payload: val, Parent: cNode}
                    }
            }
    }
    //	高度log2_n,假如key 列表随机分布，大于小于根节点的key的键值 大致适当
    //
    // 功能在于二叉树的高度，最大层次，高度也受数据项key刺进顺序影响
    // 算法复杂度 最差 O(log2_n)
    func (bst *BinarySearchTree) Puts(key int, val string) bool {
            if bst.Root != nil {
                    // 有根节点
                    MutilLock.Lock()
                    defer MutilLock.Unlock()
                    if bst.Searcher(key) != nil {
                            // 现已存在 无法刺进
                            msg := fmt.Sprintf("the key had exist at treenode:%+v\n", key)
                            Logg.Println(msg)
                            return false
                    }
                    bst.Put(key, val, bst.Root)
                    //更新巨细信息
                    if bst.Root.Key < key {
                            //新 key 增加在右侧
                            bst.RightSize += 1
                    } else if bst.Root.Key >= key {
                            //新 key 增加在右侧
                            bst.LeftSize += 1
                    }
            } else {
                    /// 没有根节点
                    bst.Root = &TreeNode{Key: key, Payload: val}
            }
            bst.Size += 1
            return true
    }
    // 设置节点
    func (bst *BinarySearchTree) SetNode(node *TreeNode) bool {
            return bst.Puts(node.Key, node.Payload)
    }
    // 找到节点为key的 Payload值，只要是平衡树，get的时刻复杂度可用坚持在 O(logN)
    func (bst *BinarySearchTree) Searcher(key int) *TreeNode {
            if bst.Root != nil {
                    res := bst.Get(key, bst.Root) /// 递归该树
                    if res != nil {
                            return res
                    }
            }
            return nil
    }
    // 当时节点，即要刺进的 二叉查找树， 子树的根，为当时节点
    func (bst *BinarySearchTree) Get(key int, cNode *TreeNode) *TreeNode {
            if cNode == nil {
                    return nil
            } else if cNode.Key == key {
                    return cNode
            } else if key < cNode.Key {
                    return bst.Get(key, cNode.LeftChild)
            } else {
                    return bst.Get(key, cNode.RightChild)
            }
    }

供给查找最大最小节点的办法

// 当时节点的左子节点，左子树的 最左下角的 值
func (tn *TreeNode) FindMin() *TreeNode {
        current := tn                       // 根节点
        for current.HasLeftChild() != nil { // 直到找到最左下角的值，便是直接后继
                current = current.LeftChild
        }
        return current
}
// 当时节点的右子节点，右子树的 最右下角的 值
func (tn *TreeNode) FindMax() *TreeNode {
        current := tn                        // 根节点
        for current.HasRightChild() != nil { // 直到找到最右下角的值，便是直接后继
                current = current.RightChild
        }
        return current
}

最后，咱们供给删去节点的办法，以便在核算运势时使用它制作爻变

    // delete 的具体完结，要求仍然坚持BST 性质
    // 1 节点无子节点 2 节点有1个子节点 3 节点有2个子节点
    func (bst *BinarySearchTree) remove(cNode *TreeNode) {
            if cNode.IsLeaf() {
                    /// leaf 叶子节点，没有子节点，属于场景1，无子节点，直接删去
                    if cNode == cNode.Parent.LeftChild {
                            /// 本身是 左子节点
                            cNode.Parent.LeftChild = nil
                    } else {
                            cNode.Parent.RightChild = nil
                    }
            } else if cNode.HasBothChildren() {
                    /// 有两个子节点
                    succe := cNode.FindSuccessor() // 找到当时需求删去的节点的后继节点
                    succe.SpliceOut()
                    cNode.Key = succe.Key         // 替换Key
                    cNode.Payload = succe.Payload // 替换Payload 值，节点的数据
            } else {
                    /// 有一个子节点
                    if cNode.HasLeftChild() != nil {
                            if cNode.IsLeftChild() {
                                    /// 左子节点删去
                                    cNode.LeftChild.Parent = cNode.Parent    // 修正指针。当时节点的左子节点的父节点，修正为节点的父节点
                                    cNode.Parent.LeftChild = cNode.LeftChild // 修正指针，当时节点的父节点的左子节点，修正为当时节点的左子节点
                            } else if cNode.IsRightChild() {
                                    /// 右 子节点删去
                                    cNode.LeftChild.Parent = cNode.Parent
                                    cNode.Parent.RightChild = cNode.LeftChild
                            } else {
                                    // 根节点删去
                                    cNode.ReplaceNodeData(
                                            cNode.LeftChild.Key,
                                            cNode.LeftChild.Payload,
                                            cNode.LeftChild.LeftChild,
                                            cNode.LeftChild.RightChild,
                                    )
                            }
                    } else {
                            if cNode.IsLeftChild() {
                                    /// 左子节点删去
                                    cNode.RightChild.Parent = cNode.Parent
                                    cNode.Parent.LeftChild = cNode.RightChild
                            } else if cNode.IsRightChild() {
                                    /// 右子节点删去
                                    cNode.RightChild.Parent = cNode.Parent
                                    cNode.Parent.RightChild = cNode.RightChild
                            } else {
                                    /// 根节点删去
                                    cNode.ReplaceNodeData(
                                            cNode.RightChild.Key,
                                            cNode.RightChild.Payload,
                                            cNode.RightChild.LeftChild,
                                            cNode.RightChild.RightChild,
                                    )
                            }
                    }
            }
    }
    // deletes 用于删去 树中某个节点，子节点替换当时节点，具体是调用 delete办法
    // 修正树的 巨细信息
    func (bst *BinarySearchTree) Deletes(key int) {
            var nTRemove *TreeNode
            if bst.Size > 1 {
                    nTRemove = bst.Get(key, bst.Root)
                    if nTRemove != nil {
                            bst.remove(nTRemove)
                            bst.Size -= 1
                    } else {
                            msg := "Error, key not in tree"
                            panic(msg)
                    }
            } else if bst.Size == 1 && bst.Root.Key == key {
                    nTRemove = bst.Root
                    bst.Root = nil
                    bst.Size -= 1
            } else {
                    msg := "Error, key not in tree."
                    panic(msg)
            }
            //没有报错 则更新巨细
            if bst.Root.Key > key {
                    //此key在左子树
                    bst.LeftSize -= 1
                    Logg.Printf("success del nTRemove:%v bst.LeftSize :%v \n", nTRemove, bst.LeftSize)
            } else if bst.Root.Key <= key {
                    // 此key 在右子树
                    bst.RightSize -= 1
                    Logg.Printf("success del nTRemove:%v bst.RightSize :%v \n", nTRemove, bst.RightSize)
            }
    }

小结

好了，一颗正宗的树就此建立完结，咱们将以此结构来做一些运算和分析，当然，也便是运势揣度。

有爱好的可以看这个小系列的第二节。

本文已参加 「新人创造礼」 活动,一同敞开创造之路。