专栏首页光城(guangcity)二分搜索树实现

二分搜索树实现

二分搜索树实现

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;
    }

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • STL之set与multiset那些事

    set/multiset以rb_tree为底层结构,因此有元素自动排序特性。排序的依据是key,而set/multiset元素的value和key合二为一:va...

    公众号guangcity
  • 再也不用担心STL的红黑树了。。。

    STL中Red-black tree(红黑树)class,用来当做SLT关系式容器(如set,multiset,map, multimap).里面所用的inse...

    公众号guangcity
  • 知识图谱系列之Neo4J

    上次写了一篇文章提到了一个有关知识图谱的概念,在本公众号中,并未写有关这方面的文章,那么这一节从python与neo4j方向来共同学习知识图谱的一些实战操作,后...

    公众号guangcity
  • 数据结构之映射Map

    1、映射Map,存储键值数据对的数据结构(key,value),可以根据键key快速寻找到值Value,可以使用链表或者二分搜索树实现的。

    别先生
  • ElasticSearch5.x安装Elasticsearch-head插件

    去https://github.com/mobz/elasticsearch-head下载代码上传到服务器上

    試毅-思伟
  • WebDriver多线程并发

    要想多线程并发的运行WebDriver,必须同时满足2个条件,首先你的测试程序是多线程,其次需要用到Selenium Server。下载位置如下图:

    流柯
  • 教学大师奖、杰出教学奖和创新创业英才奖在杭州颁发

    10月15日,中国首届“教学大师奖、杰出教学奖和创新创业英才奖”在杭州颁发。清华大学姚期智院士获得教学大师奖,北京大学黄如、复旦大学闻玉梅、南京大学卢德馨、浙...

    腾讯高校合作
  • 排序数组转换为二叉查找树

    已知一个排序的数组,将该数组转换为一个高度平衡的二叉查找树。 平衡的定义: 二叉查找树中,任意节点的两颗子树高度差不超过1. LeetCode 108

    小飞侠xp
  • 虚拟CPE和SD-WAN功能逐步走向融合

    对服务提供商而言,虚拟客户端设备(vCPE)以及软件定义广域网(SD-WAN)是能够实现业务目标的不同选择,最终目的都是要向用户提供托管服务。因此,服务提供商面...

    SDNLAB
  • 补充下3月面试题(好未来、腾讯音乐、小药药)

    补充一下落下的3月份的面试题,关于春季面经可以看我的上文 。从出师不利、面面具挂,到拿到阿里2个offer

    zz_jesse

扫码关注云+社区

领取腾讯云代金券