package BST
//=========================队列=============================
type QueueItem struct {
   value *BinaryTreeNode
   next  *QueueItem
}

type Queue struct {
   head *QueueItem
   tail *QueueItem
}

func NewQueue() (ret *Queue) {
   ret = &Queue{}
   return
}

func (q *Queue) Append(node *BinaryTreeNode) {
   if q.head == nil {
       q.head = &QueueItem{
           value: node,
       }
       q.tail = q.head
       return
   }
   q.tail.next = &QueueItem{
       value: node,
   }
   q.tail = q.tail.next
}

func (q *Queue) Remove() (ret *BinaryTreeNode) {
   if q.head == nil {
       return
   }
   if q.head == q.tail {
       q.tail = nil
   }
   ret = q.head.value
   q.head = q.head.next
   return
}

func (q *Queue) IsEmpty() bool {
   return q.head == nil
}

//==========================栈=============================
type Stack struct {
   list []*BinaryTreeNode
   top int
}

func NewStack() (ret *Stack) {
   ret = &Stack{
       top:-1,
   }
   return
}

func (s *Stack) IsEmpty() bool {
   return s.top == -1
}

func (s *Stack) Push(node *BinaryTreeNode) {
   if s.top == len(s.list) - 1 {
       s.list = append(s.list,node)
       s.top++
   } else {
       s.top++
       s.list[s.top] = node
   }
}

func (s *Stack) Pop()(ret *BinaryTreeNode) {
   if s.top == -1 {
       return
   }
   ret = s.list[s.top]
   s.top--
   return
}

func (s *Stack) Top() (ret *BinaryTreeNode) {
   ret = s.list[s.top]
   return
}
//=========================二叉树===========================
//词条
type Token struct {
   Key     int64   //词条的KEY
   Value   interface{} //词条的值
}
//获取词条的值
func (t *Token) GetValue() interface{} {
   return t.Value
}
//获取词条的键
func (t *Token) GetKey() int64 {
   return t.Key
}
//二叉树节点
type BinaryTreeNode struct {
   left    *BinaryTreeNode
   right   *BinaryTreeNode
   parent  *BinaryTreeNode
   height  int64
   Tk      *Token
}
//新建节点
func NewBinaryTreeNode(value *Token, parent *BinaryTreeNode) (ret *BinaryTreeNode) {
   ret = &BinaryTreeNode{
       Tk: value,
       parent: parent,
   }
   return
}
//获取词条
func (node *BinaryTreeNode) GetToken() *Token {
   return node.Tk
}
func (node *BinaryTreeNode) GetHeight() int64 {
   return node.height
}

//BST结构
type BST struct {
   root    *BinaryTreeNode
}
//新建BST
func NewBinarySearchTree() (ret *BST) {
   ret = &BST{}
   return
}
//发现节点
func (tree *BST) FindNode(key int64) (target *BinaryTreeNode, hot *BinaryTreeNode) {
   root := tree.root
   for root != nil {
       if root.GetToken().GetKey() == key {
           target = root
           return
       } else if root.GetToken().GetKey() < key {
           hot = root
           root = root.right
       } else {
           hot = root
           root = root.left
       }
   }
   return
}
//插入节点
func (tree *BST) InsertNode(node *BinaryTreeNode) bool {
   if node == nil {
       return true
   }
   findToken, hot := tree.FindNode(node.GetToken().GetKey())
   //节点已存在
   if findToken != nil {
       return false
   }
   if hot == nil {//空树
       tree.root = node
       tree.root.parent = nil
       return true
   } else {
       if hot.GetToken().GetKey() < node.GetToken().GetKey() && hot.right == nil {
           node.parent = hot
           hot.right = node
           tree.UpdateHeight(node)
           return true
       } else if hot.GetToken().GetKey() > node.GetToken().GetKey() && hot.left == nil {
           node.parent = hot
           hot.left = node
           tree.UpdateHeight(node)
           return true
       } else {
           return false
       }
   }
}
//删除节点
func (tree *BST) DeleteNode(key int64) bool {
   target,hot := tree.FindNode(key)
   //节点不存在
   if target == nil {
       return false
   }
   if hot == nil {//根节点
       tree.root = nil
   } else {
       if hot.left == target {
           hot.left = nil
           hot.height = 0
           if hot.right != nil {
               hot.height = hot.right.height + 1
           }
       } else if hot.right == target {
           hot.right = nil
           hot.height = 0
           if hot.left != nil {
               hot.height = hot.left.height + 1
           }
       }
   }
   //由于左子树一定小于右子树，所以将右子树作为根树，左子树进行插入会落入左侧链的最低端，从而保持树的单调特性
   tree.InsertNode(target.right)
   tree.InsertNode(target.left)
   return true
}
//更新树高
func (tree *BST) UpdateHeight(node *BinaryTreeNode) {
   //持续向上迭代更新
   node = node.parent
   height := node.height + 1
   for node != nil {
       if node.height < height {
           node.height = height
       } else {
           break
       }
       node = node.parent
       height++
   }
}