二分搜索树实现
二分搜索树实现
公众号guangcity
发布于 2019-10-31 14:43:22
发布于 2019-10-31 14:43:22
二分搜索树实现
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;
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-10-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录