《数据结构、算法与应用 —— C++语言描述》学习笔记 — 二叉搜索树
一、二叉搜索树
前面我们学习了抽象数据类型 dictionary，使用散列实现的字典操作（查找、插入和删除）所需要的平均时间为
O
(
1
)
O(1)
O(1)。而这些操作在最坏情况下的时间与字典的元素个数呈线性关系。对于以下操作，散列并不具备哦较好的平均性能：
（1）升序输出字典元素
（2）升序找到第 k 个元素
（3）删除第 k 个元素。
为了执行操作（1）需要从表中收集数据，排序，然后输出。如果使用除数为 D 的链表，那么能用 O ( D + n ) O(D+n) O(D+n)时间收集元素，用 O ( n l o g n ) O(nlogn) O(nlogn)时间排序，用 O ( n ) O(n) O(n)时间输出，因此总时间为 O ( D + n l o g n ) O(D+nlogn) O(D+nlogn)。如果使用线性开放寻址，则收集元素所需时间为 O ( b ) O(b) O(b)，其中 b 是桶的个数。这时操作（1）的总时间为 O ( b + n l o g n ) O(b+nlogn) O(b+nlogn)。如果使用链表，操作（2）和（3）可以在 O ( D + n ) O(D+n) O(D+n)的时间内完成；如果使用现行开放寻址，它们可以在 O ( b ) O(b) O(b)时间内完成。为了使操作（2）和（3）具有这样的时间性能，必须采用一个线性时间算法来确定 n 元素集合中的第 k 个元素。
如果使用平衡搜索树，那么对字典的基本操作能够在 O ( l o g n ) O(logn) O(logn)的时间内完成，操作（1）能够在 O ( n ) O(n) O(n)的时间内完成。使用索引平衡搜索树，我们也能够在 O ( l o g n ) O(logn) O(logn)的时间内完成操作（2）和（3）。下面我们先学习它们的基础版本 — 二叉搜索树。
1、二叉搜索树特征
（1）每个元素都有一个关键字，并且任意两个元素的关键字都不同；因此，所有的关键字都是唯一的。
（2）在根节点的左子树中，元素的关键字（如果有的话）都小于根节点的关键字。
（3）在根节点的右子树中，元素的关键字（如果有的话）都大于根节点的关键字。
（4）根节点的左、右子树也都是二叉搜索树。
其中，如果去掉元素关键字不可重复的要求（（2）、（3）特征中需加入等于条件），这样的二叉树被称为有重复值的二叉搜索树。
2、索引二叉搜索树
索引二叉搜索树愿与普通二叉搜索树，只是在每个节点中添加一个 leftSize 域。这个域的值是该节点左子树的元素个数。
二、抽象数据类型
#pragma once
#include "../dictionary/dictionary.h"
template <typename Key, typename Value>
class AbstractBST : public dictionary<Key, Value>
{
public:
virtual void ascend() = 0;
};
三、二叉搜索树实现
1、字典类接口修改
字典类的查找接口需要修改参数类型为 const Key，因为在字典类型中 key 应该为常量：
virtual std::pair<Key, Value>* find(const Key& key) const = 0;
其跳表等实现修改这里不再列出。
2、接口
我们通过继承 linkedBinaryTree 的实现来实现 BST：
#pragma once
#include "AbstractBST.h"
#include "../binaryTree/linkedBinaryTree.h"
#include <iostream>
template <typename Key, typename Value>
class BinarySearchTree : public AbstractBST<const Key, Value>, public linkedBinaryTree<std::pair<const Key, Value>>
{
public:
using ValueType = std::pair<const Key, Value>;
using NodeType = binaryTreeNode<ValueType>;
virtual bool empty() const override;
virtual int size() const override;
virtual ValueType* find(const Key& key) const override;
virtual void erase(const Key& key) override;
virtual void insert(const ValueType& element) override;
virtual void ascend() override;
private:
NodeType* findNode(const Key& key) const;
std::pair<bool, NodeType*> findParentAndReplaceElement(const ValueType& element);
void insertElementWithParent(const ValueType& element, NodeType* parentNode);
void swapNodeWithSuccessor(NodeType*& node);
void removeNodeWithNoOrSingleChild(NodeType* node);
};
3、查找接口
查找的过程类似二分查找，根据关键字比较的结果决定去哪棵子树中进行查找：
template <typename Key, typename Value>
inline auto BinarySearchTree<Key, Value>::find(const Key& key) const -> BinarySearchTree<Key, Value>::ValueType*
{
auto node = findNode(key);
return node == nullptr ? nullptr : &node->element;
}
template<typename Key, typename Value>
inline auto BinarySearchTree<Key, Value>::findNode(const Key& key) const ->BinarySearchTree<Key, Value>::NodeType*
{
auto currentNode = this->root;
while (currentNode != NULL)
{
if (key == currentNode->element.first)
{
return currentNode;
}
else if (key < currentNode->element.first)
{
currentNode = currentNode->leftChild;
}
else
{
currentNode = currentNode->rightChild;
}
}
return nullptr;
}
此接口的时间复杂度为 O(h)。
4、删除
删除的情况包括三种：
① 要删除的是叶子节点：
直接删除即可
② 要删除的节点含有一棵子树：
将其子树直接与父节点相关联
③ 要删除的节点含有两棵子树：
将该节点与其后继节点交换位置。所谓后继节点是指中序遍历意义下排在该节点后面的节点。如图所示，6的后继节点就是7：
交换后 BST 的条件仍然满足，而且删除的情况退化成了①、②之一。
（1）父节点扩展
为了方便后续实现，我们为每个节点增加父节点属性：
template<typename T>
class binaryTreeNode
{
...
binaryTreeNode* parent;
binaryTreeNode(const T& element, binaryTreeNode* leftChild = nullptr, binaryTreeNode* rightChild = nullptr, binaryTreeNode* parent = nullptr) :
element(element)
{
this->leftChild = leftChild;
this->rightChild = rightChild;
this->parent = parent;
}
}
二叉树中的初始化也需要进行相应修改：
template<typename T>
inline void linkedBinaryTree<T>::makeTree(const T& element, linkedBinaryTree<T>& left, linkedBinaryTree<T>& right)
{
root = new binaryTreeNode<T>(element, left.root, right.root, nullptr);
if (left.root != nullptr)
{
left.root->parent = root;
}
if (right.root != nullptr)
{
right.root->parent = root;
}
...
}
（2）后继节点
template<typename T>
inline binaryTreeNode<T>* binaryTreeNode<T>::successor()
{
{
auto currentNode = this->rightChild;
auto parentNode = currentNode;
while (currentNode != nullptr)
{
parentNode = currentNode;
currentNode = currentNode->leftChild;
}
return parentNode;
}
}
（3）节点交换功能实现
节点交换不能直接使用 swap，因为 key 类型为 const：
template<typename Key, typename Value>
inline void BinarySearchTree<Key, Value>::swapNodeWithSuccessor(NodeType*& node)
{
if (node->leftChild != nullptr && node->rightChild != nullptr)
{
auto successor = node->successor();
auto parent = node->parent;
auto swapNode = new binaryTreeNode(successor->element, node->leftChild, node->rightChild, parent);
if (parent != nullptr)
{
parent->leftChild == node ? parent->leftChild = swapNode : parent->rightChild = swapNode;
}
node->leftChild->parent = swapNode;
node->rightChild->parent = swapNode;
node = successor;
}
}
（4）删除某个节点
template<typename Key, typename Value>
inline void BinarySearchTree<Key, Value>::removeNodeWithNoOrSingleChild(NodeType* node)
{
NodeType* childNode = nullptr;
if (node->leftChild != nullptr)
{
childNode = node->leftChild;
}
else if (node->rightChild != nullptr)
{
childNode = node->rightChild;
}
if (childNode != nullptr)
{
childNode->parent = node->parent;
}
if (node->parent != nullptr)
{
node->parent->leftChild == node ? node->parent->leftChild = childNode : node->parent->rightChild = childNode;
}
else
{
this->root = this->root->leftChild != nullptr ? this->root->leftChild : this->root->rightChild;
}
}
（5）删除接口
首先我们要确定给定的关键字是否存在：
template <typename Key, typename Value>
inline void BinarySearchTree<Key, Value>::erase(const Key& key)
{
auto deleteNode = findNode(key);
if (deleteNode == nullptr)
{
return;
}
swapNodeWithSuccessor(deleteNode);
removeNodeWithNoOrSingleChild(deleteNode);
delete deleteNode;
this->treeSize--;
}
此接口的时间复杂度为 O(h)。
5、插入
插入一个节点首先要确定该节点所对应的关键字是否已存在。如果关键字已经存在，我们直接替换即可：
/*
* @return bool - 关键字是否已存在
* parent - 待插入节点的父节点位置
*/
template<typename Key, typename Value>
inline auto BinarySearchTree<Key, Value>::findParentAndReplaceElement(const ValueType& element) -> std::pair<bool, NodeType*>
{
auto currentNode = this->root;
decltype(currentNode) parentNode = nullptr;
while (currentNode != NULL)
{
parentNode = currentNode;
if (element.first == currentNode->element.first)
{
currentNode->element.second = element.second;
return make_pair(true, (NodeType*)nullptr);
}
else if (element.first < currentNode->element.first)
{
currentNode = currentNode->leftChild;
}
else
{
currentNode = currentNode->rightChild;
}
}
return make_pair(false, parentNode);
}
如果关键字不存在，我们需要根据其与父节点关键字的关系决定放入哪棵子树。同时，需要注意根节点为空的情况：
template<typename Key, typename Value>
inline void BinarySearchTree<Key, Value>::insertElementWithParent(const ValueType& element, NodeType* parentNode)
{
auto newNode = new NodeType(element, nullptr, nullptr, parentNode);
if (parentNode == nullptr)
{
this->root = newNode;
}
else
{
if (element.first < parentNode->element.first)
{
parentNode->leftChild = newNode;
}
else
{
parentNode->rightChild = newNode;
}
}
}
上述两个函数的调用如下：
template <typename Key, typename Value>
inline void BinarySearchTree<Key, Value>::insert(const ValueType& element)
{
auto [findCurrent, parentNode] = findParentAndReplaceElement(element);
insertElementWithParent(element, parentNode);
this->treeSize++;
}
此接口的时间复杂度为 O(h)。