0 / 0 / 0
Регистрация: 23.10.2016
Сообщений: 14
|
|
|
1
|
тест для RED-BLACK TREE
18.02.2017, 16:40. Показов 736. Ответов 0
здравствуйте ребята, могли бы вы мне помочь написать black box test для red-black tree(Insert,Find and Delete).
| C++ | 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #pragma once
#ifndef RED_BLACK_TREE_H_
#define RED_BLACK_TREE_H_
#include <utility>
#include <vector>
class BinaryTree
{
public:
enum Color_t {
RED = 0,
BLACK
};
struct Node_t {
Node_t(int key, Node_t *pParent, Node_t *pLeft = NULL, Node_t *pRight = NULL,
Color_t color = BLACK)
: pParent(pParent), pLeft(pLeft), pRight(pRight), color(color), key(key)
{
}
bool IsLeaf() const {
return (!pLeft && !pRight);
}
Node_t *pParent;
Node_t *pLeft;
Node_t *pRight;
Color_t color;
int key;
};
BinaryTree();
~BinaryTree();
std::pair<bool, Node_t *> InsertNode(int key);
bool DeleteNode(int key);
Node_t *FindNode(int key) const;
void GetLeafNodes(std::vector<Node_t *> &outLeafNodes);
void GetAllNodes(std::vector<Node_t *> &outAllNodes);
void GetNonLeafNodes(std::vector<Node_t *> &outNonLeafNodes);
Node_t *GetRoot() { return m_pRoot; }
protected:
Node_t *GrandParent(Node_t *pNode);
Node_t *Uncle(Node_t *pNode);
Node_t *Sibling(Node_t *pNode);
void RotateRight(Node_t *pNode);
void RotateLeft(Node_t *pNode);
void ReplaceNode(Node_t *pReplacedNode, Node_t *pNode);
void InsertFixUpTreeCase1(Node_t *pNewNode);
void InsertFixUpTreeCase2(Node_t *pNewNode);
void InsertFixUpTreeCase3(Node_t *pNewNode);
void InsertFixUpTreeCase4(Node_t *pNewNode);
void InsertFixUpTreeCase5(Node_t *pNewNode);
void DeleteNodeFixUpCase1(Node_t *pNode);
void DeleteNodeFixUpCase2(Node_t *pNode);
void DeleteNodeFixUpCase3(Node_t *pNode);
void DeleteNodeFixUpCase4(Node_t *pNode);
void DeleteNodeFixUpCase5(Node_t *pNode);
void DeleteNodeFixUpCase6(Node_t *pNode);
Node_t *m_pRoot;
};
#endif /* RED_BLACK_TREE_H_ */ |
|
0
|
(
