数据结构-二叉树-二叉搜索树

一、概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者具有以下性质的二叉树：

若它的左子树不为空，则左树上所有节点的值都小于根节点的值。

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。

它的左右子树也分别为二叉搜索树。最多找O(N)。

二、查找、插入、删除

插入

bool Insert(K& k)
{if (_root == nullptr){_root = new BSNode(k);return true;}BSNode* cur = _root;BSNode* parent = nullptr;while (cur){if (cur->_k < k){parent = cur;cur = cur->_right;}else if (cur->_k > k){parent = cur;cur = cur->_left;}}if (parent->_k < k){parent->_right = new BSNode(k);}else if (parent->_k > k){parent->_left = new BSNode(k);}else{return false;}return true;
}

查找

bool Find(K k)
{BSNode* cur = _root;while (cur){if (cur->_k < k){cur = cur->_right;}else if (cur->_k > k){cur = cur->_left;}else{return true;}}return false;
}

删除

依次删除7、14、3、8。7和14属于直接删除的场景

3、8属于需要替换法进行删除的场景。

1、没有孩子

2、一个孩字

3、两个孩子，需要进行替换，也就是替换法，用左子树的最大节点或者右子树的最小节点。

最大节点为最右节点，最小节点就是最左节点 ，还需要处理要删除的节点为根节点，它没有左子树或者没有右子树的情况。

还有一种情况就是leftmax就是root的左子树的根，此时parent为nullptr所以我们需要让parent = cur

void Erase(K& k)
{BSNode* cur = _root;BSNode* parent = nullptr;while (cur){if (cur->_k < k){parent = cur;cur = cur->_right;}else if (cur->_k > k){parent = cur;cur = cur->_left;}else{//开始托孤//要删除的节点，左孩子为空if (cur->_left == nullptr){//需要判断删除节点就是根节点的情况if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}else {parent->_left = cur->_left;}}}else //两个孩子的情况，就需要替代法来删除{//找到左子树中最大的节点BSNode* leftMax = cur->_left;//注意为什么这里等于cur;BSNode* parent = cur;  while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}//找到以后把删除节点和leftmax节点的值做交换std::swap(cur->_k, leftMax->_k);//我们该把父亲的那个孩子和cur节点的孩子连接起来呢需要判断if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;cur = nullptr;}}
}

有序数组：二分查找，问题：插入删除效率不行

二叉搜索树：插入删除效率还行。

如果退化成下面的情况，插入删除的效率就变成了O(N)，所以我们引出了AVL树红黑树B树系列。

接下来我们看一下递归版本的删除，插入和发现

bool _EraseR(BSNode*& root, const K& k)
{if (root == nullptr){return false;}if (root->_k < k){_EraseR(root->_right, k);}else if (root->_k > k){_EraseR(root->_left, k);}else{BSNode* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{BSNode* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}std::swap(leftMax->_k, root->_k);return _EraseR(root->_left, k);}delete del;del = nullptr;return true;}
}
bool _InsertR(BSNode*& root,const K& k)
{if (root == nullptr){root = new BSNode(k);return true;}if (root->_k < k){_InsertR(root->_right, k);}else if (root->_k > k){_InsertR(root->_left, k);}else{return false;}
}
bool _FindR(BSNode* root, const K& k)
{if (root == nullptr)return false;BSNode* cur = root;if (cur->_k < k){_FindR(root->_right, k);}else if (cur->_k > k){_FindR(root->_left, k);}else{return true;}
}