欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++超詳細(xì)分析紅黑樹(shù)

 更新時(shí)間:2022年06月10日 11:02:06   作者:ymz123_  
這一篇我要跟大家介紹二叉搜索樹(shù)中的另一顆樹(shù)——紅黑樹(shù),它主要是通過(guò)控制顏色來(lái)控制自身的平衡,但它的平衡沒(méi)有AVL樹(shù)的平衡那么嚴(yán)格

紅黑樹(shù)

紅黑樹(shù)的概念

紅黑樹(shù)的概念 紅黑樹(shù),是一種二叉搜索樹(shù),但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色,可以是Red或Black。 通過(guò)對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制,紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍,因而是接近平衡的。

紅黑樹(shù)和AVL樹(shù)都是高效的平衡二叉樹(shù),增刪改查的時(shí)間復(fù)雜度都是O(),紅黑樹(shù)不追求絕對(duì)平衡,其只需保證最長(zhǎng)路徑不超過(guò)最短路徑的2倍,相對(duì)而言,降低了插入和旋轉(zhuǎn)的次數(shù),所以在經(jīng)常進(jìn)行增刪的結(jié)構(gòu)中性能比AVL樹(shù)更優(yōu),而且紅黑樹(shù)實(shí)現(xiàn)比較簡(jiǎn)單,所以實(shí)際運(yùn)用中紅黑樹(shù)更多。

紅黑樹(shù)的性質(zhì)

  • 每個(gè)結(jié)點(diǎn)不是紅色就是黑色
  • 根節(jié)點(diǎn)是黑色的
  • 如果一個(gè)結(jié)點(diǎn)是紅色的,則它的兩個(gè)孩子結(jié)點(diǎn)是黑色的
  • 對(duì)于每個(gè)結(jié)點(diǎn),從該節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡(jiǎn)單路徑上,均包含相同數(shù)目的黑色結(jié)點(diǎn)
  • 每個(gè)葉子結(jié)點(diǎn)都是黑色的(此處的葉子節(jié)點(diǎn)指的是空結(jié)點(diǎn),如上圖路徑數(shù)為11條)

紅黑樹(shù)結(jié)點(diǎn)的定義

enum Color {
	BLACK,
	RED
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	Color _col;
	T _data;

	RBTreeNode(const T& data)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
		,_data(data)
	{}
};

紅黑樹(shù)的插入操作

約定:cur為當(dāng)前節(jié)點(diǎn),p為父節(jié)點(diǎn),g為祖父節(jié)點(diǎn),u為叔叔節(jié)點(diǎn)

情況一

  • 情況一:cur為紅,p為紅,g為黑,u存在且為紅注意:此處看到的樹(shù),可能是一棵完整的樹(shù),也可能是一棵子樹(shù)
  • 解決方式:將p,u改為黑,g改為紅,然后把g當(dāng)成cur,繼續(xù)向上調(diào)整

如果g是根節(jié)點(diǎn),調(diào)整完成后,需要將g改為黑色

如果g是子樹(shù),g一定有雙親,且g的雙親如果是紅色,需要繼續(xù)向上調(diào)整。

情況二

情況二:cur為紅,p為紅,g為黑,u不存在/u為黑

解決方法:p為g的左孩子,cur為p的左孩子,則進(jìn)行右單旋;p為g的右孩子,cur為p的右孩子,則進(jìn)行左單旋。

p變黑,g變紅。

1.如果u節(jié)點(diǎn)不存在,則cur一定是新插入節(jié)點(diǎn),因?yàn)槿绻鹀ur不是新插入節(jié)點(diǎn),則cur和p一定有一個(gè)節(jié)點(diǎn)的顏色是黑色,就不滿(mǎn)足性質(zhì)4:每條路徑黑色節(jié)點(diǎn)個(gè)數(shù)相同。

2.如果u節(jié)點(diǎn)存在,則其一定是黑色的,cur一定不是新增節(jié)點(diǎn),那么cur節(jié)點(diǎn)原來(lái)的顏色一定是黑色的,是作為子樹(shù)的祖父,由第一種情況變化過(guò)來(lái)的

情況三

情況三:cur為紅,p為紅,g為黑,u不存在/u為黑(折線(xiàn)型)

p為g的左孩子,cur為p的右孩子,則針對(duì)p做左單旋轉(zhuǎn);

p為g的右孩子,cur為p的左孩子,則針對(duì)p做右單旋轉(zhuǎn)。

即轉(zhuǎn)換為了情況二。再對(duì)g做對(duì)于旋轉(zhuǎn)。即進(jìn)行雙旋轉(zhuǎn)。

// T->K  set
// T->pair<const K, V> map
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBTreeIterator<T, T&, T*> iterator;
	typedef RBTreeIterator<T, const T&, const T*> const_iterator;

	iterator begin();
	iterator end();

	RBTree()
		:_root(nullptr)
	{}

	// 拷貝構(gòu)造和賦值重載
	// 析構(gòu)

	Node* Find(const K& key);

	pair<iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}

		Node* parent = nullptr;
		Node* cur = _root;

		KeyOfT kot;
		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 make_pair(iterator(cur), false);
			}
		}

		// 新增節(jié)點(diǎn),顏色是紅色,可能破壞規(guī)則3,產(chǎn)生連續(xù)紅色節(jié)點(diǎn)
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED;

		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		// 控制近似平衡
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// 情況一:uncle存在且為紅,進(jìn)行變色處理,并繼續(xù)往上更新處理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				} // 情況二+三:uncle不存在,或者存在且為黑,需要旋轉(zhuǎn)+變色處理
				else
				{
					// 情況二:?jiǎn)涡?變色
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else // 情況三:雙旋 + 變色
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else  // (parent == grandfather->_right)
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (parent->_right == cur)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}

	void RotateR(Node* parent);
	void RotateL(Node* parent);

private:
	Node* _root;
};

紅黑樹(shù)的驗(yàn)證

紅黑樹(shù)的檢測(cè)分為兩步:

  • 檢測(cè)其是否滿(mǎn)足二叉搜索樹(shù)(中序遍歷是否為有序序列)
  • 檢測(cè)其是否滿(mǎn)足紅黑樹(shù)的性質(zhì)

此處用未改造過(guò)的紅黑樹(shù)

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

	Colour _col;
	pair<K, V> _kv;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
		, _kv(kv)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree()
		:_root(nullptr)
	{}

	bool Insert(const pair<K, V>& kv);

	void RotateR(Node* parent);
	void RotateL(Node* parent);

	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 CheckRED_RED(Node* cur)
	{
		if (cur == nullptr)
		{
			return true;
		}

		if (cur->_col == RED && cur->_parent->_col == RED)
		{
			cout << "違反規(guī)則三,存在連續(xù)的紅色節(jié)點(diǎn)" << endl;
			return false;
		}

		return CheckRED_RED(cur->_left)
			&& CheckRED_RED(cur->_right);
	}

	// 檢查每條路徑黑色節(jié)點(diǎn)的數(shù)量
	bool CheckBlackNum(Node* cur, int blackNum, int benchmark) {
		if (cur == nullptr) {
			if (blackNum != benchmark){
				cout << "違反規(guī)則四:黑色節(jié)點(diǎn)的數(shù)量不相等" << endl;
				return false;}
			return true;
		}

		if (cur->_col == BLACK)
			++blackNum;

		return CheckBlackNum(cur->_left, blackNum, benchmark)
			&& CheckBlackNum(cur->_right, blackNum, benchmark);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col == RED)
		{
			cout << "根節(jié)點(diǎn)是紅色,違反規(guī)則二" << endl;
			return false;
		}

		// 算出最左路徑的黑色節(jié)點(diǎn)的數(shù)量作為基準(zhǔn)值
		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++benchmark;
			}

			cur = cur->_left;
		}

		int blackNum = 0;
		return CheckRED_RED(_root) && CheckBlackNum(_root, blackNum, benchmark);
	}

private:
	Node* _root;
};

void TestRBTree1()
{
	const int n = 1000000;
	vector<int> a;
	a.reserve(n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a.push_back(rand());
	}

	RBTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert(make_pair(e, e));
	}

	cout << t1.IsBalance() << endl;
	//t1.InOrder();
}

用紅黑樹(shù)封裝map、set

紅黑樹(shù)的迭代器

begin()與end()

begin()可以放在紅黑樹(shù)中最小節(jié)點(diǎn)(即最左側(cè)節(jié)點(diǎn))的位置

end()放在最大節(jié)點(diǎn)(最右側(cè)節(jié)點(diǎn))的下一個(gè)位置

	typedef RBTreeIterator<T, T&, T*> iterator;
	typedef RBTreeIterator<T, const T&, const T*> const_iterator;

	iterator begin()
	{
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}

		//return left
		return iterator(left);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

操作符重載

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

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	Self& operator--()
	{
		// 跟++基本是反過(guò)來(lái)
		return *this;
	}

	Self& operator++()
	{
		if (_node->_right)
		{
			// 右子樹(shù)中序第一個(gè)節(jié)點(diǎn),也就是右子樹(shù)的最左節(jié)點(diǎn)
			Node* subLeft = _node->_right;
			while (subLeft->_left)
			{
				subLeft = subLeft->_left;
			}

			_node = subLeft;
		}
		else
		{
			// 當(dāng)前子樹(shù)已經(jīng)訪(fǎng)問(wèn)完了,要去找祖先訪(fǎng)問(wèn),沿著到根節(jié)點(diǎn)的路徑往上走,
			// 找孩子是父親左的那個(gè)父親節(jié)點(diǎn)
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
};

封裝map

#pragma once
#include "RBTree.h"

namespace MyMap
{
	template < class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		pair<iterator, bool> insert(const pair<const K, V>& kv)
		{
			return _t.Insert(kv);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};

	void test_map()
	{
		map<string, string> dict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("string", "字符串"));
		dict.insert(make_pair("debug", "找蟲(chóng)子"));
		dict.insert(make_pair("set", "集合"));

		map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;
	}
}

封裝set

#pragma once
#include "RBTree.h"

namespace MySet
{
	template < class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		pair<iterator, bool> insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};

	void test_set()
	{
		set<int> s;
		s.insert(1);
		s.insert(3);
		s.insert(7);
		s.insert(2);
		s.insert(12);
		s.insert(22);
		s.insert(2);
		s.insert(23);
		s.insert(-2);
		s.insert(-9);
		s.insert(30);

		set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

到此這篇關(guān)于C++超詳細(xì)分析紅黑樹(shù)的文章就介紹到這了,更多相關(guān)C++ 紅黑樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 使用C語(yǔ)言繪制柱形圖的示例代碼

    使用C語(yǔ)言繪制柱形圖的示例代碼

    常用的統(tǒng)計(jì)圖有條形圖、柱形圖、折線(xiàn)圖、曲線(xiàn)圖、餅圖、環(huán)形圖、扇形圖,這篇文章主要為大家介紹了C語(yǔ)言中繪制條形圖和柱形圖的方法,需要的可以參考下
    2024-02-02
  • C語(yǔ)言中隨機(jī)數(shù)rand()函數(shù)詳解

    C語(yǔ)言中隨機(jī)數(shù)rand()函數(shù)詳解

    大家好,本篇文章主要講的是C語(yǔ)言中隨機(jī)數(shù)rand()函數(shù)詳解,感興趣的同學(xué)感快來(lái)看一看吧,對(duì)你有幫助的話(huà)記得收藏一下
    2022-02-02
  • VC++中HTControl控件類(lèi)之CHTRichEdit富文本編輯控件實(shí)例

    VC++中HTControl控件類(lèi)之CHTRichEdit富文本編輯控件實(shí)例

    這篇文章主要介紹了VC++中HTControl控件類(lèi)之CHTRichEdit富文本編輯控件,是一個(gè)比較實(shí)用的功能,需要的朋友可以參考下
    2014-08-08
  • C語(yǔ)言計(jì)算代碼執(zhí)行所耗CPU時(shí)鐘周期

    C語(yǔ)言計(jì)算代碼執(zhí)行所耗CPU時(shí)鐘周期

    本文給大家介紹的是使用C語(yǔ)言來(lái)計(jì)算代碼執(zhí)行所耗CPU時(shí)鐘周期的代碼,非常的簡(jiǎn)單實(shí)用,不過(guò)要依托于sync,有需要的小伙伴自己參考下吧。
    2015-03-03
  • C++:構(gòu)造函數(shù),析構(gòu)函數(shù)詳解

    C++:構(gòu)造函數(shù),析構(gòu)函數(shù)詳解

    今天小編就為大家分享一篇關(guān)于C++構(gòu)造函數(shù)和析構(gòu)函數(shù)的文章,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧
    2021-09-09
  • C++中類(lèi)的構(gòu)造函數(shù)初始值列表解讀

    C++中類(lèi)的構(gòu)造函數(shù)初始值列表解讀

    這篇文章主要介紹了C++中類(lèi)的構(gòu)造函數(shù)初始值列表,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-11-11
  • C++內(nèi)聯(lián)函數(shù)詳情

    C++內(nèi)聯(lián)函數(shù)詳情

    這篇文章主要介紹了C++內(nèi)聯(lián)函數(shù),文章主要圍繞C++內(nèi)聯(lián)函數(shù)的相關(guān)資料展開(kāi)詳細(xì)內(nèi)容,需要的朋友可以參考一下,希望對(duì)大家有所幫助
    2021-11-11
  • C++基于棧的深搜算法實(shí)現(xiàn)馬踏棋盤(pán)

    C++基于棧的深搜算法實(shí)現(xiàn)馬踏棋盤(pán)

    這篇文章主要為大家詳細(xì)介紹了C++基于棧的深搜算法實(shí)現(xiàn)馬踏棋盤(pán),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-02-02
  • C語(yǔ)言實(shí)現(xiàn)數(shù)字連連看

    C語(yǔ)言實(shí)現(xiàn)數(shù)字連連看

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)數(shù)字連連看游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-09-09
  • 用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單掃雷游戲

    用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單掃雷游戲

    這篇文章主要為大家詳細(xì)介紹了用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-07-07

最新評(píng)論