STLステップアップツリー構造の関連式容器1(set及びその下層原理の実現)

1.シリアルコンテナと関連コンテナの違い
シーケンスコンテナ:その下層は線形シーケンスのデータ構造であり、中には要素自体が格納されている.eg:vector,list,string,deque,stack,forward_list(C++11). 関連コンテナ:その下層はツリーシーケンスのデータ構造であり、構造のキー値ペアが格納されています.eg:map,set,multimap,multist. いずれもデータを格納するために使用され、関連コンテナの違いは格納されたkey/value(map)、key(set)値であり、データ取得時にシーケンスコンテナよりも効率が高い.
2.setとmultisetの一般的な使用.
set: 1.値が2にあるかないかを検索します.検索ツリーは、挿入しながらソートする.重量除去(検索時に値がツリー上にある位置を判断し、挿入されていない場合)

#include
#include
using std::cout;
//     std  ，      
using std::endl;
//       std   

#include

Multisetはsetに比べて重み付けをサポートせず、検索、ソートに単独で使用できます.しかし、一般的にはsetをもっと使います.

    void test_multi_set()
{
	std::multisets;
	/*typedef std::multiset::iterator msiter;*/
	s.insert(3);
	s.insert(3);
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(5);
	s.insert(4);

	/*std::multiset::iterator it = s.begin();*/
	/*msiter it = s.begin();*/
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << "";
		++it;
	}
	cout << endl;
	
	it = s.find(2);
	//         ，             2.
	cout << *it << endl;
	++it;
	cout << *it << endl;
	++it;
	cout << *it << endl;
	system("pause");
}

注意:

はmap/multimapとは異なり、map/multimapには真のキー値ペアが格納され、setにはvalueのみが格納されるが、下位層には構成されたキー値ペアが実際に格納される.

setに要素を挿入する場合はvalueを挿入するだけで、キー値ペアを構築する必要はありません.

setの要素は繰り返してはいけません(したがってsetを使用して重量を除去することができます).

setの反復器を使用してset内の要素を遍歴し、秩序化シーケンスを得ることができる.

setの要素は、デフォルトでは小さい値で比較されます.

setで要素を検索します.時間の複雑さはlog_です.2 n.

setの要素は変更できません.検索ツリーに影響を与えるルールを直接削除します.

setの下位層は、二叉探索ツリー(赤黒ツリー)を用いて実現される.

3.下位原理(二叉探索木の実現)
3.1二叉探索木の構造

#pragma once
template
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
}; 

template
class BSTree//binary search tree
{
	typedef BSTreeNode Node;
public:
	BSTree()
		:_root(nullptr)
	{}

	~BSTree()
	{}

3.2ツリーの新しいノードの挿入

bool Insert(const K&key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}

3.3ツリーのノードの検索

Node* Find(const K& key)
	{
		Node*cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else{
				return cur;
			}
		}
		return nullptr;
	}

3.4ツリーのノードの削除

bool Erase(const K&key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//   ，    
				//1.     ，        ，    
				//2.     ，        ，    
				//3.        ，                     。
				Node*del = cur;
				if (cur->_left == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
					}
				}
				else if (cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}
				}
				else
				{
					Node* replace = cur->_right;
					Node* p_replace = cur;//   ，  nullptr
					while (replace->_left)
					{
						p_replace = replace;
						replace = replace->_left;
					}
					cur->_key = replace->_key;
					//  replace  
					if (p_replace->_left = replace)
						p_replace->_left = replace->_right;
					else
						p_replace->_right = replace->_right;

					del = replace;
				}
				delete del;
				return true;
			}
		}
		return false;
	}

3.5ツリーの遍歴

void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << "";
		_InOrder(root->_right);
	}

private:
	Node* _root;
};

3.6試験用例(全面をカバーする必要がある)

void TestBSTree()
{
	BSTreet;
	int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();

	t.Erase(2);
	t.Erase(8);
	t.Erase(1);
	t.Erase(5);
	t.InOrder();

	for (auto e : a)
	{
		t.Erase(e);
	}
	t.InOrder();
}