二分搜索树实现

0.导语

目标：手写一个二分搜索树，完成二分搜索树的插入，删除，修改，查询，遍历等操作。

1.类封装与节点定义

★节点定义 ”

对于BST，我们定义节点包含指向左子树与指向右子树。

class BST {
/**
* 封装到私有,让外界不知道具体实现
*/
private:
    struct Node {
        Key key;
        Value value;
        Node *left;
        Node *right;

        Node(Key key, Value value) {
            this->key = key;
            this->value = value;
            this->left = this->right = NULL;
        }

        Node(Node *node) {
            this->key = node->key;
            this->value = node->value;
            this->left = node->left;
            this->right = node->right;
        }
    };

    Node *root;
    int count;
}

★构造与析构 ”

构造：

public:
    BST() {
        root = NULL;
        count = 0;
    }

析构：

public:
    ~BST() {
        destroy(root);
    }

在析构的时候，我们要释放节点内存，这颗BST树的所有节点内存释放是一个递归的过程，因此我们这里调用destroy递归函数，去递归释放节点内存。

private:
    void destroy(Node *node) {
        // 节点不为空
        if (node) {
            // 先释放左右孩子，再释放自身，所以下面先对左右孩子递归处理。
            destroy(node->left);
            destroy(node->right);
            // 最后释放自己
            delete node;
            count--;
        }
    }

2.BST内部具体函数实现

2.1 获取节点个数与是否是空的BST树

public:
    int size() {
        return count;
    }
    bool isEmpty() {
        return count == 0;
    }

2.2 插入节点

定义外部接口：

public:
    void insert(Key key, Value value) {
        root = insert(root, key, value);
    }

在插入的时候，给用户只提供插入key与value选择，具体的实现在内部屏蔽掉，这也就是封装。

定义内部接口：对于这个插入，代码里面实现了两种：递归插入与非递归插入。

2.2.1 递归插入

★思路 ”

递归插入后返回BST的根节点。首先明确递归终止条件：当节点为空，此时插入我们需要动态分配内存，new一个节点，并对BST树的节点个数+1。

具体插入过程：BST树特征是左孩子小于父亲，父亲又小于右孩子，因此要查找当前节点插入的位置，做if判断。

分为以下三种情况：

• 插入节点key与当前递归处的key相等，更新value
• 插入节点key大于当前递归处的key，递归右子树
• 插入节点key小于当前递归处的key，递归左子树

private:
   Node *insert(Node *node, Key key, Value value) {
        if (node == NULL) {
            count++;
            return new Node(key, value);
        }

        if (key == node->key)
            node->value = value;
        else if (key < node->key)
            node->left = insert(node->left, key, value);
        else
            node->right = insert(node->right, key, value);
        return node;
    }

2.2.2 非递归插入

★思路 ”

传递进来的节点如果为空，直接new一个，修改count值，返回当前节点。

否则开始对当前节点进行遍历，找到插入节点位置，由于在遍历的时候找到插入节点位置，此时要么为已经存在的key,此时直接更新value即可，要么不存在的key，此时必定在空节点处，因此我们需要保存一下前继节点，通过父亲来连接新插入的节点，这样就形成了一颗BST树。

private:
  Node *Non_Recursion_InsertNode(Node *node, Key key, Value value) {
        if (node == NULL) {
            node = new Node(key, value);
            count++;
            return node;
        }
        Node *pre = node;
        Node *cur = node;

        while (cur) {
            pre = cur;
            if (key == pre->key) {
                pre->value = value;
                return node;
            } else if (key < pre->key)
                cur = cur->left;
            else
                cur = cur->right;
        }
        if (key < pre->key)
            pre->left = new Node(key, value);
        else
            pre->right = new Node(key, value);
        count++;
        return node;
    }

2.3 查找key是否存在

同上，分为递归与非递归。

对外接口：

public:
 bool contain(Key key) {
        return contain(root, key);
    }

2.3.1 递归查找

利用BST树的性质，从当前节点，左孩子，右孩子进行查找。

递归终止条件：（1） 查找节点不存在，也就是最终node为NULL情况，返回false。（2） 待查找节点的key与树中某节点的key相等，返回true。

private:
   bool contain(Node *node, Key key) {
        if (node == NULL) return false;
        if (key == node->key) return true;
        else if (key < node->key)
            return contain(node->left, key);
        else
            return contain(node->right, key);
    }

2.3.4 非递归查找

private:
    bool Non_Recursion_Contain(Node *node, Key key) {
        if(node==NULL) return false;

        Mode* cur=node;
         while (cur) {
            if (key == node->key) {
                return true;
            } else if (key < node->key)
                cur = cur->left;
            else
                cur = cur->right;
        }
        return false;
    }

2.4 查询key对应的value或节点

同2.3，只是返回值不同。

public:
    Value *search(Key key) {
        return search(root, key);
    }
private:
    Value *search(Node *node, Key key) {
        if (node == NULL) return NULL;

        if (key == node->key) return &node->value;
        else if (key < node->key)
            return search(node->left, key);
        else
            return search(node->right, key);
    }

    Node* Search(Node *node, Key key) {
        if (node == NULL) return NULL;

        if (key == node->key) return node;
        else if (key < node->key)
            return Search(node->left, key);
        else
            return Search(node->right, key);
    }

2.5 删除节点

对外接口：

public:
    void remove(Key key) {
        root = remove(root, key);
    }

内部接口实现：

分为三种情况：

• 删除节点无左孩子,直接用右孩子代替当前节点，释放内存，节点减1,。
• 删除节点无右孩子，直接用左孩子代替。。。
• 删除节点有左孩子与右孩子，采用右孩子最小节点或左孩子最大节点代替。

private:
    Node *remove(Node *node, Key key) {
        if (node == NULL) return NULL;
        // 左孩子查找
        if (key < node->key) {
            node->left = remove(node->left, key);
            return node;
            // 右孩子查找
        } else if (key > node->key) {
            node->right = remove(node->right, key);
            return node;
            // 查找到了key
        } else { // key == node->key
            // 左孩子为空,就直接以右孩子取缔
            if (node->left == NULL) {         // 左孩子为空包含两部分(左孩子为空与左右孩子均为空)
                Node *rightNode = node->right;
                delete node;
                count--;
                return rightNode;
            }
            // 右孩子为空,就直接以左孩子取缔
            if (node->right == NULL) {
                Node *leftNode = node->left;
                delete node;
                count--;
                return leftNode;
            }
            // 左右孩子均不为空,取右孩子子树中最小或取左孩子子树中最大
            // node->left!=NULL && node->right!=NULL
            // 右孩子子树中最小方法
            Node *successor = new Node( minimum(node->right));       // 在removeMin中将最小节点删除了,后面再次访问successor会为NULL,所以此时需要重新new 分配内存
            count++;
            successor->right = removeMin(node->right);
            successor->left = node->left;
            delete node;
            count--;


            // 左孩子子树中最大方法
            /**
            Node *successor = new Node(maximum(node->left));
            count++;
            successor->left= removeMin(node->left);
            successor->right= node->right;
            delete node;
            count--;
            */
            return successor;
        }
    }

针对上述删除节点有左孩子与右孩子，采用右孩子最小节点或左孩子最大节点代替，因此需要有两个辅助函数。

★删除最小节点 ”

不断递归左孩子，直到当前节点的左孩子为空，那么这个节点就是最左节点，此时需要做三个动作：

• 保存当前节点的右孩子。
• 删除当前节点
• 返回右孩子。

private:
    Node *removeMin(Node *node) {
        if (node->left == NULL) {
            Node *rightNode = node->right;
            delete node;
            count--;
            return rightNode;
        }
        node->left = removeMin(node->left);
        return node;
    }

同样非递归实现如下：

private:
    // 非递归 返回curNode->right节点
    Node *removeMin1(Node *node) {
        Node *root = node;
        Node *currentNode = node, *p = node;
        Node *parentNode = node;
        // 空
        if (currentNode == NULL)
            return NULL;
        // 迭代
        while (currentNode->left != NULL) {
            parentNode = currentNode;
            currentNode = currentNode->left;
        }
        // 传递进来的左孩子本身就为空
        if (currentNode == parentNode) {
            Node *tmp = currentNode->right;
            delete currentNode; // 此时的currentNode为最大节点
            count--;
            return tmp;
        }
        // 传递进来的左孩子本身不为空,而是通过迭代到最小节点
        parentNode->left = currentNode->right;
        // 删除掉currentNode
        delete currentNode; // 此时的currentNode为最小节点
        count--;
        return p;
    }

★删除最大节点： ”

刚好与上述相反，递归右

private:
    Node *removeMax(Node *node) {
        if (node->right == NULL) {
            Node *leftNode = node->left;
            delete node;
            count--;
            return leftNode;
        }
        node->right= removeMax(node->right);
        return node;
    }

非递归如下：

private:
    // 非递归
    Node *removeMax1(Node *node) {
        Node *currentNode = node, *p = node;
        Node *parentNode = node;
        if (currentNode == NULL)
            return currentNode;

        while (currentNode->right != NULL) {
            parentNode = currentNode;
            currentNode = currentNode->right;
        }
        if (currentNode == parentNode) {
            Node *tmp = currentNode->left;
            delete currentNode; // 此时的currentNode为最大节点
            count--;
            return tmp;
        }
        parentNode->right = currentNode->left;
        delete currentNode; // 此时的currentNode为最大节点
        count--;
        return p;
    }

上述的对外接口如下：

public:
    void removeMin() {
        if (root)
            root = removeMin(root);
    }

    void removeMax() {
        if (root)
            root = removeMax(root);
    }

根据上面我们可以得出如何获得BST的最大与最小：

public:
    // 向左找,为最小
    // 向右找,为最大
    Key minimum() {
        assert(count != 0);
        Node *minNode = minimum(root);
        return minNode->key;
    }

    Key maximum() {
        assert(count != 0);
        Node *maxNode = maximum(root);
        return maxNode->key;
    }

内部实现：

private:
   Node *minimum(Node *node) {
        if (node->left == NULL) return node;
        return minimum(node->left);
    }

    // 非递归
    Node *minimum1(Node *node) {
        Node *currentNode = node;
        if (currentNode == NULL)
            return NULL;

        while (currentNode->left != NULL) {
            currentNode = currentNode->left;
        }
        return currentNode;
    }

    Node *maximum(Node *node) {
        if (node->right == NULL) return node;
        return maximum(node->right);
    }

    // 非递归
    Node *maximum1(Node *node) {
        Node *currentNode = node;
        if (currentNode == NULL)
            return NULL;

        while (currentNode->right != NULL) {
            currentNode = currentNode->right;
        }
        return currentNode;
    }

最后，在给出remove的非递归删除：

private:
    // 以左侧最大取代非递归删除
    Node *deleteNode(Node *root, Key key) {
        if (root == NULL) return NULL;
        Node *currentNode = root;
        Node *parentNode = root;

        //定位到要删除的key 的父节点,以及当前元素
        while (currentNode != NULL && currentNode->val != key) {
            parentNode = currentNode;
            if (currentNode->key > key) {
                currentNode = currentNode->left;
            } else {
                currentNode = currentNode->right;
            }

        }
        // 表示没找到key,直接返回结果
        if (currentNode == NULL) return root;
        // 表示与key相等的是根节点,根节点直接处理,不需要保存父节点
        if (parentNode == currentNode) {
            // 左分支为空,以右分支取缔
            if (currentNode->left == NULL) {
                Node *tmp = currentNode->right;
                delete currentNode;
                count--;
                return tmp;
            }
            // 右分支为空,以左分支取缔
            if (currentNode->right == NULL) {
                Node *tmp = currentNode->left;
                delete currentNode;
                count--;
                return tmp;
            }
            // 取左分支最大节点取代当前节点,并删除当前节点
            Node *delnode = new Node(maximum1(currentNode->left)->val);
            delnode->left = removeMax1(currentNode->left);
            delnode->right = currentNode->right;
            delete currentNode;
            count--;
            return delnode;
        }
        // key不是根节点,需要判断父节点与当前节点的关系,有可能是右分支,也可能是左分支

        // 左分支关系
        if (parentNode->left == currentNode) {
            if (currentNode->left == NULL) {
                parentNode->left = currentNode->right;
                delete currentNode;
                count--;
                return root;
            }
            if (currentNode->right == NULL) {
                parentNode->left = currentNode->left;
                delete currentNode;
                count--;
                return root;
            }
            Node *delnode = new Node(maximum1(currentNode->left)->val);
            count++;
            delnode->left = deleteMax(currentNode->left);
            delnode->right = currentNode->right;
            // 父节点左孩子更新为左边最大的节点
            parentNode->left = delnode;
            delete currentNode;
            count--;
            return root;
        }
        // 右分支关系
        if (parentNode->right == currentNode) {
            if (currentNode->left == NULL) {
                parentNode->right = currentNode->right;
                delete currentNode;
                count--;
                return root;
            }
            if (currentNode->right == NULL) {
                parentNode->right = currentNode->left;
                delete currentNode;
                count--;
                return root;
            }
            Node *delnode = new Node(maximum1(currentNode->left)->val);
            count++;
            delnode->left = removeMax1(currentNode->left);
            delnode->right = currentNode->right;
            // 父节点右孩子更新为左边最大的节点
            parentNode->right = delnode;
            delete currentNode;
            count--;
            return root;
        }
        return root;
    }

2.6 BST遍历

2.6.1 前中后遍历

四种遍历的外部接口：

以前序遍历为例，其余一样：

public:
    vector<pair<Key, Value>> preOrder() {
        vector<pair<Key, Value>> res;
        preOrder(root, res);
        return res;
    }
private:
    void preOrder(Node *node, vector<pair<Key, Value>> &res) {
        if (node) {
            res.push_back(make_pair(node->key, node->value));
            preOrder(node->left, res);
            preOrder(node->right, res);
        }
    }

非递归实现：

使用栈，每个节点绑定一个tag,每个节点分为访问与遍历两种情况，我们根据先序遍历与栈的特点，先访问的后入栈。

private:
    enum Tag {
        visit, print
    };

    struct Command {
        Tag tag;
        Node *node;

        Command(Tag t, Node *n) : tag(t), node(n) {}
    };

public:
    vector<pair<Key, Value>> _preOrder() {
        vector<pair<Key, Value>> res;
        if (root == NULL) return res;
        stack<Command> stack;
        stack.push(Command(visit, root));
        while (!stack.empty()) {
            Command command = stack.top();
            stack.pop();
            if (command.tag == print)
                res.push_back(make_pair(command.node->key, command.node->value));
            else {
                if (command.node->right)
                    stack.push(Command(visit, command.node->right));
                if (command.node->left)
                    stack.push(Command(visit, command.node->left));
                stack.push(Command(print, command.node));
            }
        }
        return res;
    }

其余遍历只是代码上下位置修改一下即可。

2.6.1 层次遍历

层次遍历使用队列，一层一层遍历。

public:
    vector<pair<Key, Value>> levelOrder() {
        vector<pair<Key, Value>> res;
        queue<Node *> q;
        q.push(root);
        while (!q.empty()) {
            Node *node = q.front();
            q.pop();
            res.push_back(make_pair(node->key, node->value));
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        return res;
    }

2.7 前驱与后继

2.7.1 获取对应key的前驱

对外接口：

public:
    Node *predecessor(Key key) {
        return predecessor(root, key);
    }

内部接口具体实现：

• 左孩子不为空，前驱就是左孩子的最大节点
• 左孩子为空，自底向上递归查找距离当前节点最近的左拐节点

private:
   Node *predecessor(Node *root, Key key) {

        Node *node = Search(root, key);
        // 如果key所在的节点不存在, 则key没有前驱, 返回NULL
        if (node == NULL)
            return NULL;

        // 如果key所在的节点左子树不为空,则其左子树的最大值为key的前驱
        if (node->left != NULL)
            return maximum(node->left);

        // 否则, key的前驱在从根节点到key的路径上, 在这个路径上寻找到比key小的最大值, 即为key的前驱
        Node *preNode = predecessorFromAncestor(root, key);
        return preNode == NULL ? NULL : preNode;
    }

因此要编写一个函数来实现求当前节点的最近左拐节点，实际上就是求距离给定节点最近的节点，且此节点为父亲节点的右子树中。

从根节点开始递归查找，如果查找的key小于node的key，那么继续往左孩子查找，如果一直为左孩子，就找不到，那么就是递归终止条件的NULL。如果能找到就意味着某处进行了右拐，也就是key大于了node的key，此时当前节点有可能为距离最近的节点，因此先暂存一下，继续到右孩子递归，如果tmpNode与目标节点之间是相邻的，也就是tmpNode为NULL，那么直接返回node即可，否则说明之间有其他节点，返回tmpNode即可。

如下：3的前驱是2，但1有可能是，所以继续往后递归，就是前面的描述意思。

1
 \
  2
   \
    3

实现如下：

private:
    Node *predecessorFromAncestor(Node *node, Key key) {
        if (node->key == key)
            return NULL;
        if (key < node->key) {     // 我们目标是找比key小的最大key,如果比node的key小就应该在它的左子树中查找
            return predecessorFromAncestor(node->left, key);
        } else {      // 此时的key小于node的key在右子树中查找
            assert(key > node->key);
            /**
             * 如果当前节点小于key,则当前节点有可能是比key小的最大值
             * 向右继续搜索,将结果存储到tmpNode中
             */
            Node *tmpNode = predecessorFromAncestor(node->right, key);
            if (tmpNode)
                return tmpNode;
            else
                // 如果tmpNode为空,则当前节点即为结果
                return node;
        }
    }

非递归实现：

private:
    Node *_predecessorFromAncestor(Node *node, Key key) {
        Node *firstRParent = NULL;
        while (node) {
            if (node->key == key) {
                return firstRParent;
            }
            if (node->key > key) {
                node = node->left;
            } else if (node->key < key) {
                firstRParent = node;        //出现右拐点
                node = node->right;
            }
        }
        return firstRParent;
    }

2.7.2 获取对应key的后继

外部接口：

public:
    Node *successor(Key key) {
        return successor(root, key);
    }

内部实现：

• 当前节点右孩子不为空，查找右孩子最小节点
• 当前节点右孩子为空，网上查找第一个左拐节点。

private:
    // 查找key的后继, 递归算法
    // 如果不存在key的后继(key不存在, 或者key是整棵二叉树中的最大值), 则返回NULL
    Node *successor(Node *root, Key key) {

        Node *node = Search(root, key);
        // 如果key所在的节点不存在, 则key没有前驱, 返回NULL
        if (node == NULL)
            return NULL;

        // 如果key所在的节点右子树不为空,则其右子树的最小值为key的后继
        if (node->right != NULL)
            return minimum(node->right);

        // 否则, key的后继在从根节点到key的路径上, 在这个路径上寻找到比key大的最小值, 即为key的后继
        Node *sucNode = successorFromAncestor(root, key);
        return sucNode == NULL ? NULL : sucNode;
    }

因此需要编写网上查找的第一个左拐节点：

递归实现：

实现同上述的右拐节点相对称。

private:
    /**
     * 在node为根的二叉搜索树中,寻找key的祖先中,比key大的最小值所在节点.递归算法
     * 算法调用前已保证key存在在以node为根的二叉树中
     * @param node
     * @param key
     * @return
     */
    Node *successorFromAncestor(Node *node, Key key) {
        if (node->key == key)
            return NULL;
        if (key > node->key) {     // 我们目标是找比key大的最小key,如果比node的key大就应该在它的右子树中查找
            return successorFromAncestor(node->right, key);
        } else {      // 此时的key小于node的key在左子书中查找
            assert(key < node->key);
            /**
             * 如果当前节点大于key,则当前节点有可能是比key大的最小值
             * 向左继续搜索,将结果存储到tmpNode中
             */
            Node *tmpNode = successorFromAncestor(node->left, key);
            if (tmpNode)
                return tmpNode;
            else
                // 如果tmpNode为空,则当前节点即为结果
                return node;
        }
    }

非递归实现：

private:
    Node *_successorFromAncestor(Node *node, Key key) {
        Node *firstLParent = NULL;
        while (node) {
            if (node->key == key) {
                return firstLParent;
            }
            if (node->key < key) {
                node = node->right;
            } else if (node->key > key) {
                firstLParent = node;        //出现右拐点
                node = node->left;
            }
        }
        return firstLParent;
    }

2.8 floor与ceil实现

2.8.1 floor实现

查找与给定key距离最近，且小于等于目标key的key。外部接口：

    Node *floor(Key key) {
        // 空树或给定的key超过树中最大的key
        if (count == 0 || key < minimum()) return NULL;
        return floor(root, key);
    }

内部实现：

• 如果node的key值和要寻找的key值相等，则node 本身就是key的floor节点。
• 如果node的key比要寻找的key大，则要寻找的key的floor节点一定在node的左边子树中。
• 如果node的key小于要寻找的key，则node有可能是key的floor节点,也有可能不是(存在比node->key大但小于key的其余节点)，则要尝试向node的右子树寻找一下。

private:
    Node *floor(Node *root, Key key) {
        if (root == NULL) return NULL;

        // 如果node的key值和要寻找的key值相等
        // 则node 本身就是key的floor节点
        if (key == root->key) return root;
        // 如果node的key比要寻找的key大
        // 则要寻找的key的floor节点一定在node的左边子树中
        if (root->key > key) return floor(root->left, key);
        // 如果node的key小于要寻找的key
        // 则node有可能是key的floor节点,也有可能不是(存在比node->key大但小于key的其余节点)
        // 则要尝试向node的右子树寻找一下
        Node *tmpNode = floor(root->right, key);
        if (tmpNode) return tmpNode;
        return root;
    }

2.8.2 ceil实现

对外接口：

private:
    Node *ceil(Key key) {
        // 空树或给定的key超过树中最大的key
        if (count == 0 || key > maximum()) return NULL;
        return ceil(root, key);
    }

• 如果node的key值和要寻找的key值相等则node 本身就是key的ceil节点.
• 如果node的key比要寻找的key小,则要寻找的key的ceil节点一定在node的右边子树中。
• 如果node的key大于要寻找的key，则node有可能是key的ceil节点,也有可能不是(存在比node->key小但大于key的其余节点)，则要尝试向node的左子树寻找一下。

private:
    Node *ceil(Node *root, Key key) {
        if (root == NULL) return NULL;

        // 如果node的key值和要寻找的key值相等
        // 则node 本身就是key的ceil节点
        if (key == root->key) return root;
        // 如果node的key比要寻找的key小
        if (root->key < key) return ceil(root->right, key);
        // 如果node的key大于要寻找的key
        // 则node有可能是key的ceil节点,也有可能不是(存在比node->key小但大于key的其余节点)
        // 则要尝试向node的左子树寻找一下
        Node *tmpNode = ceil(root->left, key);
        if (tmpNode) return tmpNode;
        return root;
    }