目录

搜索树

搜索树，通常特指二叉搜索树，是一种基于二叉树的、具有特定排序性质的数据结构。

它的核心特性遵循 “左小右大” 原则：

  • 任意节点的左子树上所有节点的值，都小于该节点本身的值。
  • 任意节点的右子树上所有节点的值，都大于该节点本身的值。
  • 默认情况下，左、右子树也都是二叉搜索树。
  • （通常）不存在键值相等的节点。

核心操作与性能

由于其有序性，二叉搜索树支持以下高效操作：

  • 查找：从根节点开始，比目标值小则进入左子树，大则进入右子树，直到找到或到达空节点。平均时间复杂度为 O(log n)。
  • 插入：遵循查找路径，找到合适的空位置插入新节点，始终保持"左小右大"的规则。
  • 删除：情况稍复杂，需处理待删除节点有0个、1个或2个子节点的情况，但核心仍是维护树的有序性。

局限性：性能退化问题

二叉搜索树的性能严重依赖于树的形状。

  • 理想情况：树是完全平衡或接近完全平衡的，此时树高为 log₂n，所有操作效率都很高。
  • 最坏情况：如果插入的数据是有序的（如1, 2, 3, 4, 5…），树会退化成一条链表。
    • 此时，树高为 n。
    • 查找、插入、删除的时间复杂度都退化为 O(n)，失去了其高效的优势。

理想情况和最坏情况如下图所示：

在这里插入图片描述

key模型和key-value模型

Key模型是纯键存储结构，每个节点只包含一个键值(Key)，不存储额外的数据值(Value)。它主要用于判断元素是否存在、数据去重和集合操作，关注的是"存在性"问题。STL中的set就是典型的Key模型实现，适用于黑白名单过滤、唯一性检查等场景，结构简单且内存占用较小。

Key-Value模型是键值对存储结构，每个节点包含键(Key)和对应的值(Value)。Key用于排序和快速查找，Value存储实际关联的数据。它主要用于建立映射关系，如字典、缓存系统和统计计数等。STL中的map和set都是Key-Value模型的典型实现，能够表达更复杂的对应关系，应用范围更加广泛。

搜索树实现

我们这里以key-value模型举例,key模型只需去除value即可

template<class K, class V>
struct BSTreeNode {
    BSTreeNode<K,V>* _left;    // 左子节点指针
    BSTreeNode<K,V>* _right;   // 右子节点指针
    K _key;                    // 键值，用于排序和比较
    V _value;                  // 存储的数据值
    

    // 构造函数，初始化键值对和子节点指针
    BSTreeNode(const K& key = K(), const V& value = V())
        :_key(key), _value(value), _left(nullptr), _right(nullptr) {}

};

使用key和value进行节点构造,然后进行构造搜索树

插入操作 (Insert)

  1. 从根节点开始比较，小于当前节点往左，大于往右
  2. 找到空位置后插入新节点

查找操作 (Find)

​ 比key大往右走,比key小往左走,相等则找到了,返回,走到空则查找失败,树中没有该节点.

删除操作 (Erase)

三种情况处理：

  1. 删除叶子节点：直接删除，父节点对应指针置空
  2. 删除只有一个子节点的节点：用子节点替代被删除节点
  3. 删除有两个子节点的节点：
    • 找到左子树的最大节点或右子树的最小节点
    • 交换键值对
    • 转换为删除叶子节点或单子节点的情况

实现代码:

#pragma once

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<cassert>
using namespace std;

// 二叉搜索树节点模板类
template<class K, class V>
struct BSTreeNode {
    BSTreeNode<K,V>* _left;    // 左子节点指针
    BSTreeNode<K,V>* _right;   // 右子节点指针
    K _key;                    // 键值，用于排序和比较
    V _value;                  // 存储的数据值
    
    // 构造函数，初始化键值对和子节点指针
    BSTreeNode(const K& key = K(), const V& value = V())
        :_key(key), _value(value), _left(nullptr), _right(nullptr) {}
};

// 二叉搜索树模板类
template<class K, class V>
class BSTree {
    typedef BSTreeNode<K, V> Node;  // 节点类型别名

public:
    // 默认构造函数
    BSTree():_root(nullptr){}
    
    // 拷贝构造函数 - 深拷贝
    BSTree(const BSTree& tree)
    {
        _root = Copy(tree._root);
    }

    // 赋值运算符重载
    BSTree& operator=(const BSTree& tree)
    {
        return BSTree(tree);
    }
    
    // 析构函数 - 释放所有节点内存
    ~BSTree()
    {
        Destroy(_root);
        _root = nullptr;
    }
    
    // 插入键值对
    bool Insert(const K& key, const V& value){
        // 创建新节点
        Node* newNode = new Node(key, value);
        if (_root == nullptr) {
            // 空树情况，新节点作为根节点
            _root = newNode;
        }
        else {
            Node* parent = _root;  // 记录父节点
            Node* cur = _root;     // 当前遍历节点

            // 寻找插入位置
            while (cur) {
                parent = cur;
                if (key < cur->_key) 
                    cur = cur->_left;      // 往左子树找
                else if (key > cur->_key) 
                    cur = cur->_right;     // 往右子树找
                else 
                    return false;          // 键值已存在，插入失败
            }

            // 在父节点的正确位置插入新节点
            if (key < parent->_key) {
                parent->_left = newNode;
            }
            else {
                parent->_right = newNode;
            }
        }
        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)
    {
        if (_root == nullptr) return false;  // 空树情况
        
        Node* parent = _root;  // 父节点指针
        Node* cur = _root;     // 当前节点指针

        // 寻找要删除的节点
        while (cur && cur->_key != key) {
            parent = cur;
            if (key < cur->_key) 
                cur = cur->_left;
            else  
                cur = cur->_right;
        }
        
        if (cur == nullptr) return false;  // 未找到要删除的节点

        // 情况1：删除的节点只有左子树或无子树
        if (cur->_right == nullptr){
            if (cur == parent->_left){
                parent->_left = cur->_left;  // 父节点左指针指向cur的左子树
            }
            else if(cur == parent->_right){
                parent->_right = cur->_left; // 父节点右指针指向cur的左子树
            }
            else if (cur == _root)  // 删除的是根节点
            {
                _root = cur->_left;  // 根节点指向左子树
            }
            else
            {
                assert(false);  // 不应该执行到这里
            }
            delete cur;  // 释放节点内存
        }
        // 情况2：删除的节点只有右子树或无子树
        else if (cur->_left == nullptr){
            if (cur == parent->_left){
                parent->_left = cur->_right;  // 父节点左指针指向cur的右子树
            }
            else if( cur == parent->_right){
                parent->_right = cur->_right; // 父节点右指针指向cur的右子树
            }
            else if (cur == _root)  // 删除的是根节点
            {
                _root = cur->_right;  // 根节点指向右子树
            }
            else
            {
                assert(false);  // 不应该执行到这里
            }
            
            delete cur;  // 释放节点内存
        }
        // 情况3：删除的节点有两个子树
        else {
            // 寻找左子树的最大节点（替代节点）
            Node* leftMaxParent = cur;       // 替代节点的父节点
            Node* leftMax = cur->_left;      // 替代节点
            while (leftMax->_right) {
                leftMaxParent = leftMax;
                leftMax = leftMax->_right;
            }
            
            // 交换当前节点和替代节点的键值对
            swap(cur->_key, leftMax->_key);
            swap(cur->_value, leftMax->_value);

            // 删除替代节点（现在替代节点最多只有一个左子树）
            if (leftMax == leftMaxParent->_left) {
                leftMaxParent->_left = leftMax->_left;
            }
            else {
                leftMaxParent->_right = leftMax->_left;
            }

            delete leftMax;  // 释放替代节点内存
        }

        cout << ":" << key << endl;  // 输出删除的键值（调试信息）
        return true;  // 删除成功
    }

    // 中序遍历 - 按键值升序输出
    void InOrder()
    {
        _InOrder(_root);
    }
    
    // 判断树是否为空
    bool Empty()
    {
        return _root == nullptr;
    }
    
private:
    // 递归销毁整棵树
    void Destroy(Node* root)
    {
        if (root == nullptr) return;

        Destroy(root->_left);   // 递归销毁左子树
        Destroy(root->_right);  // 递归销毁右子树

        delete root;            // 释放当前节点
        root = nullptr;
    }
    
    // 递归拷贝整棵树
    Node* Copy(Node* root)
    {
        if (root == nullptr) return root;

        // 创建新节点
        Node* newnode = new Node(root->_key, root->_value);

        // 递归拷贝左右子树
        newnode->_left = Copy(root->_left);
        newnode->_right = Copy(root->_right);

        return newnode;
    }
    
    // 递归中序遍历
    void _InOrder(Node* root)
    {
        if (root == nullptr) return;

        _InOrder(root->_left);  // 遍历左子树

        // 输出当前节点的键值对
        cout << root->_key << ":" << root->_value << endl;

        _InOrder(root->_right); // 遍历右子树
    }
    
    Node* _root = nullptr;  // 根节点指针
};

AVL树

什么是AVL树

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。

使用平衡因子并不是必须的，而是其中一种实现方式。平衡因子 = 右子树高度 - 左子树高度

如果它有n个结点，其高度可保持在 O(log_2 n)，搜索时间复杂度O(log_2 n)。

AVL树的实现

AVL树的大部分操作与搜索树相同，但是需要维护自身的平衡，因此在插入与删除的时候需要进行平衡调整。删除操作较为复杂，本文章暂未讲解，但是与插入操作相似，也是先按照搜索树删除，在更新平衡因子，如果不平衡在进行旋转。

插入操作详解

AVL树在插入新节点后，为了维持其平衡性（即任何节点的左右子树高度差绝对值不超过1），需要严格遵守以下核心3步：

1.按照二叉搜索树规则插入
  • 从根节点开始，将新节点的键值与当前节点比较。
  • 遵循“左小右大”的原则：

    如果新节点键值 小于 当前节点键值，则递归进入左子树插入。

    如果新节点键值 大于 当前节点键值，则递归进入右子树插入。

  • 直到找到一个空位置，将新节点插入。
2.更新父节点的平衡因子

  • 新节点插入后，其父节点的平衡因子必须更新。

  • 更新规则如下：

    如果新节点是作为左孩子插入的，则父节点的平衡因子 -1。

    如果新节点是作为右孩子插入的，则父节点的平衡因子 +1。

3.向上回溯并检查平衡，直至根节点
  • 从插入节点的父节点开始，自底向上地回溯到根节点，检查并更新沿途祖先节点的平衡因子。
  • 对于每一个被访问的祖先节点（我们称之为当前节点），根据其更新后的平衡因子，采取以下行动：
当前节点的新平衡因子 含义 需要执行的操作
0 插入后，该节点左右子树高度变得相等。
这意味着插入操作填补了原来较矮的一边，使得以该节点为根的子树总高度没有发生变化。		 停止回溯。
因为子树高度未变，不会影响更上层祖先的平衡。
-1 或 1 插入后，该节点变得一边稍高。
这意味着以该节点为根的子树总高度增加了。		 1. 继续向上回溯，去更新其父节点（即爷爷节点）的平衡因子。
2. 更新爷爷节点平衡因子的规则与第二步相同：
- 如果当前节点是爷爷节点的左孩子，则爷爷节点平衡因子 -1。
- 如果当前节点是爷爷节点的右孩子，则爷爷节点平衡因子 +1。
-2 或 2 该节点严重不平衡，违反了AVL树的性质。 1. 立即停止回溯。
2. 对该节点进行旋转操作，以恢复平衡。
- 根据不平衡的具体情况（LL, LR, RR, RL），选择对应的旋转策略（单旋或双旋）。
3. 旋转后，以该节点为根的子树高度恢复到了插入前的状态，因此不会影响更上层的平衡，回溯过程自然结束。

示意流程图

更新中平衡因子不可能出现除了0，±1， ±2之外的情况，因为在插入之前已经是AVL树，符合性质 高度差不超过1（平衡因子为0，±1），因此在插入一个节点后最多改变1，最坏就是±2，然后旋转后变成平衡的

3.1右单旋

当某一个节点的平衡因子为-2，并且其左孩子的平衡因子为-1，那么就需要进行右单旋操作。

在这里插入图片描述

上图中h为高度，a,b,c均为高度为h的AVL子树。但是，a子树一定是平衡的，因为要想更新平衡因子至X节点，那么一定得从插入新节点的父亲节点开始一路向上一直更新，如果a子树不平衡，要么在插入之后变平衡，要么进行旋转后恢复平衡，不会一直向上更新，只有平衡树插入才会导致一直向上更新。

由于 a < Y < b < X < c (Y的值大于a子树的最大节点值，Y的值小于b节点的最小值，其余节点和子树比较也类似)，那么我们就可以根据平衡树和搜索树规则将Y当做根节点，a子树为左孩子，X节点为右孩子，b，c子树分别为X的左右孩子。这就是一次右单旋情况。

3.2左单旋

当某一个节点的平衡因子为2，并且其右孩子的平衡因子为1，那么就需要进行左单旋操作。

在这里插入图片描述

左单旋几乎是与右单旋是镜像的操作，如果能理解右单旋，左单旋很容易就可以理解。

3.3左右双旋

当某一个节点的平衡因子为-2，并且其左孩子的平衡因子为1，那么就需要进行左右双旋操作。

在这里插入图片描述

如上图所示，插入节点在b，c子树的时候，就需要进行左右双旋，（先左单旋在右单旋），

3.3右左双旋

当某一个节点的平衡因子为2，并且其左孩子的平衡因子为-1，那么就需要进行右左双旋操作。

在这里插入图片描述

AVL树模拟实现代码

#pragma once

#include<iostream>
#include<cassert>
using namespace std;

template<class K, class V>
struct AVLTreeNode {
	AVLTreeNode<K, V>* _parent;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;

	K _key;
	V _value;
	int _bf;

	AVLTreeNode(const K& key = K(), const V& value = V())
		:_key(key), _value(value), 
		_left(nullptr), _right(nullptr),
		_parent(nullptr),_bf(0) {
	}

};

template<class K, class V>
class AVLTree {
	typedef AVLTreeNode<K, V> Node;

public:

	AVLTree() :_root(nullptr) {}
	AVLTree(const AVLTree& tree)
	{
		_root = Copy(tree._root);
	}

	AVLTree& operator=(const AVLTree& tree)
	{
		return AVLTree(tree);
	}
	~AVLTree()
	{
		Destroy(_root);
		_root = nullptr;
	}

	bool Insert(const K& key, const V& value) {

		Node* newNode = new Node(key, value);
		if (_root == nullptr) {
			_root = newNode;
		}
		else {
			Node* parent = _root;
			Node* cur = _root;

			while (cur) {
				parent = cur;
				if (key < cur->_key) cur = cur->_left;
				else if (key > cur->_key) cur = cur->_right;
				else return false;
			}

			if (key < parent->_key) {
				parent->_left = newNode;
			}
			else {
				parent->_right = newNode;
			}

			newNode->_parent = parent;
			cur = newNode;
			while ( parent != nullptr)
			{
				if (cur == parent->_left) 
				{
					parent->_bf--;
					if (abs(parent->_bf) != 1)
					{
						if (parent->_bf == -2 && cur->_bf == 1)
						{
							//左右双旋
							RotateLR(parent);
						}
						else if (parent->_bf == -2 && cur->_bf == -1)
						{
							//右单旋
							RotateR(parent);
							
						}
						break;
					}
				}
				else 
				{
					parent->_bf++;

					if (abs(parent->_bf)!= 1)
					{
						if (parent->_bf == 2 && cur->_bf == 1)
						{
							//左单旋
							RotateL(parent);
						}
						else if (parent->_bf == 2 && cur->_bf == -1)
						{
							//右左双旋
							RotateRL(parent);
						}
						break;
					}
				}

				cur = parent;
				parent = parent->_parent;
								
			}


		}
	//	cout << key << ":" << IsBalance() << endl;
	//	InOrder();
	//	cout << endl;
		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;
	}

	void InOrder()
	{
		_InOrder(_root);
	}
	bool Empty()
	{
		return _root == nullptr;
	}

	bool IsBalance()
	{
		int deep = 0;
		return _IsBalance(_root, &deep);
	}
private:

	void Destroy(Node* root)
	{
		if (root == nullptr) return;

		Destroy(root->_left);
		Destroy(root->_right);

		delete root;
		root = nullptr;
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr) return root;

		Node* newnode = new Node(root->_key, root->_value);

		newnode->_left = Copy(root->_left);
		newnode->_right = Copy(root->_right);

		return newnode;
	}

	bool _IsBalance(Node* root, int* deep)
	{
		if (root == nullptr) return true;

		if (abs(root->_bf) > 1)
		{
			cout << "key:" << root->_key << "bf error: " << root->_bf << endl;
			return false;
		}

		int ldeep = 0;
		int rdeep = 0;

		if (!(_IsBalance(root->_left, &ldeep) && _IsBalance(root->_right, &rdeep))) { return false; }
		 if (abs(ldeep - rdeep) > 1)
		 {
			 cout << "no balance: key->" << root->_key << endl;
			 return false;
		 }
		 *deep = max(ldeep, rdeep)+1;
		 return true;
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr) return;

		_InOrder(root->_left);

		//cout << root->_key << ":" << root->_value << endl;
		cout << root->_key << " ";

		_InOrder(root->_right);

	}


	void RotateR(Node* cur)
	{
		Node* parentOfcur = cur->_parent;
		Node* left = cur->_left;


		cur->_left = left->_right;
		if(left->_right)
		left->_right->_parent = cur;
		left->_right = cur;
		cur->_parent = left;
		if (parentOfcur == nullptr)
		{
			_root = left;
			left->_parent = nullptr;
		}
		else
		{

			if (parentOfcur->_left == cur)
			{
				parentOfcur->_left = left;
				left->_parent = parentOfcur;
			}
			else
			{
				parentOfcur->_right = left;
				left->_parent = parentOfcur;
			}
		}

		left->_bf = 0;
		cur->_bf = 0;

	}

	void RotateL(Node* cur)
	{
		Node* parentOfcur = cur->_parent;
		Node* right = cur->_right;

		cur->_right = right->_left;
		if(right->_left)
		right->_left->_parent = cur;
		right->_left = cur;
		cur->_parent = right;


		if (parentOfcur == nullptr)
		{
			_root = right;
			right->_parent = nullptr;
		}
		else
		{
			if (parentOfcur->_right == cur)
			{
				parentOfcur->_right = right;
				right->_parent = parentOfcur;
			}
			else
			{
				parentOfcur->_left = right;
				right->_parent = parentOfcur;
			}
		}

		right->_bf = 0;
		cur->_bf = 0;
	}

	void RotateRL(Node* cur)
	{

		Node* parentOfcur = cur->_parent;

		Node* right = cur->_right;
		Node* leftOfright = right->_left;

		RotateR(right);
		RotateL(cur);

		if (leftOfright->_bf == -1)
		{
			cur->_bf = 0;
			right->_bf = 1;
			leftOfright->_bf = 0;
		}
		else if (leftOfright->_bf == 1)
		{
			cur->_bf = -1;
			right->_bf = 0;
			leftOfright->_bf = 0;

		}
		else
		{
			cur->_bf = right->_bf = leftOfright->_bf = 0;
		}

	}

	void RotateLR(Node* cur)
	{
		Node* parentOfcur = cur->_parent;

		Node* left = cur->_left;
		Node* rightOfleft = left->_right;

		RotateL(left);
		RotateR(cur);

		if (rightOfleft->_bf == -1)
		{
			cur->_bf = 1;
			left->_bf = 0;
			rightOfleft->_bf = 0;
		}
		else if (rightOfleft->_bf == 1)
		{
			cur->_bf = 0;
			left->_bf = -1;
			rightOfleft->_bf = 0;

		}
		else
		{
			cur->_bf = left->_bf = rightOfleft->_bf = 0;

		}

	}
	Node* _root = nullptr;
};

红黑树

红黑树也是自平衡的二叉搜索树，通过引入规则和颜色来控制平衡，同AVL树一样都是搜索树的增强版，不同的是，AVL树是严格平衡，而红黑树则相对宽松一点，最长路径不大于最短路径的二倍，因为实现起来较AVL树相对容易，因此也是map和set最常用的底层容器。本文也同样只讲解了红黑树的插入操作，删除操作较为复杂，并未讲解，其他操作与搜索树相同。

红黑树的性质

  1. 每个节点要么是红色，要么是黑色
  2. 根节点是黑色的
  3. 每个叶子节点（NIL节点）都是黑色的
  4. 不能有两个相邻的红色节点（即红色节点的父节点和子节点不能是红色的）
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

实现平衡的原因

第二条性质为根节点必须为黑，是因为根节点作为所有路径的公共祖先，根节点的颜色直接影响整个树的平衡状态。如果根节点为红色，在某些情况下可能导致性质冲突，特别是在插入操作时可能引发不必要的重新平衡。因此强制根节点为黑色可以更好的维护性质5。

第三条性质所说的叶子节点特指空节点（NIL节点），而是存放实际数据的叶子节点中的左右孩子指针（代码中为叶子节点里实际存放的空指针，在数据结构上抽象为NIL节点）。将所有实际的空指针统一视为黑色的NIL节点，极大地简化了路径长度的计算和平衡条件的判断。这种设计使得算法无需特别处理各种边界情况，每个节点都可以被视为拥有完整的左右子树（即使是NIL），从而保证了从任一节点到所有叶子节点的路径定义明确，这也是为了更好的维护性质5。

而通过第4和5条性质，就可以控制红黑树为平衡树：

在红黑树中，如果存在全黑的路径，那一定是最短的，如果存在一黑一红相间的路径，那一定是最长的（通过性质4不能有连续红节点约束），在通过性质5，就使得最短路径和最长路径中含有相等数量的黑色节点，则该最长路径是最短路径的二倍，但在实际的红黑树总可能并没有同时存在这两条路径，但是其他的路径长度一定是在最短和最长的区间内，因此在一颗实际存在的红黑树中，最长的路径一定不会大于最短的路径的2倍。

红黑树插入操作

红黑树插入需要维护自身性质,需要通过调整颜色,旋转来维护性质,从而达到平衡的目的.

插入规则可以归结为以下3步.

1.按照二叉搜索树规则插入

  • 从根节点开始，将新节点的键值与当前节点比较。

  • 遵循“左小右大”的原则：

    如果新节点键值 小于 当前节点键值，则递归进入左子树插入。

    如果新节点键值 大于 当前节点键值，则递归进入右子树插入。

  • 直到找到一个空位置，将新节点插入。

2.检查父节点颜色
  • 新节点的颜色为红色，若是插入节点的父亲节点为黑色，则本身符合红黑树性质，无需调整,插入结束.
  • 若插入节点的父亲节点为红色，则需进行调整、执行步骤3
3.调整颜色,旋转维持平衡

若需要调整颜色,则父节点一定是黑色,那么又可以得出,爷爷节点(父节点的父节点)一定是黑色,因为不能出现连续的红色节点,那么这一步的调整则需要根据叔叔节点(父节点的兄弟节点)来判断.

为了方便讲解,我们给这些节点进行缩写命名

爷爷节点 grandfather: g节点

父亲节点 parent: p节点

叔叔节点 uncle: u节点

新插入节点 child: c节点

3.1 叔叔节点为红,调整颜色,无需旋转

在这里插入图片描述

如图所示,只要叔叔节点存在且为黑,那么只需将父节点和叔叔节点置为黑,将爷爷节点置为红,即可完成该步调整.

与AVL树不同,c和p可以是p和g的任意一边的子树,无需判断左右.

这种做法可以理解为:通过爷爷节点的路径黑色节点必包含爷爷节点,那么将他分别放入左右子树的根节点也可以进行平替,通过爷爷节点的路径黑色节点树量没变.

注意:爷爷节点不一定为根节点,而是一颗子树的起始,因此在变为红色后还需接着向上调整,只需将爷爷节点当做新插入的节点c,按照调整规则(步骤2,3)接着向上调整即可.

3.2 叔叔节点不为红色,且为LL或者RR

如图所示:

LL: p为g的左孩子,c为p的左孩子

RR: p为g的右孩子,c为p的右孩子

X: 所有路径黑色节点为h+1的子红黑树

Y: 所有路径黑色节点为h的子红黑树

Y子树经过了u节点,则经过u节点的每条路径上的黑色节点数量为h+1,根据性质5,则X子树的路径上的黑色节点数量都为h+1

但是叔叔节点不为红对应着2种情况

  1. 叔叔节点不存在

    这种情况下**,c一定是新插入的节点**,因为叔叔节点不存在,g的右孩子为NIL节点,即这条路径上的黑色节点数量为2(g,NIL),那么c如果不是新插入的节点,那么其子树中一定存在黑色节点,加上其叶子节点NIL,没条路径上的黑色节点数量超过了2,不符合性质5.

  2. 叔叔节点存在且为黑,此时cur一定不是新插入节点,之前的颜色一定是黑色,现在是红色是因为在变色调整过程中将其调整为红色了

这两种处理方法相同,均为以g点进行旋转,然后将g的颜色置为红,将p的颜色置为黑

3.2.1 叔叔节点不存在

在这里插入图片描述

3.2.2 叔叔节点存在且为黑

在这里插入图片描述

总结一下,可以概括为:

当叔叔节点不为红,

LL: 对g进行右单旋,g变红,p变黑.

RR: 对g进行左单旋,g变红,p变黑

3.3 叔叔节点不为红,且为LR或者RL

LR: p为g的左孩子,c为p的右孩子

RL: p为g的右孩子,c为p的左孩子

与3.2相同,该情况下叔叔节点不为红也对应着2种情况,解释也与3.2一模一样

3.3.1 叔叔节点不存在

在这里插入图片描述

对父亲节点进行一次单旋就可以转化为3.2.1.

3.3.2 叔叔节点存在且为黑

在这里插入图片描述

对父亲节点进行一次单旋就可以转化为3.2.2

需要注意的是:进行旋转后,p与c的相对位置发生变化,在转化后执行3.2的步骤是要注意对应关系(3.3 p 对应3.2 c, 3.3 c对应 3.2 p)

总结一下,可以概括为:

当叔叔节点不为红

LR: 对p进行左单旋,然后对g进行右单旋,g变红,c变黑.

LL: 对p进行右单旋,然后对g进行左单旋,g变红,c变黑

红黑树模拟实现代码

#pragma once

#include<iostream>

#include<cassert>
using namespace std;

enum Color{ RED, BLACK};
template<class K, class V>
struct RBTreeNode {
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;


	K _key;
	V _value;

	Color _color;

	RBTreeNode(const K& key = K(), const V& value = V())
		:_key(key), _value(value), _left(nullptr),
		_right(nullptr), _color(RED), _parent(nullptr){
	}

};

template<class K, class V>
class RBTree {
	typedef RBTreeNode<K, V> Node;

public:

	RBTree() :_root(nullptr) {}
	RBTree(const RBTree& tree)
	{
		_root = Copy(tree._root);
	}

	RBTree& operator=(const RBTree& tree)
	{
		return BSTree(tree);
	}
	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}
	bool Insert(const K& key, const V& value) {

		Node* newNode = new Node(key, value);
		if (_root == nullptr) {
			_root = newNode;
		}
		else {
			Node* parent = _root;
			Node* cur = _root;

			while (cur) {
				parent = cur;
				if (key < cur->_key) cur = cur->_left;
				else if (key > cur->_key) cur = cur->_right;
				else return false;
			}

			if (key < parent->_key) {
				parent->_left = newNode;
			}
			else {
				parent->_right = newNode;
			}
			newNode->_parent = parent;
			cur = newNode;

			while (parent != nullptr && parent != _root && parent->_color == RED){
				Node* grandFather = parent->_parent;
				Node* uncle = (parent == grandFather->_left ? grandFather->_right : grandFather->_left);

				if (uncle != nullptr && uncle->_color == RED){
					parent->_color = uncle->_color = BLACK;
					grandFather->_color = RED;

					cur = grandFather;
					parent = grandFather->_parent;
				}
				else {//(uncle == nullptr || uncle->_color == BLACK)
					
					if (parent == grandFather->_left ){
						//     g
						//   p   u
						// c
						if (cur == parent->_left){
							RotateR(grandFather);

							parent->_color = BLACK;
							grandFather->_color = RED;
						}
						//     g
						//   p   u
						//     c
						else{
							RotateLR(grandFather);
							grandFather->_color = RED;
							cur->_color = BLACK;
						}

					}
					else {
						//     g
						//   u   p
						//         c
						if (cur == parent->_right){
							RotateL(grandFather);
							parent->_color = BLACK;
							grandFather->_color = RED;
						}
						//     g
						//   u   p
						//     c
						else{
							RotateRL(grandFather);
							grandFather->_color = RED;
							cur->_color = BLACK;
						}
					}
					break;
				}
			}

		}

		_root->_color = BLACK;
		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;
	}

	void InOrder()
	{
		_InOrder(_root);
	}
	bool Empty()
	{
		return _root == nullptr;
	}

	bool IsBalance()
	{

		int blackNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_color == BLACK)blackNum++;
			cur = cur->_right;
		}
		return _IsBalance(_root, blackNum,  0);
	}
private:
	void Destroy(Node* root)
	{
		if (root == nullptr) return;

		Destroy(root->_left);
		Destroy(root->_right);

		delete root;
		root = nullptr;
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr) return root;

		Node* newnode = new Node(root->_key, root->_value);

		newnode->_left = Copy(root->_left);
		newnode->_right = Copy(root->_right);

		return newnode;
	}
	bool _IsBalance(Node* root, int blackNum, int selfBlackNum)
	{
		if (root == nullptr)
		{
			if (blackNum != selfBlackNum)
			{
				cout << "Black number error, blackNum: " << blackNum << " , selfBlackNum: " << selfBlackNum << endl;
				return false;
			}
			else
			{
				//cout << "blackNum: " << blackNum << " , selfBlackNum: " << selfBlackNum << endl;
				return true;
			}
		}

		if (root->_color == RED && root->_parent->_color == RED)
		{
			cout << "parent and cur is RED, key:" << root->_key << endl;
			return false;
		}

		if (root->_color == BLACK) selfBlackNum++;
		return _IsBalance(root->_left, blackNum, selfBlackNum) && _IsBalance(root->_right, blackNum, selfBlackNum);
	}

	void RotateR(Node* cur)
	{
		Node* parentOfcur = cur->_parent;
		Node* left = cur->_left;


		cur->_left = left->_right;
		if (left->_right)
			left->_right->_parent = cur;
		left->_right = cur;
		cur->_parent = left;
		if (parentOfcur == nullptr)
		{
			_root = left;
			left->_parent = nullptr;
		}
		else
		{

			if (parentOfcur->_left == cur)
			{
				parentOfcur->_left = left;
				left->_parent = parentOfcur;
			}
			else
			{
				parentOfcur->_right = left;
				left->_parent = parentOfcur;
			}
		}


	}

	void RotateL(Node* cur)
	{
		Node* parentOfcur = cur->_parent;
		Node* right = cur->_right;

		cur->_right = right->_left;
		if (right->_left)
			right->_left->_parent = cur;
		right->_left = cur;
		cur->_parent = right;


		if (parentOfcur == nullptr)
		{
			_root = right;
			right->_parent = nullptr;
		}
		else
		{
			if (parentOfcur->_right == cur)
			{
				parentOfcur->_right = right;
				right->_parent = parentOfcur;
			}
			else
			{
				parentOfcur->_left = right;
				right->_parent = parentOfcur;
			}
		}

	
	}

	void RotateRL(Node* cur)
	{

		Node* parentOfcur = cur->_parent;

		Node* right = cur->_right;
		Node* leftOfright = right->_left;

		RotateR(right);
		RotateL(cur);

	}

	void RotateLR(Node* cur)
	{
		Node* parentOfcur = cur->_parent;

		Node* left = cur->_left;
		Node* rightOfleft = left->_right;

		RotateL(left);
		RotateR(cur);

	}
	void _InOrder(Node* root)
	{
		if (root == nullptr) return;

		_InOrder(root->_left);

		cout << root->_key << ":" << root->_value << endl;

		_InOrder(root->_right);

	}
	Node* _root = nullptr;
};
# c++ # 开发语言 # 算法 # c语言 # linux
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

cover

【安心陪诊 Agent】老年陪诊需求分析：家属、老人、医生三方到底缺什么

avatar AI Agent技术社区
cover

生产级AI Agent系统架构实战，从模块拆解到代码落地与K8s部署

avatar AI Agent技术社区
cover

深度解耦的 AI 新生态：大模型上下文协议（MCP）全栈落地实战

avatar AI Agent技术社区