针对少量的、无规则的数据，可以采用链表进行顺序查找 从头到尾依次逐个查找，直到找到所要的数据或搜索完整个数据序列。时间复杂度是O(n) 它的优点是插入比较快，但是查找比较慢。
1.2 有序数组（二分查找）针对有序数组，可以采用二分查找法（折半查找法） 基本原理： 首先讲要查找的元素月数组的中间元素比较 定义三个遍历，最小值，最大值，中间值，其中中间值=（最小值+最大值）/2 如果key小于中间值，把最大值的下标移动到中间值的前一个 如果key大于中间值，把最小值的下标移动到中间值的后一个。 如果key和中间元素相等，匹配成功，结束查找。
一般情况下二分查找比顺序查找快很多，是很多实际应用中经常被采用。 有序数组的二分查找法的不足：插入操作非常慢，需要后插入位置后的都要向后移动一位。
1.3 二叉查找树那么是否有同时保证查找、插入、删除操作效率都比较高的算法和数据结构呐？ 要满足插入的高效性，首先能想到的是链表，但是链表无法使用 查找时高效的二分查找法。而二叉查找树将二分查找的效率和链表的灵活性结合起来。也是这篇我们学习实践的重点。
还有对二叉树进行优化的平衡二叉查找树以及散列表，我们将在后面几篇进行学习实践。
图片来源于《算法》
二、二叉查找树（BST）通过上面一小节，我们了解到二叉查找树，结合了链表的灵活性以及数组的二分查找的高效性。这一小节，我们来了解二叉查找树数据结构，以及创建（插入）、查找（遍历）、删除过程。
先来看下二叉查找树的数据结构 二叉查找树使用的数据结构由结点组成，每个结点只能有一个父结点（跟结点除外），每个结点包含两个链接（也可以为空）分别指向左子结点和右子结点。
我们先来定义二叉查找树一个结点的结构体
template
struct BSTNode
{
BSTNode(const T& key = T())
: _left(nullptr)
, _right(nullptr)
, _key(key)
{}
BSTNode* _left;
BSTNode* _right;
T _key;
};
二叉查找树采用二叉树的中序遍历的方式进行创建插入。 如果树是空的，就返回一个包含该键值对的新结点，称为根结点。 如果被查找的键小于根结点的键，在左子树中插入该键，否则在右子树中插入。
具体实现如下
bool insertNode(const T& key)
{
//如果树为空，直接创建一个新结点进行插入
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//查找要插入的位置，从根结点作为比较的起始点
Node* cur = _root;
Node* parent = nullptr;
//通过下面这个while循环找到要插入的位置。也可以使用递归函数实现
while (cur)
{
//通过parent记录要出入结点的位置
parent = cur;
//要插入的值比当前结点值小，在其左子结点树上继续查找
if (key < cur->_key)
{
cur = cur->_left;
}
//否则，在其右子结点树上继续查找
else if (key >= cur->_key)
{
cur = cur->_right;
}
}
//插入元素
//生成新的结点
cur = new Node(key);
//和父节点进行比较，决定插入在左结点还是右结点
if (key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
从根结点开始查找，
具体实现如下
Node* find(const T& key)
{
Node* cur = _root;
//也可以改为递归的方式
//运用了高效的二分查找
while (cur)
{
if (cur->_key == key)
{
return cur;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
else
{
cur = cur->_right;
}
}
return nullptr;
}
删除结点分为以下三种情况
- 删除叶子结点、
- 删除有一个子树的结点；
- 删除有两个子树的结点。
这个比较复杂些。我们先把流程搞清楚，然后在通过代码实现
删除叶子结点
- 找到要删除的叶子结点 targetNode
- 找到targetNode的父节点parentNode
- 确定targetNode是parentNode的左子结点还是右子结点
- 进行删除 左子结点： parentNode.left = nullptr; 右子节点 parentNode.right = nullptr;
删除有一个子树的结点 这种情况要考虑，该结点的子结点是左子结点还是右子结点。以及该结点是其父节点的左子结点还是右子结点。具体步骤如下：
-
找到要删除的叶子结点 targetNode （同删除叶子结点第一步）
-
找到targetNode的父节点parentNode （同删除叶子结点第一步）
-
确定targetNode的子结点是左子结点还是右子结点
-
确定targetNode的是其parentNode结点的左子结点还是右子结点
-
如果targetNode的子结点是左子结点 如果targetNode是其父节点parentNode的左子结点 parentNode.left = targetNode.left
如果targetNode是其父结点parentNode的右子结点 parentNode.right = targetNode.left
-
如果targetNode的子结点是右子结点 如果targetNode是其父节点parentNode的左子结点 parentNode.left = targetNode.right
如果targetNode是其父结点parentNode的右子结点 parentNode.right = targetNode.right
删除有两个子树的结点 删除拥有两个子树的结点后，左子树和右子树又该如何和原结点建立关系呐？ 具体步骤如下
- 找到要删除的叶子结点 targetNode （同删除叶子结点第一步）
- 找到targetNode的父节点parentNode （同删除叶子结点第一步）
- 从tartgetNode的右子树中找到最小的结点（或者从targetNode的左子树中找到最大的结点）
- 用一个临时变量tmp存储该上一步找到结点的值
- 删除第3步找到的结点
- 把targetNode.key = tmp，即不改变链表的指向，只需要改变当前要删除结点的值即可。
梳理清楚上面的步骤后，我们看下通过代码如何实现结点的删除
bool delete(const T& key)
{
//如果树为空，删除失败
if (_root == nullptr)
{
return false;
}
//查找key在树中的位置
//targetNode的位置以及parentNode的位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (key == cur->_key)
{
break;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{
parent = cur;
cur = cur->_right;
}
}
//遍历了整棵树，如果key不在树中，无法删除
if (cur == nullptr)
{
return false;
}
//如果在树中找到了key，进行删除结点,要分三种情况：
//1.该结点是叶子结点
//2.该结点只有左子结点或者右子结点
//3.该结点左右子树都存在
//情况1
if (cur->_left == nullptr && cur->_right == nullptr)
{
if(cur == parent->_left)
{
parent->_left = nullptr;
}else
{
parent->_right = nullptr;
}
}
//情况2
else if (cur->_left == nullptr)
{
//情况2.1：
//只有根结点和根的右孩子，此时要删除的结点正好是树的根
if (cur == _root)
{
_root = cur->_right;
}
else
{
//或该结点不是树的根
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
}
//情况2.2：
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_right)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
}
else
{
//当前结点左右孩子都存在，直接删除不好删，可以在其子树中找一个替代结点，比如找其左子树中的最大结点，即左子树中最右侧的结点，或者找其右子树中最小的结点，即右子树中最小的结点。替换结点找到后，将替代结点中的值交给待删除结点，转换成删除替代结点。
if (cur->_left != nullptr || cur->_right != nullptr)
{
//找右子树中最小的结点替换待删除的结点
Node* repalce = cur->_right;
parent = cur;
while (repalce->_left)
{
parent = repalce;
repalce = repalce->_left;
}
cur->_key = repalce->_key;
if (repalce == parent->_left)
{
parent->_left = repalce->_right;
}
else
{
parent->_right = repalce->_right;
}
delete repalce;
repalce = nullptr;
}
return true;
}
return false;
}
