突破编程_C++_查找算法（红黑树查找）

1 算法题：使用红黑树的数据结构在无序数组中查找指定元素

1.1 题目含义

这个题目要求实现一个红黑树（Red-Black Tree），这是一种自平衡的二叉查找树，它通过颜色和一系列的调整规则来确保树的大致平衡，从而实现对数级别的查找、插入和删除操作。题目要求你在实现红黑树的基础上，使用它来在一个无序数组中查找指定的元素，并返回该元素在原始数组中的位置（索引）。

红黑树的性质

红黑树满足以下五个性质：

每个节点要么是红色，要么是黑色。
根节点是黑色。
所有叶子节点（NIL 或空节点）是黑色。
如果一个节点是红色的，则它的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

1.2 示例

示例 1:
输入：

nums = [4, 2, 7, 10, 1, 6, 8]
target = 7

输出：

说明：

首先，根据数组 [4, 2, 7, 10, 1, 6, 8] 构建一个 B 树。然后，在树中查找元素 7。找到后，返回元素 7 在原始数组中的位置，即索引 2。

示例 2:
输入：

nums = [1, 3, 5, 7]
target = 9

输出：

-1

说明：

根据数组 [1, 3, 5, 7] 构建 B 树后，在树中查找元素 9。由于元素 9 不存在于树中，所以返回 -1，表示未找到目标值。

示例 3:
输入：

nums = []
target = 0

输出：

-1

说明：

nums 为空，0 不存在于 nums 中，返回 -1。

2 解题思路

这一题目涉及两个主要步骤：红黑树的构建和红黑树中的元素查找，以及如何在红黑树节点和原始数组元素之间建立并维护索引映射关系。

第一步：定义红黑树节点结构

首先，需要定义一个红黑树的节点结构。每个节点需要包含键（即元素值），颜色（红色或黑色），以及指向父节点、左孩子和右孩子的指针。这里可以使用结构体或类来表示这个节点。

第二步：实现红黑树的基本操作

在插入或删除节点时，可能需要执行一些基本操作来保持红黑树的性质。这些操作包括：

旋转：左旋和右旋。旋转操作是为了在插入或删除节点后重新平衡树结构。
颜色调整：改变节点的颜色。当插入或删除节点导致红黑树的性质被破坏时，可以通过改变节点的颜色来修复。

这些操作是构建红黑树的基础，必须正确实现。

第三步：实现红黑树的插入操作

插入操作是构建红黑树索引的关键步骤。需要将每个数组元素及其位置作为键值对插入到红黑树中。插入过程中，遵循二叉查找树的规则，并在插入后检查红黑树的性质是否被破坏。如果破坏了，则使用第二步中定义的基本操作来修复。

第四步：构建红黑树索引

遍历无序数组，对于数组中的每个元素，执行以下步骤：

将元素及其位置作为键值对插入到红黑树中。
检查红黑树的性质，如果需要，执行旋转和颜色调整。
完成遍历后，就得到了一个包含数组元素及其位置信息的红黑树索引。

第五步：实现红黑树的查找操作

查找操作是从根节点开始，根据二叉查找树的规则向下遍历红黑树，直到找到要查找的元素或者遍历到叶子节点。如果找到了元素，返回该元素在红黑树中对应的节点所存储的位置信息。

第六步：处理查找结果

在查找操作中，需要处理几种情况：

如果找到了元素，返回该元素在红黑树中对应的节点所存储的位置信息，即该元素在原始数组中的位置。
如果元素在数组中不存在，返回一个特殊值（如 -1）来表示未找到。
如果元素在数组中存在多个，根据题目要求，只返回元素第一次出现的位置。

第七步：调用查找操作并输出结果

最后，调用红黑树的查找操作，传入要查找的元素，并根据第六步中的规则处理查找结果。然后，将结果输出，完成整个算法题的要求。

3 算法实现代码

如下为算法实现代码：

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

enum Color { RED, BLACK };

struct Node
{
	int data;
	int position;
	bool color;
	Node *left, *right, *parent;

	Node(int data, int position)
	{
		this->data = data;
		this->position = position;
		left = right = parent = NULL;
		this->color = RED;
	}
};

class RedBlackTree
{
private:
	Node *root;
protected:
	void rotateLeft(Node *&, Node *&);
	void rotateRight(Node *&, Node *&);
	void fixViolation(Node *&, Node *&);
public:
	RedBlackTree() { root = NULL; }
	void insert(const int &data, const int &position);
	void inorder();
	void levelOrder();

	int findPosition(int value);
};

void inorderHelper(Node *root)
{
	if (root == NULL)
		return;

	inorderHelper(root->left);
	cout << root->data << "  ";
	inorderHelper(root->right);
}

Node* BSTInsert(Node* root, Node *pt)
{
	if (root == NULL)
		return pt;

	if (pt->data < root->data)
	{
		root->left = BSTInsert(root->left, pt);
		root->left->parent = root;
	}
	else if (pt->data > root->data)
	{
		root->right = BSTInsert(root->right, pt);
		root->right->parent = root;
	}

	return root;
}

void levelOrderHelper(Node *root)
{
	if (root == NULL)
		return;

	static deque<Node *> q;
	q.push_back(root);

	while (!q.empty())
	{
		Node *temp = q.front();
		cout << temp->data << "  ";
		q.pop_front();

		if (temp->left != NULL)
			q.push_back(temp->left);

		if (temp->right != NULL)
			q.push_back(temp->right);
	}
}

void RedBlackTree::rotateLeft(Node *&root, Node *&pt)
{
	Node *pt_right = pt->right;

	pt->right = pt_right->left;

	if (pt->right != NULL)
		pt->right->parent = pt;

	pt_right->parent = pt->parent;

	if (pt->parent == NULL)
		root = pt_right;

	else if (pt == pt->parent->left)
		pt->parent->left = pt_right;

	else
		pt->parent->right = pt_right;

	pt_right->left = pt;
	pt->parent = pt_right;
}

void RedBlackTree::rotateRight(Node *&root, Node *&pt)
{
	Node *pt_left = pt->left;

	pt->left = pt_left->right;

	if (pt->left != NULL)
		pt->left->parent = pt;

	pt_left->parent = pt->parent;

	if (pt->parent == NULL)
		root = pt_left;

	else if (pt == pt->parent->left)
		pt->parent->left = pt_left;

	else
		pt->parent->right = pt_left;

	pt_left->right = pt;
	pt->parent = pt_left;
}

void RedBlackTree::fixViolation(Node *&root, Node *&pt)
{
	Node *parent_pt = NULL;
	Node *grand_parent_pt = NULL;

	while ((pt != root) && (pt->color != BLACK) && pt->parent &&
		(pt->parent->color == RED))
	{

		parent_pt = pt->parent;
		grand_parent_pt = pt->parent->parent;

		if (parent_pt == grand_parent_pt->left)
		{

			Node *uncle_pt = grand_parent_pt->right;

			if (uncle_pt != NULL && uncle_pt->color == RED)
			{
				grand_parent_pt->color = RED;
				parent_pt->color = BLACK;
				uncle_pt->color = BLACK;
				pt = grand_parent_pt;
			}

			else
			{
				if (pt == parent_pt->right)
				{
					rotateLeft(root, parent_pt);
					pt = parent_pt;
					parent_pt = pt->parent;
				}

				rotateRight(root, grand_parent_pt);
				swap(parent_pt->color, grand_parent_pt->color);
				pt = parent_pt;
			}
		}

		else
		{
			Node *uncle_pt = grand_parent_pt->left;

			if ((uncle_pt != NULL) && (uncle_pt->color == RED))
			{
				grand_parent_pt->color = RED;
				parent_pt->color = BLACK;
				uncle_pt->color = BLACK;
				pt = grand_parent_pt;
			}
			else
			{
				if (pt == parent_pt->left)
				{
					rotateRight(root, parent_pt);
					pt = parent_pt;
					parent_pt = pt->parent;
				}

				rotateLeft(root, grand_parent_pt);
				swap(parent_pt->color, grand_parent_pt->color);
				pt = parent_pt;
			}
		}
	}

	root->color = BLACK;
}

void RedBlackTree::insert(const int &data, const int &position)
{
	Node *pt = new Node(data, position);

	root = BSTInsert(root, pt);

	fixViolation(root, pt);
}

void RedBlackTree::inorder() { inorderHelper(root); }
void RedBlackTree::levelOrder() { levelOrderHelper(root); }

int RedBlackTree::findPosition(int value) {
	Node* current = root;
	while (current != NULL) {
		if (value < current->data) {
			current = current->left;
		}
		else if (value > current->data) {
			current = current->right;
		}
		else { // value is equal to current node data, position found!
			return current->position;
		}
	}
	// value not found in the tree, return -1 or any invalid position.
	return -1;
}

class Solution
{
public:
	int redBlackTreeSearch(std::vector<int>& nums, int target) {
		RedBlackTree tree;
		for (size_t i = 0; i < nums.size(); i++)
		{
			tree.insert(nums[i], i);
		}
		int position = tree.findPosition(target);
		return position;
	}
};

这段代码实现了一个红黑树，并使用它在有序数组中查找指定数值的位置。

首先定义了一个节点类 Node，包含数据 data、数据原始位置 position、颜色 color、左右子节点 left 和 right 以及父节点parent。其中，颜色用枚举类型 Color 表示，包括 RED 和 BLACK 两种颜色。

接着定义了一个红黑树类 RedBlackTree，包含了插入节点、中序遍历、层序遍历等方法。其中，插入节点的方法 BSTInsert 是二叉搜索树的插入方法，而 fixViolation 方法用于修复插入节点后可能破坏红黑树性质的操作。

调用上面的算法，并得到输出：

int main()
{
	Solution s;
	std::vector<int> nums= { 15, 10, 20, 8, 12, 16, 25 }; 
	
	int target = 16;
	int position = s.redBlackTreeSearch(nums, target);
	if (position != -1) { 
		cout << "The position of " << target << " in the array is: " << position << endl;
	}
	else { 
		cout << "Value not found in the tree." << endl;
	}
	return 0;
}

上面代码的输出为：

The position of 16 in the array is: 5

4 测试用例

以下是针对上面算法的测试用例，基本覆盖了各种情况：

（1）基础测试用例
输入：数组 [3, 5, -1, 0, 9, 12]，目标值 9
输出：4
说明：目标值 9 存在于数组中，位于索引 4 的位置。

（2）目标值不存在于数组中
输入：数组 [3, 5, -1, 0, 9, 12]，目标值 2
输出：-1
说明：目标值 2 不存在于数组中。

（3）目标值位于数组开头
输入：数组 [-1, 0, 3, 9, 5, 12]，目标值 -1
输出：0
说明：目标值 -1 位于数组的开头，即索引 0 的位置。

（4）目标值位于数组末尾
输入：数组 [9, -1, 3, 0, 5, 12]，目标值 12
输出：5
说明：目标值 12 位于数组的末尾，即索引 5 的位置。

（5）目标值位于数组中间
输入：数组 [0, -1, 3, 9, 5, 12]，目标值 3
输出：2
说明：目标值 3 位于数组的中间位置，即索引 2 的位置。

（6）空数组
输入：数组 []，目标值 9
输出：-1
说明：空数组不包含任何元素，因此无法找到目标值。

（7）数组只有一个元素
输入：数组 [9]，目标值 9
输出：0
说明：数组只有一个元素，且该元素就是目标值，位于索引 0 的位置。

（8）数组中存在多个相同的目标值
输入：数组 [1, 2, 3, 3, 4, 5]，目标值 3
输出：2 或 3
说明：数组中存在多个目标值 3，返回任意一个目标值的索引都是正确的。这里可以返回 2 或 3。

breakthrough_01