【数据结构】二叉搜索树–BST，Binary Search Tree

文章目录

• 二叉搜索树
• • 1. 二叉搜索树的概念
  • 2. 二叉搜索树的接口
  • • 2.1 查找
    • • 非递归查找
      • 递归查找
    • 2.2 中序遍历
    • 2.3 插入
    • • 非递归插入
      • 递归插入
    • 2.4 删除
    • • 非递归删除
      • 递归删除
  • 3. 二叉搜索树的应用
  • • key搜索模型
    • kv搜索模型
  • 5. oj题

二叉搜索树

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它可以是一颗空树，或者是一个满足如下性质的二叉树：

• 如果左子树不为空，左子树上所有节点的值都小于根节点；
• 如果右子树不为空，右子树上所有节点的值都大于根节点；

且它的左右子树，也满足上述性质。

举个栗子吧，以6为根节点的BST树结构：

template<class K>
struct bstree_node
{
    bstree_node<K>(K key)
        : _left(nullptr), _right(nullptr), _key(key)
    {}

    bstree_node<K>* _left;
    bstree_node<K>* _right;
    K _key;
};

template<class K>
class bstree
{
public:
  typedef bstree_node<K> node;
private:
    node* _root = nullptr;
};

两个又相同数组构成的二叉树，但是却形成了两个不同树结构。二叉搜索树最大的问题是会退化，比如右单枝，顺序插入时就会退化成一个链表。

搜索二叉树的效率体现在搜索上，最坏情况搜索高度次。所以树的高度越低，性能越好。所以一般不会使用单纯的搜索二叉树，而是使用升级版的AVL 树（平衡二叉搜索树）和红黑树

大概了解一下
AVL 树（平衡二叉搜索树）：

红黑树

2. 二叉搜索树的接口

2.1 查找

若根节点不为空：

• 如果节点值等于 $key$
• 如果节点值小于 $key$
• 如果节点值大于 $key$

走到空树还没找到，则返回

f

a

l

s

e

false

false。

非递归查找

bool find(const K& key)
{
    // 从根节点开始查找
    node* cur = _root;

    // 循环遍历树，直到当前节点为空（即没有找到）
    while (cur)
    {
        // 如果查找的键值小于当前节点的键值
        if (key < cur->_key)
        {
            // 移动到当前节点的左子节点，因为左子节点的键值更小
            cur = cur->_left;
        }
        // 如果查找的键值大于当前节点的键值
        else if (key > cur->_key)
        {
            // 移动到当前节点的右子节点，因为右子节点的键值更大
            cur = cur->_right;
        }
        // 如果查找的键值等于当前节点的键值
        else
        {
            return true;
        }
    }

    return false;
}

二叉搜索树的查找非常的迅速，在二叉树相对平衡的情况下，时间复杂度高度次

O

(

l

o

g

N

)

O(logN)

O(logN)。最差是线性状态，为

O

(

N

)

O(N)

O(N)。

递归查找

递归函数 find_r 会沿着树的结构向下搜索，每次比较 key 和当前节点的键值，决定向左或向右移动。这种递归调用会一直持续到找到匹配的键值或者遍历完整个树。

基本情况（终止条件）：
如果 root 是 nullptr，表示已经到达了树的末端，没有找到匹配的键值，因此返回 false。

递归调用：
如果 key 小于 root->_key，说明要查找的键值可能在左子树中，因此递归调用 _find_r(root->_left, key)。
如果 key 大于 root->_key，说明要查找的键值可能在右子树中，因此递归调用 _find_r(root->_right, key)。

找到匹配键值：
如果 key 等于 root->_key，表示找到了匹配的键值，立即返回 true。

bool find_r(const K& key)
{
    return _find_r(_root, key);
}

bool _find_r(node* root, const K& key)
{
    if (root == nullptr)
        return false;

    if (key < root->_key)
        return _find_r(root->_left, key);
    else if (key > root->_key)
        return _find_r(root->_right, key);
    else
        return true;
}

2.2 中序遍历

二叉搜索树的中序遍历结果，就是树中元素排成升序的结果。

void inorder()
{
    _inorder(_root);
    std::cout << std::endl;
}

void _inorder(node* root)
{
    if (root == nullptr)
        return;

    _inorder(root->_left);
    std::cout << root->_key << " ";
    _inorder(root->_right);
}

一般成员函数在类外调用时，无法直接传入成员变量作参数。故可以将主体逻辑包装成子函数，再由成员函数去调用即可。

void TestBSTree() 
{
    BSTree<int> t;
    int a[] = { 7,1,3,6,4,8,7,9,3,2,5 }; //排序数组
    for (auto e : a) {
        t.Insert(e); //插入二叉搜索树
    }
    t.Inorder(); //中序遍历
}

如上代码，相当于利用二叉搜索树排序数组，而二叉搜索树结构天然具有排序加去重的功能。

2.3 插入

二叉搜索树的插入也很简单，共分两种情况：

1. 树为空，则直接插入，
2. 树不为空，则按性质查找到插入位置，再插入新节点。

cur指针进行比较并向下移动的同时，父指针parent始终指向cur的父节点。当cur走到空的时候，就创建新节点并链接到父节点的指针上。

1. 插入的值比当前节点的值小，则插入到左子树中，
2. 反之，比当前节点的值大，则插入到右子树中。

非递归插入

非递归插入方法通过迭代遍历二叉搜索树来找到新节点的插入位置。首先检查树是否为空，如果是，则直接将新节点设为根节点。如果树不为空，则从根节点开始，使用一个当前节点指针 cur 和一个父节点指针 parent 来跟踪遍历过程。在遍历过程中，根据新键值与当前节点键值的比较结果，决定向左子树还是右子树移动。如果新键值小于当前节点键值，则移动到左子节点；如果大于，则移动到右子节点。如果遇到相同键值的节点，则插入失败并返回 false。当 cur 为空时，表示已经到达了插入位置，此时根据新键值与 parent 节点键值的比较结果，在父节点的左或右子节点位置插入新节点。这种方法直观且易于理解，不需要额外的栈空间，适用于大多数情况下的树操作。

bool insert(const K& key)
{
    // 如果根节点为空，直接将新节点作为根节点
    if (_root == nullptr)
    {
        _root = new node(key);
        return true;
    }

    node* cur = _root;
    node* parent = nullptr;

    // 循环找到合适的插入位置
    while (cur)
    {
        if (key < cur->_key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (key > cur->_key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
            return false; // 如果存在相同键值的节点，不插入
    }

    // 根据键值大小插入新节点
    if (key < parent->_key)
        parent->_left = new node(key);
    else
        parent->_right = new node(key);

    return true;
}

可见，二叉搜索树的每次插入都是把节点放在叶节点的位置上。

递归插入

递归插入方法通过递归调用函数自身来遍历二叉搜索树，并找到新节点的插入位置。递归函数 _insert_r 接受当前节点指针的引用和要插入的键值作为参数。如果当前节点为空，表示到达了插入位置，此时创建一个新节点并将其赋值给当前节点指针，然后返回 true 表示插入成功。如果新键值小于当前节点键值，则递归调用函数在左子树中继续查找插入位置；如果新键值大于当前节点键值，则递归调用函数在右子树中查找。如果遇到相同键值的节点，则返回 false 表示插入失败。递归插入方法简洁优雅，代码量少，但可能会因为递归调用导致栈空间的使用增加，对于大型树结构可能存在性能问题。然而，对于小型或中型树结构，递归插入是一种高效且易于实现的方法。

bool insert_r(const K& key)
{
    return _insert_r(_root, key);
}

bool _insert_r(node*& root, const K& key)
{
    // 如果当前节点为空，创建新节点并返回true
    if (root == nullptr)
    {
        root = new node(key);
        return true;
    }

    // 根据键值大小递归插入左子树或右子树
    if (key < root->_key)
        return _insert_r(root->_left, key);
    else if (key > root->_key)
        return _insert_r(root->_right, key);
    else
        return false; // 如果存在相同键值的节点，不插入
}

参数类型是节点指针的引用，使得root不仅是节点指针，还是其父节点的左或右孩子指针，修改root也就修改了父节点的左右孩子。

2.4 删除

二叉搜索树的难点在于删除，因为节删除节点需要维护剩余节点的链接关系。

删除叶节点很容易，释放节点并置空父节点的指针即可。删除非叶结点，可以将子树中满足条件的节点替换上来。

如果节点不存在先返回

f

a

l

s

e

false

false，如果存在，则分以下几种情况：
1.直接删除：

2.替换删除：

1. 先将左树最大节点的左孩子托，或是右树最小节点的右孩子托付给父节点。
2. 再将左树最大节点覆盖待删除的节点。

非递归删除

bool erase(const K& key)
{
node* parent = nullptr; // 父节点指针初始化为nullptr
node* cur = _root; // 当前节点指针指向根节点
while (cur) // 循环遍历直到当前节点为空
{
if (key < cur->_key) // 如果搜索键小于当前节点键值
{
parent = cur; // 更新父节点指针为当前节点
cur = cur->_left; // 移动到左子节点
}
else if (key > cur->_key) // 如果搜索键大于当前节点键值
{
parent = cur; // 更新父节点指针为当前节点
cur = cur->_right; // 移动到右子节点
}
else // 如果搜到到匹配的键值
{
if (!cur->_left) // 如果当前节点没有左子节点
{
if (parent == nullptr)
_root = _root->_right;
else if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
delete cur; // 删除当前节点
}
else if (!cur->_right) // 如果当前节点没有右子节点
{
if (parent == nullptr)
_root = _root->_left;
else if (cur == parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
delete cur; // 删除当前节点
}
else // 如果当前节点有左右子节点
{
#ifdef 方式1 // 采用方式1删除节点--直接删除
node* min = cur->_right; // 当前节点的右子树中找到最小节点
while (min->_left)
min = min->_left;
K minkey = min->_key;
erase(min->_key);
cur->_key = minkey;
#endif
#ifdef 方式2 // 采用方式2删除节点--替换删除
node* min_parent = cur; // 最小节点的父节点
node* min = cur->_right; // 当前节点的右子树中找到最小节点
while (min->_left)
{
min_parent = min;
min = min->_left;
}
cur->_key = min->_key; // 更新当前节点的键值为最小节点的键值
if (min == min_parent->_left)
min_parent->_left = min->_right;
else
min_parent->_right = min->_right;
delete min; // 删除最小节点
#endif
}
return true;
}
}
return false;
}

递归删除

bool erase_r(const K& key)
{
// 调用递归删除函数，传入根节点指针和搜索键值
return _erase_r(_root, key);
}
bool _erase_r(node*& root, const K& key)
{
// 如果当前子树根节点为空，返回false
if (root == nullptr)
return false;
// 根据搜索键值与当前节点键值的比较，决定进入左子树或右子树进行递归删除
if (key < root->_key)
return _erase_r(root->_left, key);
else if (key > root->_key)
return _erase_r(root->_right, key);
else
{
// 保存当前节点指针
node* del = root;
// 如果当前节点没有左子节点，将右子节点替换当前节点
if (!root->_left)
root = root->_right;
// 如果当前节点没有右子节点，将左子节点替换当前节点
else if (!root->_right)
root = root->_left;
else
{
// 寻找右子树中的最小节点
node* min = root->_right;
while(min->_left)
min = min->_left;
root->_key = min->_key; // 更新当前节点键值为最小节点键值
// 递归删除最小节点，并返回结果
return _erase_r(root->_right, min->_key);
}
// 释放删除节点
delete del;
return true; // 返回删除成功
}
}

3. 二叉搜索树的应用

搜索树有两种应用，key搜索模型和key/value搜索模型。此外，二叉搜索树插入重复值会失败，所以自带去重功能。

key搜索模型

key搜索模型查找返回真假，只能用来判断数据是否存在。应用场景如存储车牌号判断是否放行等。

kv搜索模型

通过key查找对应value，两个值是强相关的映射关系。 应用场景如中英互译，身份绑定等。

cpp
Copy code
// 结构体定义包括键值对节点和左右子节点指针
template<class K, class V>
struct bstree_node
{
bstree_node<K, V>* _left;
bstree_node<K, V>* _right;
K _key;
V _val;
// 构造函数初始化键、值和左右子节点指针
bstree_node<K, V>(const K& key, const V& val)
: _key(key), _val(val), _left(nullptr), _right(nullptr)
{}
};
// 二叉搜索树类
template<class K, class V>
class bstree
{
typedef bstree_node<K, V> node; // 节点类型定义为树节点结构体
public:
// 插入节点函数，传入键值和值，返回插入是否成功
bool insert(const K& key, const V& val)
{
if (_root == nullptr) // 如果根节点为空
{
_root = new node(key, val); // 创建新节点作为根节点
return true;
}
node* parent = nullptr; // 父指针初始化为空
node* cur = _root; // 当前节点指针指向根节点
while (cur) // 循环查找插入位置
{
if (key < cur->_key) // 如果插入键值小于当前节点键值
{
parent = cur; // 更新父指针为当前节点
cur = cur->_left; // 移动到左子节点
}
else if (key > cur->_key) // 如果插入键值大于当前节点键值
{
parent = cur; // 更新父指针为当前节点
cur = cur->_right; // 移动到右子节点
}
else
return false; // 如果键值相等，返回失败
}
if (key < parent->_key) // 根据父节点键值判断位置插入左子节点或右子节点
parent->_left = new node(key, val); // 创建新节点作为左子节点
else if (key > parent->_key)
parent->_right = new node(key, val); // 创建新节点作为右子节点
return true; // 返回插入成功
}
// 查找键值对应节点，返回找到的节点指针，如果不存在返回空指针
node* find(const K& key)
{
node* cur = _root; // 当前节点指针指向根节点
while (cur) // 循环查找节点
{
if (key < cur->_key) // 如果搜索键值小于当前节点键值
cur = cur->_left; // 移动到左子节点
else if (key > cur->_key) // 如果搜索键值大于当前节点键值
cur = cur->_right; // 移动到右子节点
else
return cur; // 找到匹配键值时返回当前节点
}
return nullptr; // 没找到返回空指针
}
// 删除节点函数，传入键值，返回删除是否成功
bool erase(const K& key)
{
node* parent = nullptr; // 父节点指针初始化为空
node* cur = _root; // 当前节点指针指向根节点
while (cur) // 循环查找删除节点
{
if (key < cur->_key) // 如果键值小于当前节点键值
{
parent = cur; // 更新父节点指针为当前节点
cur = cur->_left; // 移动到左子节点
}
else if (key > cur->_key) // 如果键值大于当前节点键值
{
parent = cur; // 更新父节点指针为当前节点
cur = cur->_right; // 移动到右子节点
}
else // 找到匹配键值的节点
{
if (!cur->_left) // 如果当前节点没有左子节点
{
if (!parent) // 如果父节点为空，说明当前节点为根节点
_root = _root->_right; // 将根节点替换为右子节点
else if (cur == parent->_left) // 如果当前节点是父节点的左子节点
parent->_left = cur->_right; // 将父节点的左子节点替换为当前节点的右子节点
else
parent->_right = cur->_right; // 将父节点的右子节点替换为当前节点的右子节点
delete cur; // 删除当前节点
}
else if (!cur->_right) // 如果当前节点没有右子节点
{
if (!parent) // 如果父节点为空，说明当前节点为根节点
_root = _root->_left; // 将根节点替换为左子节点
else if (cur == parent->_left) // 如果当前节点是父节点的左子节点
parent->_left = cur->_left; // 将父节点的左子节点替换为当前节点的左子节点
else
parent->_right = cur->_left; // 将父节点的右子节点替换为当前节点的左子节点
delete cur; // 删除当前节点
}
else // 如果当前节点有左右子节点
{
node* min_parent = cur; // 最小节点的父节点初始化为当前节点
node* min = cur->_right; // 最小节点指针初始化为当前节点的右子节点
while (min->_left) // 寻找右子树中的最小节点
{
min_parent = min;
min = min->_left;
}
cur->_key = min->_key; // 更新当前节点键值为最小节点键值
cur->_val = min->_val; // 更新当前节点值为最小节点值
if (min == min_parent->_left) // 将最小节点的父节点指向最小节点右子节点
min_parent->_left = min->_right;
else
min_parent->_right = min->_right;
delete min; // 删除最小节点
}
return true; // 返回删除成功
}
}
return false; // 未找到匹配键值，返回删除失败
}
// 中序遍历函数，输出键值对
void inorder()
{
_inorder(_root); // 调用内部中序遍历函数
cout << endl; // 换行
}
// 中序遍历辅助函数
void _inorder(node* root)
{
if (!root) // 如果当前节点为空，返回
return;
_inorder(root->_left); // 递归遍历左子树
cout << root->_key << "-" << root->_val << endl; // 输出当前节点键值对
_inorder(root->_right); // 递归遍历右子树
}
private:
node* _root = nullptr; // 根节点指针初始化为空
};

5. oj题