binary search tree

二叉搜索树

Also known as sorted binary tree（sorted binary tree）,是指一棵空树或者具有下列性质的二叉树：
若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
任意节点的左、右子树也分别为二叉查找树;

特点：
All nodes on the left subtree have values ​​less than the root node value
All nodes on the right subtree have values ​​greater than the root node value

插入

迭代版本
We can use two pointers to find the previous position of the inserted position and insert it

bool Insert(const T &key) //迭代
    {
    
        //如果根节点为NULL
        if (_root == nullptr)
        {
    
            _root = new Node(key);
            return true;
        }
        Node *cur = _root;
        Node *prev = nullptr;

        while (cur)
        {
    
            if (cur->_key < key)
            {
    
                prev = cur;
                cur = cur->_left;
            }
            else if (cur->_key > key)
            {
    
                prev = cur;
                cur = cur->_right;
            }
            else
            {
    
                return false; //若是返回fasleIt means that the number has been inserted
            }
        }
        // preis the previous node to be inserted
        //将cur放到prev 合适的位置
        cur = new Node(key);
        if (prev->_key > key)
        {
    
            prev->_left = cur;
        }
        else
        {
    
            prev->_right = cur;
        }
        return true;
    }

• 递归
  We can also use recursive notation
  in tree operations,Understand the idea of ​​pre-inorder traversal,Many recursive operations are well understood

    bool InsertR(Node *&root, const T &key)
    {
    
        if (root == nullptr)
        {
    
            root = new Node(key);
            return true;
        }

        if (root->_key > key)
        {
    
            return _InsertR(root->_left, key); //Recursively return to the smallest left subtree
        }
        else if (root->_key < key)
        {
    
            return _InsertR(root->_right, key);//Recursively return to the smallest left subtree
        }
        else
        {
    
            return false;
        }
    }

删除

• 要删除的节点无孩子节点
• The node to be deleted has only the left child node
• 要删除的节点只有右孩子节点
• The node to be deleted has left and right child nodes

If only the right child

 if (cur->_left == nullptr)
                {
    
                    if (cur == _root) //若是根节点
                    {
    
                        _root = cur->_right;
                    }
                    else
                    {
    
                        if (prev->_left == cur)
                        {
    
                            prev->_left = cur->_right;
                        }
                        else
                        {
    
                            prev->_right = cur->_right;
                        }
                    }
                    delete cur;
                }

如果只有右孩子

 else if (cur->_right == nullptr)
                {
    
                    if (cur == _root)
                    {
    
                        _root = cur->_left;
                    }
                    else
                    {
    
                        if (prev->_left == cur)
                        {
    
                            prev->_left = cur->_left;
                        }
                        else
                        {
    
                            prev->_right = cur->_left;
                        }
                    }
                    delete cur;
                }

既有左孩子又有右孩子

Node *maxleft = cur->_left;
                    while (maxleft->_right)
                    {
    
                        maxleft = maxleft->_right;
                    }
                    T max = maxleft->_key;
                    Erase(maxleft);
                    cur->_key = max;

查找

Based on the tree-building characteristics of sorted binary trees,二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低.为{\displaystyle O(\log n)}O(\log n).But in extreme cases it may be inserted into a singly linked list,查找效率较低

    Node *Find(const T &key)
    {
    
        Node *cur = _root;
        while (cur)
        {
    
            if (key < cur->_key)
            {
    
                cur = cur->_left;
            }
            else if(key > cur->_key)
            {
    
                cur = cur->_right;
            }
            else
            {
    
                return cur;
            }
        }
        return nullptr;
    }