# Binary search tree

The binary search tree is a special binary tree. The core properties of the data structure are:

For each node X in the tree, all key values ​​in its left subtree are less than the key value of X, and all key values ​​in its right subtree are greater than the key value of X

• MakeEmpty: Empty the binary search tree
• Find: Given the keyword value, return the node pointer of the keyword value
• FindMin and FindMax: return node pointers of the minimum key value and the maximum key value
• Insert: Insert a node with a given key value
• Delete: Delete a node with a specified key value

## Code

### Structure

type tree_data struct {
data int
}

type tree_node struct {
num int
data tree_data
left_point *tree_node
right_point *tree_node
parent *tree_node
}

### Constructor

func New_tree_node(num int, data tree_data, parent *tree_node) *tree_node {
node := tree_node{}
node.num = num
node.data = data
node.left_point = nil
node.right_point = nil
node.parent = parent
return &node
}

### Empty method

func (t *tree_node) MakeEmpty() {
if t.left_point != nil {
t.left_point.MakeEmpty()
}
if t.right_point != nil {
t.right_point.MakeEmpty()
}
t.num = 0
t.data = tree_data{}
}

### Find method

When searching:

• When the label to be checked is greater than the label of this node, query to the right subtree
• When the label to be checked is smaller than the label of this node, query to the left subtree
• When the label to be checked is equal to the label of this node, hit and return the pointer of this node
func (t *tree_node) Find(num int) (*tree_node, error) {
if num> t.num {
if t.right_point == nil {
return &tree_node{}, errors.New("num not exsist")
} else {
return t.right_point.Find(num)
}
} else if num <t.num {
if t.left_point == nil {
return &tree_node{}, errors.New("num not exsist")
} else {
return t.left_point.Find(num)
}
} else {
return t, nil
}
}

### Find the minimum/maximum method

func (t *tree_node) FindMin() *tree_node {
if t.left_point != nil {
return t.left_point.FindMin()
} else {
return t
}
}
func (t *tree_node) FindMax() *tree_node {
if t.right_point != nil {
return t.right_point.FindMax()
} else {
return t
}
}

### Insert method

When inserting:

• When the insertion label is greater than the node label, insert to the right subtree
• When the insertion label is smaller than the node label, insert to the left subtree
• When the inserted label is equal to the label of this node, overwrite the original value
func (t *tree_node) Insert(num int, data tree_data) {
if num> t.num {
if t.right_point != nil {
t.right_point.Insert(num, data)
} else {
t.right_point = New_tree_node(num, data, t)
}
} else if num <t.num {
if t.left_point != nil {
t.left_point.Insert(num, data)
} else {
t.left_point = New_tree_node(num, data, t)
}
} else {
t.data = data
}
}

### Delete method

When deleting, if the node is deleted, then:

• When the node has no subtree (it is a leaf), directly set the pointer of the parent node to the node nil(delete the node)
• When this node has only one subtree, directly replace this node with a child node
• When this node has two subtrees, find the smallest node a of the right node, replace the data and label of this node with the data and label of node a, and then delete node a recursively
func (t *tree_node) Delete(num int) {
if num <t.num {
t.left_point.Delete(num)
} else if num> t.num {
t.right_point.Delete(num)
} else {
if t.left_point == nil && t.right_point == nil {
if t.parent.left_point.num> t.num {
t.parent.left_point = nil
} else {
t.parent.right_point = nil
}
} else {
if t.left_point == nil {
t.parent = t.right_point
} else if t.right_point == nil {
t.parent = t.left_point
} else {
temp := t.right_point.FindMin()
t.num = temp.num
t.data = temp.data
temp.Delete(temp.num)
}
}
}
}
Reference: https://cloud.tencent.com/developer/article/1110763 Binary Search Tree Binary Search Tree-Cloud + Community-Tencent Cloud