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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
public virtual bool BinaryTree_Node_Delete(ulong target, string nodeName)
{
ChainManager.Chain_CheckInvalidBlock(target);
ulong primaryTarget = target;
lock (nodeOperations)
{
/* Déjà on cherche */
ulong node = BinaryTree_Node_Search(target, nodeName);
if (node == 0)
return false; /* Man ? she doesn't exists ! */
else
{
/* let's do */
/* déjà on obtient l'enfant droit et gauche */
ulong right = BinaryTree_Node_GetElement(node, BinaryTreeElement.RightKey);
ulong left = BinaryTree_Node_GetElement(node, BinaryTreeElement.LeftKey);
ulong parent = BinaryTree_Node_GetElement(node, BinaryTreeElement.ParentKey);
if (left == 0 && right == 0)
{
/* Aucun enfant, on supprime juste du parent */
if (parent != 0)
{
if (BinaryTree_Node_GetElement(parent, BinaryTreeElement.LeftKey) == node)
{
/* On supprime la gauche */
BinaryTree_Node_SetElement(parent, BinaryTreeElement.LeftKey, 0);
}
else
{
/* Sinon la droite */
BinaryTree_Node_SetElement(parent, BinaryTreeElement.RightKey, 0);
}
}
else
{
/* On vient de supprimer la racine et elle n'avais aucun enfant O_o ... plus de racine */
BinaryTree_Node_SetElement(target, BinaryTreeElement.ChildsRoot, 0);
}
}
else if (left == 0 || right == 0)
{
BinaryTree_Node_DeleteWithOneChild(target, node, right, left, parent);
}
else
{
/* Bon, on a deux enfants sur les bras */
/* On cherche d'abord le noeud le plus à gauche de l'abre droit */
ulong tempRes = right;
ulong temp = 0;
while ((temp = BinaryTree_Node_GetElement(tempRes, BinaryTreeElement.LeftKey)) != 0)
{
tempRes = temp;
}
/* On le supprime de l'endroit où il était */
BinaryTree_Node_DeleteWithOneChild(target, tempRes,
BinaryTree_Node_GetElement(tempRes, BinaryTreeElement.RightKey), 0,
BinaryTree_Node_GetElement(tempRes, BinaryTreeElement.ParentKey));
/* On remplace la clef à supprimer par la valeur de ce dernier */
if (parent != 0)
{
if (BinaryTree_Node_GetElement(parent, BinaryTreeElement.LeftKey) == node)
{
/* On supprime la gauche */
BinaryTree_Node_SetElement(parent, BinaryTreeElement.LeftKey, tempRes);
}
else
{
/* Sinon la droite */
BinaryTree_Node_SetElement(parent, BinaryTreeElement.RightKey, tempRes);
}
BinaryTree_Node_SetElement(tempRes, BinaryTreeElement.ParentKey, parent);
}
else
{
/* nouveau root : l'élément trouvé */
BinaryTree_Node_SetElement(target, BinaryTreeElement.ChildsRoot, tempRes);
BinaryTree_Node_SetElement(tempRes, BinaryTreeElement.RootOwner, target);
BinaryTree_Node_SetElement(tempRes, BinaryTreeElement.ParentKey, 0);
}
/* On modifie son left et right */
BinaryTree_Node_SetElement(tempRes, BinaryTreeElement.LeftKey, left);
BinaryTree_Node_SetElement(tempRes, BinaryTreeElement.RightKey, right);
}
BinaryTree_Node_SetChildCount(primaryTarget, BinaryTree_Node_GetChildCount(primaryTarget) - 1);
return true;
}
}
}
protected virtual void BinaryTree_Node_DeleteWithOneChild(ulong target, ulong node, ulong right, ulong left, ulong parent)
{
/* La node n'a qu'un enfant, on la remplace simplement par celui ci dans le parent */
if (parent != 0)
{
if (BinaryTree_Node_GetElement(parent, BinaryTreeElement.LeftKey) == node)
{
/* On supprime la gauche */
BinaryTree_Node_SetElement(parent, BinaryTreeElement.LeftKey, right != 0 ? right : left);
}
else
{
/* Sinon la droite */
BinaryTree_Node_SetElement(parent, BinaryTreeElement.RightKey, right != 0 ? right : left);
}
BinaryTree_Node_SetElement(right != 0 ? right : left, BinaryTreeElement.ParentKey, parent);
}
else
{
/* nouveau root : l'unique enfant */
BinaryTree_Node_SetElement(target, BinaryTreeElement.ChildsRoot, right != 0 ? right : left);
BinaryTree_Node_SetElement(right != 0 ? right : left, BinaryTreeElement.RootOwner, target);
BinaryTree_Node_SetElement(right != 0 ? right : left, BinaryTreeElement.ParentKey, 0);
}
} |
Implémentation d'un B+Tree pour le stockage d'une liste
).
) soit il manquait certaines opérations (dont la suppression d'une node, j'en ai besoin). Existe-t-il des descriptions complètes de l'algo sous une forme "simple" (pseudocode) sur le net ?
Répondre avec citation
)
Envoyé par millie
), on va dire que j'aime le sport 
).
Partager