《数据结构、算法与应用 —— C++语言描述》学习笔记 — 二叉搜索树

• 一、二叉搜索树
• • 1、二叉搜索树特征
  • 2、索引二叉搜索树
• 二、抽象数据类型
• 三、二叉搜索树实现
• • 1、字典类接口修改
  • 2、接口
  • 3、查找接口
  • 4、删除
  • • （1）父节点扩展
    • （2）后继节点
    • （3）节点交换功能实现
    • （4）删除某个节点
    • （5）删除接口
  • 5、插入

一、二叉搜索树

前面我们学习了抽象数据类型 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)。