二分查找树是一种特殊的二叉树,它的每个节点都满足以下性质:

  • 如果它的左子树不为空,那么左子树上所有节点的值都小于它的根节点的值。
  • 如果它的右子树不为空,那么右子树上所有节点的值都大于它的根节点的值。

这样的二叉树可以方便地进行查找、插入和删除操作,因为每次只需要比较当前节点和目标值的大小,然后选择相应的子树继续操作。二分查找树的平均时间复杂度为 O(log n),其中 n 是节点的个数。

class BinarySearchTree {
private:
typedef struct TreeNode{
    int val;
    TreeNode* l, * r;
    TreeNode(int __val) : val(__val), l(0), r(0) {}
}*root;
public:
    void insert(TreeNode*& root, int val) {
        if (!root) root = new TreeNode(val);
        else if (root->val > val) insert(root->l, val);
        else insert(root->r, val);
    }
    void del(TreeNode*& root, int val) {
        if (!root) return ;
        if (root->val > val) del(root->l, val);
        else if (root->val < val) del(root->r, val);
        else {
            if (!root->l) root = root->r;
            else if (!root->r) root = root->l;
            else {
                TreeNode* p = root->r;
                while(p->l) p = p->l;
                root->val = p->val;
                del(root->r, p->val);
            }
        }
    }
}; 
分类: AlgorithmTree

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status