red black tree-SFML

can someone make a red and black tree using SFML ....because i really need... i would appreciate it if someone could make it for me. i really dont know how to use SFML i only know how to use win32 console. so please help me out here.. :(
Are you talking about drawing a red and black tree with SFML, or did you mean writing an implementation of the red-black tree data structure?

http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
I wrote out an entire red-black tree in one of my earlier programs to sort names as efficiently as possible. I noticed a great increase in performance when I finally implemented it, because the tree had thousands of names. The regular tree was quite slow. This was my class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class NamesBinaryTree {  // Storage of names in alphabetically order in a binary tree so that looking up names will be as efficient as possible
	private:
		class Node;  // The way to forward declare a nested class, which is required for defining a member function pointer of NamesBinaryTree::Node in the next line.
		typedef int (NamesBinaryTree::Node::*stringComparisonFunction) (const std::string&, const std::string&);
		enum Colour {RED, BLACK};
		class Node {
			private:
				NamesBinaryTree& namesBinaryTree;  // reference data member because a Node must be part of a NamesBinaryTree
				std::pair<std::string, Person*> personInfo;  // for values of type other than std::pair<std::string, Person*> use T and template<T> the class
				Node *left;
				Node *right;
				Node *parent;
				Colour colour;
				friend class NamesBinaryTree;
			public:
				Node (NamesBinaryTree& tree): namesBinaryTree (tree), colour (RED) {
					// if (!isRoot() && (parent->colour == BLACK)) colour = RED;	
					// else if (parent && (parent->colour == RED)) colour = BLACK;	
				}
				std::pair<std::string, Person*> PersonInfo () const {return personInfo;}
				inline Node* insertNode (NamesBinaryTree& tree, Node*& node, Person* person, stringComparisonFunction sCF);
				inline const Node* searchNode (const Node* node, const std::string& name, stringComparisonFunction sCF);  // searchNode can no longer be declared const ever since the stringComparisonFunction parameter was put in.  I'm not sure why because the stringComparisonFunction sCF is still not changing any data members of Node.
				inline void destroySubtree (Node* node);  // I currently see no reason to destroy any subtree of entireCircleTree.
				inline int countNodesFrom (const Node* node) const;
				inline void displayNodeAndChildren (const Node* node) const;
				inline Node* findMaxNode (Node* node) const;  // Declaring const Node* node gives problems.
				inline Node* removeMaxNode (Node* node, Node* maxNode);
				inline Node* removeNode (Node*& node, const Person* person, stringComparisonFunction sCF);  // Removing names should actually never be done in entireCircleTree (entireCircle only grows or stays the same, but never shrinks).  But p.247-256 in "Jumping into C++" (Allain) does give the code for it.
				bool isRoot () const {return !parent;}
				bool isLeftChild () const {return parent->left == this;}
				bool isRightChild () const {return parent->right == this;}
				// Member functions of NamesBinaryTree::Node that member function pointer stringComparisonFunction can point to:
				inline int std_string_compare (const std::string&, const std::string&);  // this uses std::string::compare
				inline int caseSensitiveCompare (const std::string&, const std::string&) {return NOT_FOUND;}  // not yet defined
				inline int caseInsensitiveCompare (const std::string&, const std::string&) {return NOT_FOUND;}  // not yet defined.  Use tolower (#include <ctype.h>) on every letter and then use std::string::compare.  An example is:  http://www.cplusplus.com/reference/list/list/sort/
				inline int mergedIntoOneWordCaseSensitiveCompare (const std::string&, const std::string&) {return NOT_FOUND;}  // not yet defined
				inline int mergedIntoOneWordCaseInsensitiveCompare (const std::string&, const std::string&) {return NOT_FOUND;}  // not yet defined (remove all ' ' characters, and then use tolower (#include <ctype.h>) on every letter and then use std::string::compare)
		};
		Node *root;  // root Node of the tree
	public:
		NamesBinaryTree (): root (nullptr) {}
		~NamesBinaryTree () {root->destroySubtree (root);}
		typedef Node NamesNode;  // This is needed to declare Node outside of NamesBinaryTree since Node is a private nested class (so use NamesBinaryTreeNode::NamesNode *node, though auto *node = ... would also work too).
		Node* insert (Person* person, stringComparisonFunction sCF) {
			Node* insertedNode = root->insertNode (*this, root, person, sCF);
			redBlackTreeCase1 (insertedNode);  // Configures the tree into a red-black tree after the above insertion to maximize tree balancing.
			return insertedNode;
		}
		const Node* search (const std::string& name, stringComparisonFunction sCF) const {return root->searchNode (root, name, sCF);}
		Node* remove (const Person* person, stringComparisonFunction sCF) {return root->removeNode (root, person, sCF);}
		int numNodes () const {return root->countNodesFrom (root);}
		void displayTree () const;
		//	Red-black tree implementation methods
		inline Node* grandparent (Node* node);
		inline Node* uncle (Node* node);
		inline void redBlackTreeCase1 (Node *node);
		inline void redBlackTreeCase2 (Node *node);
		inline void redBlackTreeCase3 (Node *node);
		inline void redBlackTreeCase4 (Node *node);
		inline void redBlackTreeCase5 (Node *node);
		inline void rotateLeft (Node* node);
		inline void rotateRight (Node* node);
};
Last edited on
the kind of red and black tree is like this.. but not actually like this it can only insert and delete nodes. like this below
http://www.cs.usfca.edu/~galles/visualization/RedBlack.html
Topic archived. No new replies allowed.