红黑树进阶：正向与反向迭代器的实现及map、set的封装实践

文章目录

  • 一、引言
  • 二、红黑树迭代器设计
    • 1、迭代器的基本概念和分类
    • 2、正向迭代器设计
      • a.迭代器结构定义
      • b.迭代器的 ++与 --
    • 3、反向迭代器设计
      • a.反向迭代器的必要性
      • b.反向迭代器的实现要点
    • 4、红黑树封装迭代器
  • 三、使用红黑树实现Map
  • 四、红黑树实现Set
  • 五、细节理解
    • 1、 typname的使用
    • 2、map和set中仿函数与红黑树中 KeyOfT 的关系
  • RBTree.h（红黑树源码）

一、引言

map和set是两种常见的数据结构，它们分别用于存储键值对和无序集合。红黑树作为一种高效的平衡搜索树，非常适合用于封装这两种数据结构。通过红黑树的特性，我们可以保证map和set在插入、删除和查找操作时的性能稳定且高效。此外，红黑树的有序性也使得map和set在遍历元素时能够按照特定的顺序进行，满足了更多实际应用的需求。

迭代器是一种设计模式，它允许我们顺序访问容器中的元素。对于红黑树来说，设计高效的迭代器是实现其封装Map和Set的关键之一。通过迭代器，我们可以方便地遍历红黑树中的节点，从而实现Map和Set的遍历操作。

在本文中，我们将首先探讨红黑树的正向和反向迭代器设计。正向迭代器允许我们按照中序遍历的顺序访问红黑树的节点，而反向迭代器则允许我们按照逆中序遍历的顺序访问节点。这些迭代器的设计将为我们后续封装Map和Set提供便利。

红黑树基础回顾 -> 深入解析红黑树（RB-Tree）：原理、操作及应用

二、红黑树迭代器设计

1、迭代器的基本概念和分类

迭代器的主要目的是简化对容器的遍历操作，使得无论底层数据结构是顺序表、链表还是树，都可以使用相同的方式来遍历。

在C++中，迭代器通常被实现为类的内部类型，它封装了对容器中元素的指针或引用，并提供了一组操作符重载（如*、->、++、--等）以便对容器进行遍历操作。通过迭代器，可以访问容器中的元素，检查迭代器的有效性（即是否指向一个有效的元素），以及比较两个迭代器是否相等或一个迭代器是否在另一个迭代器之前。

2、正向迭代器设计

a.迭代器结构定义

其中 typedef RBTreeNode<T> Node;是红黑树节点的定义，我们可以在文末的红黑树代码中观察。

template<class T,class Ptr,class Ref>
struct RBTreeIterator {
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ptr, Ref> Self;
	Node* _node;
	RBTreeIterator(Node* node = nullptr)
		:_node(node)
	{}

	Ref operator*() { return _node->_data; }
	Ptr operator->() { return &_node->_data; }
	bool operator!=(const Self& s)const { return _node != s._node; }
	bool operator==(const Self& s) const { return _node == s._node; }
private:
	void increment();
    void decrement();
};

  1. Ref operator*() const:
    这个函数重载了解引用运算符*。它返回当前迭代器所指向的节点的数据成员的引用（_node->_data）。这使得你可以通过解引用迭代器来访问它指向的元素，就像访问指针所指向的对象一样。例如，如果你有一个迭代器it指向红黑树中的一个元素，你可以通过*it来访问这个元素的值。

  2. Ptr operator->() const:
    这个函数重载了成员访问运算符->。它返回一个指向当前迭代器所指向的节点的数据成员的指针（&_node->_data）。这使得你可以通过迭代器来直接访问它所指向元素的成员，就像通过指针访问对象的成员一样。例如，如果元素是一个具有成员member的对象，你可以通过it->member来访问它。

  3. bool operator!=(const Self& s) const:
    这个函数重载了不等于运算符!=。它比较当前迭代器和另一个迭代器s是否指向不同的节点（_node != s._node）。如果它们指向的节点不同，则返回true，否则返回false。这使得你可以使用标准循环结构，如while或for循环，来遍历迭代器范围，直到迭代器不等于另一个迭代器（通常是容器的end()迭代器）。

  4. bool operator==(const Self& s) const:
    这个函数重载了等于运算符==。它比较当前迭代器和另一个迭代器s是否指向相同的节点（_node == s._node）。如果它们指向同一个节点，则返回true，否则返回false。这允许你检查两个迭代器是否指向相同的位置。

这些操作符重载使得迭代器可以像内置指针一样使用，提供了一种更加自然和直观的方式来遍历容器中的元素。同时，由于迭代器内部封装了对节点的引用或指针，它们也提供了更好的封装和抽象，隐藏了底层数据结构的复杂性。

b.迭代器的 ++与 –

递增和递减操作是迭代器设计的关键部分。对于红黑树的迭代器来说，递增操作需要找到当前节点的后继节点，而递减操作需要找到当前节点的前驱节点。

  1. 递增操作 increment()
    • 如果当前节点有右子树，则后继节点是右子树中的最左节点。
    • 如果当前节点没有右子树，则后继节点是当前节点沿父节点链向上移动时遇到的第一个不是从父节点的右子树下来的节点。
void increment() {
    if (_node->_right != nullptr) {
        // 如果当前节点有右子树，找到右子树中的最左节点  
        Node* subLeft = _node->_right;
        while (subLeft->_left) {
            subLeft = subLeft->_left;
        }
        _node = subLeft;
    }
    else {
        // 如果当前节点没有右子树，沿父节点链向上移动  
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent != nullptr && cur == parent->_right) {
            cur = parent;
            parent = parent->_parent;
        }
        _node = parent;
    }
}
  1. 递减操作 decrement()
    • 如果当前节点有左子树，则前驱节点是左子树中的最右节点。
    • 如果当前节点没有左子树，则前驱节点是当前节点沿父节点链向上移动时遇到的第一个不是从父节点的左子树下来的节点。
void decrement() {
    if (_node->_left != nullptr) {
        // 如果当前节点有左子树，找到左子树中的最右节点  
        Node* subRight = _node->_left;
        while (subRight->_right != nullptr) {
            subRight = subRight->_right;
        }
        _node = subRight;
    }
    else {
        // 如果当前节点没有左子树，沿父节点链向上移动  
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent != nullptr && cur == parent->_left) {
            cur = parent;
            parent = parent->_parent;
        }
        _node = parent;
    }
}

前置递增和递减运算符 operator++() 和 operator--()

这两个函数是前置递增和递减运算符的重载。它们分别调用上文的 increment() 和 decrement() 函数来改变迭代器指向的当前节点，并返回迭代器的引用（*this）。

Self& operator++() {
    increment();
    return *this;
}

Self& operator--() {
    decrement();
    return *this;
}

在调用这些函数时，运算符前面的迭代器对象会首先被更新（递增或递减），然后返回更新后的迭代器对象的引用。

后置递增和递减运算符 operator++(int) 和 operator--(int)

这两个函数是后置递增和递减运算符的重载。它们用于创建迭代器的一个临时副本，更新原始迭代器，然后返回这个临时副本。这种形式的递增和递减操作会先返回迭代器当前指向的元素的引用，然后再移动迭代器。

Self operator++(int) {
    Self tmp(*this);
    increment();
    return tmp;
}

Self operator--(int) {
    Self tmp(*this);
    decrement();
    return tmp;
}

注意，这两个函数的参数是一个未命名的整型参数。这个参数的存在纯粹是为了区分前置和后置版本的运算符。在实际调用中，这个参数不会被传递任何值，它仅仅是一个占位符，用于区分前置和后置版本。由于后置版本的运算符实际上先返回当前值再递增或递减，所以需要先创建一个当前迭代器的副本（tmp），然后递增或递减迭代器，最后返回这个副本。

这样的设计使得用户可以用如下两种方式使用迭代器：

// 前置版本
++it;  // 先移动迭代器，再返回新的迭代器
--it;  // 先移动迭代器，再返回新的迭代器

// 后置版本
it++;  // 先返回当前迭代器，再移动迭代器
it--;  // 先返回当前迭代器，再移动迭代器

后置版本的迭代器主要用于那些需要在表达式中先返回当前值再改变迭代器位置的场景，比如在循环中：

for (iterator it = container.begin(); it != container.end(); ++it) {
    // ...
}

在这里，++it 使用了后置递增运算符，它首先返回 it 当前指向的元素的迭代器，然后递增 it 以指向下一个元素。在循环的每次迭代中，这允许我们安全地使用 it 来访问当前元素，同时准备移动到下一个元素。

3、反向迭代器设计

a.反向迭代器的必要性

反向迭代器的必要性主要体现在需要逆序遍历容器或集合元素时。在C++ STL中，很多容器如vector、list、deque等，都提供了正向迭代器来遍历元素，但有时我们可能需要从后往前遍历元素，这时候就需要反向迭代器。例如，在需要查找一个序列中最后一个满足特定条件的元素时，使用反向迭代器可以显著提高效率。

b.反向迭代器的实现要点

正向与反向迭代器应该提供统一的接口，使得用户可以通过相同的方式来操作它们。

  1. 封装正向迭代器：反向迭代器内部封装了一个正向迭代器，通过操作这个正向迭代器来实现反向迭代。
  2. 反向操作：反向迭代器的++、--、*、->等操作需要与正向迭代器的相应操作相反。例如，反向迭代器的++实际上是调用正向迭代器的--，而反向迭代器的--则是调用正向迭代器的++。
  3. 类型别名：反向迭代器需要定义一些类型别名，如Ref和Ptr，来指代结点数据的引用和指针。这些类型别名通常是从正向迭代器中继承的。
  4. 比较操作：反向迭代器还需要定义比较操作，如operator!=和operator==，以便能够比较两个反向迭代器是否相等或不等。这些操作也是通过调用正向迭代器的相应操作来实现的。
  5. 解引用操作：无论是正向迭代器还是反向迭代器，都应该提供*和->操作来访问结点数据。
  6. 递增和递减操作：正向迭代器提供++和--来移动迭代器，反向迭代器也应该提供相同的操作，但它们的语义应该是相反的。
  7. 比较操作：正向和反向迭代器都应该提供比较操作，如!=和==，以便判断两个迭代器是否指向同一位置。
//反向迭代器---迭代器适配器
template<class Iterator>
struct ReverseIterator{
	typedef ReverseIterator<Iterator> Self; //反向迭代器的类型
	typedef typename Iterator::Ref Ref; //结点指针的引用
	typedef typename Iterator::Ptr Ptr; //结点指针

	Iterator _it; //反向迭代器所封装的正向迭代器

	ReverseIterator(Iterator it)
		:_it(it) //根据所给正向迭代器构造一个反向迭代器
	{}

	Ref operator*() { return *_it; }
	Ptr operator->() { return _it.operator->(); }
	Self& operator++() {
		--_it; 
		return *this;
	}
	Self& operator--() {
		++_it; 
		return *this;
	}
	bool operator!=(const Self& s) const { return _it != s._it;	}
	bool operator==(const Self& s) const { return _it == s._it; }
};

4、红黑树封装迭代器

有了上面的两个模板类后，我们仅需在红黑树所在类中添加：

typedef RBTreeIterator<T, T*, T&> iterator;
typedef ReverseIterator<iterator> reverse_iterator;

RBTreeIterator 是一个代表红黑树（Red-Black Tree）迭代器的模板类，用于遍历红黑树容器中的元素。

iterator 类型别名被定义为 RBTreeIterator<T, T*, T&>，简化了对红黑树迭代器的引用，使得我们使用红黑树时能够更简单地引用迭代器类型。

reverse_iterator 类型别名被定义为 ReverseIterator<iterator>，它表示反向迭代器，用于以相反的顺序遍历红黑树中的元素。这个反向迭代器封装了正向迭代器（即 iterator 类型），并提供了反向迭代所需的方法。

这种设计让用户可以透明地选择使用正向迭代器还是反向迭代器来遍历红黑树，而不需要关心底层实现细节。

以下是如何使用这些迭代器类型别名的简单示例：

// 假设 RBTree 是一个红黑树容器模板类
template<class K,class T,class KeyOfT>
class RBTree {
public:
    // ... 其他成员和方法 ...

    // 迭代器类型别名
	typedef RBTreeIterator<T, T*, T&> iterator;
	typedef ReverseIterator<iterator> reverse_iterator;

    // 获取指向容器中第一个元素的迭代器
    iterator begin() {
       		Node* subL = _root;
		while (subL && subL->_left) {
			subL = subL->_left;
		}
		return iterator(subL);
    }

    // 获取指向容器末尾之后位置的迭代器
    iterator end() { return nullptr; }
    
    reverse_iterator rbegin(){
		Node* right = _root;
		while (right && right->_right){
			right = right->_right;
		}
		return reverse_iterator(iterator(right));
	}
	reverse_iterator rend(){
		return reverse_iterator(iterator(nullptr));
	}
    
    //end()  rbegin()在使用时存在缺陷。
    // ... 其他成员和方法 ...
};

int main() {
    RBTree<int> tree;
    // ... 向tree中添加元素 ...

    // 使用正向迭代器遍历树
    for (RBTree<int>::iterator it = tree.begin(); it != tree.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用反向迭代器逆序遍历树
    for (RBTree<int>::reverse_iterator rit = tree.rbegin(); rit != tree.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个示例中，RBTree 类提供了正向迭代器 iterator 和反向迭代器 reverse_iterator。用户可以通过这些迭代器类型别名方便地遍历红黑树中的元素，无论是正向还是反向。

三、使用红黑树实现Map

map模板类中，我们使用了红黑树RBTree来存储键值对。为了适配红黑树，我们定义了一个内部结构体MapKeyOfT，它用于从键值对pair<K, V>中提取键K。这样，红黑树就能根据键来排序和查找键值对了。

在map的公开接口中，我们定义了正向和反向迭代器类型别名iterator和reverse_iterator，它们分别对应于红黑树的正向和反向迭代器。我们也提供了begin()、end()、rbegin()和rend()方法来获取对应的迭代器。

template<class K,class V>
class map {
    struct MapKeyOfT {
        const K& operator()(const pair<K, V>& kv) {
            return kv.first;
        }
    };

public:
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::reverse_iterator reverse_iterator;
    reverse_iterator rbegin() { return _t.rbegin(); }
    reverse_iterator rend() { return _t.rend(); }
    iterator begin() { return _t.begin(); }
    iterator end() { return _t.end(); }
    iterator find(const K& key) { return _t.Find(key); }
    pair<iterator, bool> insert(const pair<K, V>& kv) {
        return _t.Insert(kv);
    }
    V& operator[](const K& key) {
        pair<iterator, bool>ret = insert({ key,V() });
        return ret.first->second;
    }

private:
    RBTree<K, pair<const K, V>, MapKeyOfT>_t;
};

find()方法用于在map中查找具有指定键的元素，调用了红黑树的Find()方法来实现查找功能。

insert()方法用于向map中插入一个键值对。它返回一个包含迭代器和一个布尔值的pair，迭代器指向新插入的元素（如果已存在则指向已存在的元素），布尔值表示是否成功插入了新元素，通过调用红黑树的Insert()方法实现。

operator[]方法用于通过键来访问或插入对应的值。如果键不存在于map中，则插入一个新的键值对，其中键为传入的键，值为类型的默认值（通过V()调用构造函数创建）。然后返回值的引用，这样用户就可以直接修改它。注意，由于这种方式可能在键不存在时改变map的内容，因此在使用时需要小心。

在类的私有部分，我们定义了一个红黑树对象_t来实际存储键值对。红黑树的键类型为K，值类型为pair<const K, V>，这样每个节点就存储了一个键值对。键的提取函数是MapKeyOfT，它确保红黑树能够正确地对键值对进行排序和查找。

四、红黑树实现Set

set模板类使用红黑树来存储唯一的键，并且提供了常见的集合操作。与map类似，这里也定义了一个内部结构体SetKeyOfT，用于从键K中提取键本身（在这个情况下，提取操作实际上只是返回传入的键）。

与map类似，在公开接口中，我们仍然定义了正向和反向迭代器类型别名iterator和reverse_iterator，用于遍历集合中的元素。同时，提供了begin()、end()、rbegin()和rend()方法来获取相应的迭代器。

template<class K>
class set {
    struct SetKeyOfT {
        const K& operator()(const K& key) {
            return key;
        }
    };
public:
    typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;
    typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator;
    reverse_iterator rbegin() { return _t.rbegin(); }
    reverse_iterator rend() { return _t.rend(); }

    iterator begin() { return _t.begin(); }
    iterator end() { return _t.end(); }
    pair<iterator, bool> insert(const K& key) { return _t.Insert(key); }

private:
    RBTree<K, const K, SetKeyOfT> _t;
};

insert()方法用于向集合中插入一个键。如果键已经存在于集合中，则不会插入重复键。该方法返回一个包含迭代器和布尔值的pair，迭代器指向新插入的键（或已存在的键），布尔值表示是否成功插入了新键。

在类的私有部分，我们定义了一个红黑树对象_t来存储键。由于集合中的元素是唯一的，因此红黑树的键类型为K，值类型为const K。这样，每个节点存储了一个不可变的键。键的提取函数是SetKeyOfT，它确保红黑树能够正确地对键进行排序和查找。

注意，这个set实现是基于红黑树的，因此它提供了对数时间复杂度的查找、插入和删除操作。同时，由于红黑树的自平衡特性，它能够在数据动态变化时保持较快的查找速度。

五、细节理解

1、 typname的使用

我们以set为例：

typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator;

在这里RBTree<K, const K, SetKeyOfT> 创建了一个红黑树模板实例，其中：

  • K 是键的类型。
  • const K 是值的类型，表示集合中的元素是不可变的。
  • SetKeyOfT 是一个结构体，它用于从键中提取键（实际上在这里并没有进行转换，因为键已经是所需的形式）。

接着，通过作用域解析运算符 ::，你从这个红黑树模板实例中获取了 iterator 和 reverse_iterator 类型的定义，并将它们分别重命名为 iterator 和 reverse_iterator，以便在 set 类内部和外部都可以方便地引用它们。

这样的做法在设计模板类时是非常常见的，主要有以下几个用意：

  1. 抽象和封装：通过定义类型别名，我们隐藏了底层数据结构的实现细节。用户不需要知道底层是红黑树还是其他数据结构，只需要通过set类提供的接口进行操作即可。这增加了代码的抽象性和封装性，使得代码更加易于理解和维护。

  2. 简化接口：类型别名使得set类的接口更加简洁和一致。用户可以直接使用iterator和reverse_iterator来遍历集合，而不需要记住底层数据结构的迭代器类型。这提高了代码的易用性和可读性。

  3. 提供统一访问方式：无论是正向遍历还是反向遍历，用户都可以通过统一的接口进行访问。这降低了用户的学习成本，提高了代码的可重用性。

  4. 灵活性：通过类型别名，我们可以轻松地更改底层数据结构而不需要修改使用该数据结构的代码。例如，如果将来决定使用另一种数据结构来实现set，只需要更改类型别名的定义即可，而不需要修改所有使用迭代器的代码。

  5. 遵循STL风格：在C++标准模板库（STL）中，这种使用类型别名的做法是非常普遍的。遵循STL风格可以使得自定义的容器类与STL中的容器类在接口和使用方式上保持一致，从而提高了代码的兼容性和可移植性。

综上所述，通过定义类型别名来抽象和封装底层数据结构的细节，我们可以创建一个更加简洁、易用、灵活和兼容的set类。这样的做法在设计和实现模板类时是非常有益的。

2、map和set中仿函数与红黑树中 KeyOfT 的关系

⚠️理解map和set中仿函数的用意：

在这里插入图片描述

在我实现的map和set中，MapKeyOfT和SetKeyOfT（或类似的键提取器）与红黑树中的KeyOfT都扮演着从容器中存储的元素中提取键的角色。

首先，让我们明确每个键提取器的用途：

  • MapKeyOfT：在map容器中，每个元素都是一个键值对（pair<const Key, T>）。MapKeyOfT的作用是从这个键值对中提取出键（Key）部分，以便在红黑树中进行搜索、排序和平衡操作。

  • SetKeyOfT：在set容器中，每个元素就是一个单独的键（Key）。SetKeyOfT的作用相对简单，它直接从元素中提取出键，因为元素本身就是键。

  • KeyOfT：在红黑树的上下文中，KeyOfT是一个更通用的概念，用于从某个类型的元素中提取出键。这个键用于在红黑树中进行比较和排序，以确保树的平衡和高效的搜索性能。

现在，让我们讨论它们之间的关系：

在STL或其他类似的关联容器实现中，map和set通常是基于红黑树实现的。这意味着MapKeyOfT和SetKeyOfT实际上是特定于map和set的键提取器，它们根据容器的需求定制了从元素中提取键的方式。这些键提取器在内部被用于与红黑树进行交互，以确保正确的搜索和排序行为。

从某种程度上说，MapKeyOfT和SetKeyOfT可以看作是KeyOfT在map和set容器中的特化版本。它们针对键值对和单个键的不同情况进行了定制，但背后的原理是相同的：都是从某种类型的元素中提取出用于比较和排序的键。

总结来说，MapKeyOfT、SetKeyOfT和KeyOfT都是为了从元素中提取键而存在的。

RBTree.h（红黑树源码）

#pragma once 
#include <iostream>
#include"ReverseIterator.h"
using namespace std;

enum Color { RED, BLACK };
template<class T>
struct RBTreeNode {
	RBTreeNode(const T& data) :_data(data), _color(RED) {}
	RBTreeNode<T>* _left = nullptr;
	RBTreeNode<T>* _right = nullptr;
	RBTreeNode<T>* _parent = nullptr;
	T _data;
	Color _color;
};


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

public:
	typedef RBTreeIterator<T, T*, T&> iterator;
	typedef ReverseIterator<iterator> reverse_iterator;
	reverse_iterator rbegin(){
		Node* right = _root;
		while (right && right->_right){
			right = right->_right;
		}
		return reverse_iterator(iterator(right));
	}
	reverse_iterator rend(){
		return reverse_iterator(iterator(nullptr));
	}
	iterator begin() {
		Node* subL = _root;
		while (subL && subL->_left) {
			subL = subL->_left;
		}
		return iterator(subL);
	}
	iterator end() { return nullptr; }

	pair<iterator, bool> Insert(const T& data) {
		if (!_root) {
			_root = new Node(data);
			_root->_color = BLACK;
			return { iterator(_root),true };
		}
		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur) {
			if (kot(cur->_data) < kot(data)) {
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data)) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				return { iterator(cur), false };
			}
		}
		cur = new Node(data);
		Node* newnode = cur;
		if (kot(parent->_data) < kot(data))
			parent->_right = cur;
		else
			parent->_left = cur;

		cur->_parent = parent;

		while (parent && parent->_color == RED) {
			Node* grandparent = parent->_parent;
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_color == RED)
				{
					parent->_color = BLACK;
					uncle->_color = BLACK;

					cur = grandparent;
					parent = cur->_parent;
				}
				else {
					if (cur == parent->_left) {
						RotateR(grandparent);
						grandparent->_color = RED;
						parent->_color = BLACK;
					}
					else
					{
						RotateL(parent);
						RotateR(grandparent);
						grandparent->_color = RED;
						cur->_color = BLACK;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_color == RED) {
					parent->_color = BLACK;
					uncle->_color = BLACK;
					cur = grandparent;
					parent = cur->_parent;

				}
				else
				{
					if (cur == parent->_right) {
						RotateL(grandparent);
						parent->_color = BLACK;
						grandparent->_color = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandparent);
						cur->_color = BLACK;
						grandparent->_color = RED;
					}
					break;
				}
			}
		}
		_root->_color = BLACK;
		return { iterator(newnode),true };
	}
	void _Inorder(Node* root) {
		if (root == nullptr) {
			return;
		}
		_Inorder(root->_left);
		cout << root->_kv.first << " ";
		_Inorder(root->_right);
	}

	void  Inorder() {
		_Inorder(_root);
		cout << endl;
	}

	bool Check(Node* cur, int blackNum, int refBlackNum) {
		if (cur == nullptr) {
			if (blackNum != refBlackNum)
			{
				cout << "黑色节点数量不相等" << endl;
				return false;
			}
			//cout << "黑色节点数量：" << blackNum << endl;
			return true;
		}

		if (cur->_color == RED && cur->_parent->_color == RED) {
			cout << cur->_kv.first << "存在连续的红色节点" << endl;
			return false;
		}
		if (cur->_color == BLACK) {
			++blackNum;
		}
		return Check(cur->_left, blackNum, refBlackNum)
			&& Check(cur->_right, blackNum, refBlackNum);
	}

	bool IsBalance() {
		if (_root != nullptr && _root->_color == RED)
			return false;

		int refBlackNum = 0;
		Node* cur = _root;
		while (cur != nullptr) {
			if (cur->_color == BLACK)
				refBlackNum++;
			cur = cur->_left;
		}
		return Check(_root, 0, refBlackNum);
	}
	iterator Find(const K& key) {
		Node* cur = _root;
		while (cur) {
			if (cur->_kv.first < key)
				cur = cur->_right;
			else if (cur->_kv.first > key)
				cur = cur->_left;
			else
				return cur;
		}
		return NULL;
	}


	size_t Size() { return _Size(_root); }

	size_t _Size(Node* root) {
		if (root == NULL)
			return 0;
		return _Size(root->_left)
			+ _Size(root->_right) + 1;
	}

	int _Height(Node* root) {
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	int Height() { return _Height(_root); }
	void RotateL(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		subR->_left = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = subR;
		if (parent == _root) {
			_root = subR;
			subR->_parent = nullptr;
		}
		else {
			if (ppnode->_left == parent)
				ppnode->_left = subR;
			else
				ppnode->_right = subR;

			subR->_parent = ppnode;
		}
	}

	void RotateR(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = subL;
		if (parent == _root) {
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
				ppnode->_left = subL;
			else
				ppnode->_right = subL;
			subL->_parent = ppnode;
		}
	}
private:
	Node* _root = nullptr;
};

本文完整代码： map与set · 比奇堡的Zyb/每日学习 - 码云 - 开源中国 (gitee.com)

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/486817.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【超图 SuperMap3D】【基础API使用示例】51、超图SuperMap3D - 绘制圆｜椭圆形面标注并将视角定位过去

【超图 SuperMap3D】【基础API使用示例】51、超图SuperMap3D - 绘制圆｜椭圆形面标注并将视角定位过去

前言 引擎下载地址&#xff1a;[添加链接描述](http://support.supermap.com.cn/DownloadCenter/DownloadPage.aspx?id2524) 绘制圆形或者椭圆形效果 核心代码 entity viewer.entities.add({// 圆中心点position: { x: -1405746.5243351874, y: 4988274.8462937465, z: 370…
阅读更多...
Web漏洞-SQL注入之二次、加密、DNS加密注入

Web漏洞-SQL注入之二次、加密、DNS加密注入

实例1&#xff1a;sqli-labs21 输入admin&#xff0c;admin 测试&#xff1a; 可以看到注入点在cookie处&#xff0c;发送到decoder&#xff08;解密&#xff09; 所以如果要注入&#xff0c;需要将注入语句加密 Eg&#xff1a;admin’ and 11加密后&#xff1a;YWRtaW4ZIGFu…
阅读更多...
重学SpringBoot3-Profiles介绍

重学SpringBoot3-Profiles介绍

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 重学SpringBoot3-Profiles介绍 Profiles简介如何在Spring Boot中使用Profiles定义Profiles激活ProfilesIDEA设置active profile使用Profile-specific配置文件 条件化Bean…
阅读更多...
[深度学习]yolov8+pyqt5搭建精美界面GUI设计源码实现二

[深度学习]yolov8+pyqt5搭建精美界面GUI设计源码实现二

【简单介绍】 基于目标检测算法YOLOv8和灵活的PyQt5界面开发框架&#xff0c;我们精心打造了一款集直观性、易用性和功能性于一体的目标检测GUI界面。通过深度整合YOLOv8在目标识别上的卓越能力与PyQt5的精致界面设计&#xff0c;我们成功研发出一款既高效又稳定的软件GUI。 …
阅读更多...
中等职业学校大数据课程建设方案

中等职业学校大数据课程建设方案

大数据产业是以数据及数据所蕴含的信息价值为核心生产要素&#xff0c;通过数据技术、数据产品、数据服务等形式&#xff0c;使数据与信息价值在各行业经济活动中得到充分释放的赋能型产业。 大数据产业定义一般分为核心业态、关联业态、衍生业态三大业态。 一、专…
阅读更多...
SaaS模式java智慧工地源码 有演示 AI视频智能分析解决工地安监需求

SaaS模式java智慧工地源码 有演示 AI视频智能分析解决工地安监需求

SaaS模式java智慧工地源码 AI视频智能分析解决工地安监需求 有演示 智慧工地系统充分利用计算机技术、互联网、物联网、云计算、大数据等新一代信息技术&#xff0c;以PC端&#xff0c;移动端&#xff0c;平板端三位一体的管控方式为企业现场工程管理提供了先进的技术手段。让劳…
阅读更多...
【python从入门到精通】--第一战：安装python

【python从入门到精通】--第一战：安装python

&#x1f308; 个人主页&#xff1a;白子寰 &#x1f525; 分类专栏&#xff1a;python从入门到精通&#xff0c;魔法指针&#xff0c;进阶C&#xff0c;C语言&#xff0c;C语言题集&#xff0c;C语言实现游戏&#x1f448; 希望得到您的订阅和支持~ &#x1f4a1; 坚持创作博文…
阅读更多...
HDFS集群环境配置

HDFS集群环境配置

HDFS集群环境配置 环境如下三台服务器&#xff1a; 192.168.32.101 node1192.168.32.102 node2192.168.32.103 node3 一、Hadoop安装包下载​​​​​​​ 点此官网下载​​​​​​​ 二、Hadoop HDFS的角色包含&#xff1a; NameNode&#xff0c;主节点管理者DataNode&am…
阅读更多...
大博主都不告诉你的视频号下载工具！提取视频小程序

大博主都不告诉你的视频号下载工具！提取视频小程序

视频下载plus一款专业的视频号视频提取工具分享平台&#xff0c;免费提供视频号视频使用教程&#xff0c;勿用于商业价值&#xff0c;分享视频下载助手以及提取视频小程序&#xff0c;仅供学习和交流。 视频下载工具 1:视频下载工具&#xff1a;常见的有视频下载软件&#xf…
阅读更多...
计算机三级网络技术 选择+大题234笔记

计算机三级网络技术 选择+大题234笔记

上周停去准备计算机三级的考试啦&#xff0c;在考场上看到题目就知道这次稳了&#xff01;只有一周的时间&#xff0c;背熟笔记&#xff0c;也能稳稳考过计算机三级网络技术&#xff01;
阅读更多...
【算法分析与设计】链表排序

【算法分析与设计】链表排序

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;算法分析与设计 ⛺️稳中求进&#xff0c;晒太阳 题目 给你链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 示例 示例 1&#xff1a; 输入&#xff1a;head […
阅读更多...
计算机软考初级含金量高吗？

计算机软考初级含金量高吗？

并不是说软考初级就没有含金量&#xff0c;对于想评初级职称的考生来说还是很有用处的。根据 国人部 发[2003]39号&#xff1a;通过考试获得证书的人员&#xff0c;表明其已具备从事相应专业岗位工作的水平和能力&#xff0c;用人单位可根据工作需要从获得证书的人员中择优聘任…
阅读更多...
Wireshark使用实训---分析IP包

Wireshark使用实训---分析IP包

1.Wireshark简介和作用 Wireshark是一个开源的网络分析工具&#xff0c;用于捕捉和分析网络数据包。它可以帮助网络管理员和安全专家监控和解决网络问题&#xff0c;同时也可以用于学习和教学网络通信原理。 Wireshark可以在网络中捕获和分析传输的数据包&#xff0c;包括协议…
阅读更多...
OceanBase4.2.2.1 单机集群在ArmX86安装（自测记录）

OceanBase4.2.2.1 单机集群在ArmX86安装（自测记录）

OceanBase OceanBase就不必多加介绍了&#xff0c;本次主要是分享对于它的安装使用&#xff0c;先说说背景&#xff0c;首先接触是因为信创国产化的要求&#xff0c;为满足支持国产化&#xff0c;安装了Arm架构下版本4.0.0&#xff0c;满足支持通过。后来项目实际使用&#xff…
阅读更多...
Oracle数据库入门第二课（查询）

Oracle数据库入门第二课（查询）

前面二白详细讲了一下如何下载安装Oracle以及插件&#xff0c;下面咱们正式学习一下Oracle数据库的查询语言。 DQL:数据库查询语言 一、简单查询 关键字:oracle数据库定义好的有特殊含义的字符 我们的sql语句就是由多种关键字组合而成 语法: select 要查询的内容 from 数…
阅读更多...
操作系统入门框架

操作系统入门框架

博主b站入口&#xff1a;Uncertanity的个人空间 参考资料 王道计算机网络课程 电子科技大学操作系统课件
阅读更多...
玩具蛇（蓝桥杯）

玩具蛇（蓝桥杯）

文章目录 玩具蛇题目描述答案&#xff1a;552dfs 玩具蛇 题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 小蓝有一条玩具蛇&#xff0c;一共有 16 节&#xff0c;上面标着数字 1 至 16。每一节都是一个正方形的形…
阅读更多...
学习人工智能：Attention Is All You Need-1-介绍；Transformer模型架构；编码器，解码器

学习人工智能：Attention Is All You Need-1-介绍；Transformer模型架构；编码器，解码器

Transformer模型是目前最成功的chatGPT&#xff0c;Sora&#xff0c;文心一言&#xff0c;LLama&#xff0c;Grok的基础模型。 《Attention Is All You Need》是一篇由Google DeepMind团队在2017年发表的论文&#xff0c;该论文提出了一种新的神经网络模型&#xff0c;即Trans…
阅读更多...
QT 信号（Signal）与槽（Slot）机制

QT 信号（Signal）与槽（Slot）机制

一、信号&#xff08;signal&#xff09;与槽&#xff08;slot&#xff09; 在QT中&#xff0c;信号&#xff08;signal&#xff09;与槽&#xff08;slot&#xff09;机制是一种用于对象间通信的重要机制。它允许一个对象发出信号&#xff0c;而其他对象可以通过连接到该信号…
阅读更多...
电容笔品牌排行榜：2024五款便宜好用的电容笔极力推荐！

电容笔品牌排行榜：2024五款便宜好用的电容笔极力推荐！

iPad作为我们最常使用的平板&#xff0c;我们想体验iPad的高效使用&#xff0c;丝滑体验&#xff0c;电容笔已经成为许多人的必备工具之一。Apple Pencil适用于专业绘图&#xff0c;一千的售价着实太高&#xff0c;如果普通学生党&#xff0c;用户使用选一款好的电容笔平替&…
阅读更多...
最新文章

Copyright @ 2022~2023