Binary search tree Binary search tree

Binary search tree Binary search tree

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

Binary search tree ADT

  • 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