B木の高さが低くなる場合
さて、こうやってどんどん要素を削除していくと、親から要素を削除する際に左側の部分木からも右側の部分木からも要素をもらってくることができない状態になります。
つまり、部分木内部の節点がすべてK個の要素しか保持していない状態です。
このような状態に陥ってしまうと、新たに1つでも要素を拠出するとツリーのバランスルールが守れません。そこで、左右の子節点をマージして新たなルートとし、木の高さが一段低くなります。これが、B木が低くなるたった1つの場合です。
このとき、左側部分木の一番右側の一列と、右側部分木の一番左側の一列で上から下までのマージが発生することになりますが、これらはすべてK個の要素しか保持していないことになるので問題なく実行できます。
図10 左右の子節点をマージしてB木が低くなる
B木への追加も削除もできるテストプログラム
前回作成したテストプログラムを改良して、要素の削除もできるようにしました（BTree_Test2.exe）。今回も、なるべくノード内部に実装を集中するようにしています。
複数の節点間でのデータのやりとりが発生する場合には、自分が節点になったつもりで考えると分かりやすいかもしれません。こうしたオブジェクト指向の視点で考えることがアルゴリズムを理解するうえでも役に立つことでしょう。
既定値では、次数が2のB木が生成されます。任意の次数のB木を作成したい場合は、画面右側のSpinEditから次数を指定して「K次のB木を生成」ボタンをクリックしてください。
また、「キーの削除」ボタンで指定したキーを削除できます。いろいろと試してB木の動きを確認して下さい。
●BTreeのソースコード（BTree.pas）
001: unit BTree;
002:
003: interface
004:
005: uses
006: SysUtils, Classes, StrUtils, Dialogs;
007:
008: type
009:
010: TKeyVal = record
011: Key: Integer;
012: Val: Integer;
013: end;
014:
015: TBTreeNode = class(TObject)
016: private
017: FCount: Integer;
018: FMaxKeys: integer;
019: FKeys: array of Integer;
020: FVals: array of integer;
021: FChildNodes: array of TBTreeNode;
022: FOrder: integer;
023: FIsRoot: Boolean;
024: function GetChildNodes(Index: Integer): TBtreeNode;
025: function GetKeys(Index: Integer): Integer;
026: function GetVals(Index: Integer): Integer;
027: procedure InsertKeyVal(Index: Integer; const new_key, new_val: Integer);
028: procedure InsertChildNode(Index: Integer; const new_node: TBtreeNode);
029: procedure SetChildNodes(Index: Integer; const Value: TBtreeNode);
030: procedure SetKeys(Index: Integer; const Value: Integer);
031: procedure SetVals(Index: Integer; const Value: Integer);
032: function IsLeaf:Boolean;
033: procedure SetIsRoot(const Value: Boolean);
034: protected
035: procedure DumpNodes(var S : String; depth : Integer);
036: function InternalAdd(new_key, new_val:Integer; var new_node:TBtreeNode;var return_key, return_val:Integer):boolean;
037: function InternalDel(del_key:Integer; var new_root:TBTreeNode):boolean;
038: procedure GetRightMostinTree(var right_key, right_val : Integer);
039: procedure GetLeftMostInNode(var left_key, left_val : Integer; var return_node:TBTReeNode);
040: procedure GetRightMostInNode(var right_key, right_val : Integer; var return_node:TBTReeNode);
041: procedure SetCount(Value : Integer);
042: public
043: constructor Create(Order:Integer);
044: destructor Destroy;override;
045: property Order : Integer read FOrder;
046: property MaxKeys : Integer read FMaxKeys;
047: property Keys[Index:Integer]:Integer read GetKeys write SetKeys;
048: property Vals[Index:Integer]:Integer read GetVals write SetVals;
049: property ChildNodes[Index:Integer]:TBtreeNode read GetChildNodes write SetChildNodes;
050: property Count:Integer read FCount write SetCount;
051: property IsRoot:Boolean read FIsRoot write SetIsRoot;
052: end;
053:
054: TBtree = class(TObject)
055: private
056: FCount : Integer;
057: FOrder : Integer;
058: FRoot : TBTreeNode;
059: protected
060: public
061: function DumpNodes:String;
062: procedure Add(new_key, new_val:Integer);
063: procedure Del(del_key:Integer);
064: constructor Create(Order:Integer);
065: destructor Destroy;override;
066: property Order : Integer read FOrder;
067: property Count : Integer read FCount;
068: end;
069:
070: implementation
071:
072: { TBTreeNode }
073:
074: //節点のコンストラクタ
075: constructor TBTreeNode.Create(Order:Integer);
076: begin
077: inherited Create;
078:
079: FCount := 0;
080: FOrder := Order;
081: FMaxKeys := Order * 2;
082: FIsRoot := False;
083:
084: //実装を簡易にするため、0..2*K、つまり要素数2K+1の配列とする
085: SetLength(FKeys, FMaxKeys + 1);
086: SetLength(FVals, FMaxKeys + 1);
087:
088: //子節点へのリンクは2K+1個を使用するので、余分を1つとる
089: //こうしておくと、分割の際に、K+1個ずつ分配しやすい
090: SetLength(FChildNodes, FMaxKeys + 2);
091:
092: end;
093:
094: //節点のデストラクタ
095: //子節点があれば、それを解放する
096: destructor TBTreeNode.Destroy;
097: var
098: idx : Integer;
099: begin
100: //ルートが不要になった際に連鎖解放されないための仕掛け
101: if (IsRoot = False) then
102: begin
103: for idx := 0 to FCount do
104: begin
105: if (FChildNodes[idx] <> nil) then FChildNodes[idx].Free;
106: end;
107: end;
108:
109: inherited;
110: end;
111:
112: //節点の状態を返す処理
113: procedure TBTreeNode.DumpNodes(var S: String; depth: Integer);
114: var
115: idx : Integer;
116: begin
117: //節点が葉かどうかで処理を分ける
118: if (IsLeaf = True) then
119: //葉である場合
120: begin
121: for idx := 0 to FCount -1 do
122: begin
123: S := S + DupeString(' ', depth) + IntToStr(FKeys[idx]) + #13#10;
124: end;
125: end else
126: //葉でない場合
127: begin
128: for idx := 0 to FCount -1 do
129: begin
130: FChildNodes[idx].DumpNodes(S, depth + 1);
131: S := S + DupeString(' ', depth) + IntToStr(FKeys[idx]) + #13#10;
132: end;
133: FChildNodes[FCount].DumpNodes(S, depth + 1);
134: end;
135: end;
136:
137: function TBTreeNode.GetChildNodes(Index: Integer): TBtreeNode;
138: begin
139: result := FChildNodes[Index];
140: end;
141:
142: function TBTreeNode.GetKeys(Index: Integer): Integer;
143: begin
144: result := FKeys[Index];
145: end;
146:
147: //節点内の一番左端の値を返して削除する
148: procedure TBTreeNode.GetLeftMostInNode(var left_key, left_val: Integer;
149: var return_node: TBTReeNode);
150: var
151: idx : Integer;
152: begin
153:
154: //左端の値を戻り値に入れる
155: left_key := FKeys[0];
156: left_val := FVals[0];
157: return_node := FChildNodes[0];
158:
159: //左へ詰める
160: for idx := 0 to FCount - 1 do
161: begin
162: FKeys[idx] := FKeys[idx+1];
163: FVals[idx] := FVals[idx+1];
164: end;
165: for idx := 0 to FCount do
166: FChildNodes[idx] := FChildNodes[idx+1];
167:
168: //クリーンアップ
169: FChildNodes[FCount+1] := nil;
170: Dec(FCount);
171: end;
172:
173: //節点内の一番右端の値を返して削除する
174: procedure TBTreeNode.GetRightMostInNode(var right_key, right_val: Integer;
175: var return_node: TBTReeNode);
176: begin
177:
178: //右端の値を戻り値に入れる
179: right_key := FKeys[FCount - 1];
180: right_val := FVals[FCount - 1];
181: return_node := FChildNodes[FCount];
182:
183: //クリーンアップ
184: FChildNodes[FCount] := nil;
185: Dec(FCount);
186: end;
187:
188: //部分木の中の最右端を返す
189: procedure TBTreeNode.GetRightMostinTree(var right_key, right_val: Integer);
190: begin
191: if (FChildNodes[FCount] <> nil) then
192: begin
193: FChildNodes[FCount].GetRightMostinTree(right_key, right_val);
194: end else
195: begin
196: right_key := FKeys[FCount - 1];
197: right_val := FVals[FCount - 1];
198: //ここではキーを削除しない
199: end;
200: end;
201:
202: function TBTreeNode.GetVals(Index: Integer): Integer;
203: begin
204: result := FVals[Index];
205: end;
206:
207: //節点への要素の追加
208: function TBTreeNode.InternalAdd(new_key, new_val:Integer; var new_node:TBtreeNode;var return_key, return_val:Integer):boolean;
209: var
210: idx : Integer;
211: begin
212: //新しいキーがバケット内のどの位置にあたるかをチェックしておく
213: //idxには、new_key の位置が入る
214: if (FCount = 0) then
215: idx := 0
216: else
217: for idx := 0 to FCount - 1 do
218: if (FKeys[idx] > new_key) then break;
219:
220: //葉の場合とそうでない場合で処理を分ける
221: if (IsLeaf = True) then
222: //節点が葉である場合
223: begin
224: //新しいキーより大きい値の左側へ新しいキーを挿入する
225: //余分を1つ取ってあるので必ず挿入できる
226: InsertKeyVal(idx, new_key, new_val);
227:
228: //すでにバケットがいっぱいかどうかで処理を分ける
229: if (FCount > FMaxkeys) then
230: begin
231: //バケットの分割が発生する
232: result := True;
233:
234: //分割用の新しい節点を生成
235: new_node := TBTreeNode.Create(FOrder);
236:
237: //新節点へ値を移動する
238: for idx := 0 to FOrder - 1 do
239: begin
240: //中央値はK番目にあたるので、K+1番目から上を新節点へ移動
241: //(K-1)+(K+1)=2K
242: new_node.Keys[idx] := FKeys[idx + FOrder + 1];
243: new_node.Vals[idx] := FVals[idx + FOrder + 1];
244: end;
245:
246: //親節点へ返すキーと値の組をセット
247: return_key := FKeys[FOrder];
248: return_val := FVals[FOrder];
249:
250: //分割によって、CountはKになる
251: FCount := FOrder;
252: new_node.SetCount(FOrder);
253:
254: exit;
255: end else
256: begin
257: //分割は発生していない
258: result := False;
259: exit;
260: end;
261: end else
262: //節点が葉で無い場合の処理
263: begin
264: //新しいキーより大きいキーの左側の子節点へキーを追加する
265: //idxには、キーの位置が入っているので、同じ位置のFChildNodesがそれにあたる
266:
267: //追加した結果分割が発生したかどうかで処理を分ける
268: if (FChildNodes[idx].InternalAdd(new_key, new_val, new_node, return_key, return_val) = True) then
269: //分割が発生した
270: begin
271: //分割の結果返されたキーを挿入するのも、idxの位置になるので
272: //これを再度チェックする必要はない
273:
274: //新しいキーより大きい値の左側へ新しいキーを挿入する
275: //余分を1つ取ってあるので必ず挿入できる
276: InsertKeyVal(idx, return_key, return_val);
277:
278: //新しい子節点を追加する
279: //位置としては、右側の子節点となるので、idx+1の位置へ挿入する
280: InsertChildNode(idx + 1, new_node);
281:
282: //すでにバケットがいっぱいかどうかで処理を分ける
283: if (FCount > FMaxkeys) then
284: begin
285: //バケットの分割が発生する
286: result := True;
287:
288: //分割用の新しい節点を生成
289: new_node := TBTreeNode.Create(FOrder);
290:
291: //新節点へ値を移動する
292: for idx := 0 to FOrder - 1 do
293: begin
294: //中央値はK番目にあたるので、K+1番目から上を新節点へ移動
295: //0+K+1=K+1 〜 (K-1)+(K+1)=2K を移動する
296: new_node.Keys[idx] := FKeys[idx + FOrder + 1];
297: new_node.Vals[idx] := FVals[idx + FOrder + 1];
298:
299: //子節点へのリンクも同様に移動し、移動元をnilで埋める
300: new_node.ChildNodes[idx] := FChildNodes[idx + FOrder + 1];
301: FChildNodes[idx + FOrder + 1] := nil;
302: end;
303:
304: //子節点へのリンクは、一番右側がはみ出すのでこれを移動する
305: new_node.ChildNodes[FOrder] := FChildNodes[FMaxKeys + 1];
306: FChildNodes[FMaxKeys + 1] := nil;
307:
308: //親節点へ返すキーと値の組をセット
309: return_key := FKeys[FOrder];
310: return_val := FVals[FOrder];
311:
312: //分割によって、CountはKになる
313: FCount := FOrder;
314: new_node.SetCount(FOrder);
315:
316: exit;
317:
318: end else
319: //分割は発生していない
320: begin
321: result := False;
322: exit;
323: end;
324: end else
325: //分割が発生していない
326: begin
327: result := False;
328: exit;
329: end;
330: end;
331: end;
332:
333: //節点からの要素の削除
334: function TBTreeNode.InternalDel(del_key: Integer; var new_root:TBTreeNode): boolean;
335: var
336: idx, Match : Integer;
337: IsMatch, IsShort : Boolean;
338: key, val : Integer;
339: new_node, return_node : TBTreeNode;
340: return_key, return_val : Integer;
341: begin
342: result := False;
343:
344: //削除するキーがバケット内のどの位置にあたるかをチェックしておく
345: //マッチするキーがあればフラグを立てる
346: //idxには、マッチした位置または子節点へ下がる位置が入る
347: IsMatch := False;
348: Match := FCount;
349: for idx := 0 to FCount - 1 do
350: begin
351: if (FKeys[idx] = del_key) then
352: begin
353: IsMatch := True;
354: Match := idx;
355: break;
356: end;
357: if (FKeys[idx] > del_key) then
358: begin
359: IsMatch := False;
360: Match := idx;
361: break;
362: end;
363: end;
364: //削除キーがバケット内の要素のどれよりも大きい場合
365: //マッチせずに、初期値のままとなる
366:
367:
368: //葉の場合とそうでない場合で処理を分ける
369: if (IsLeaf = True) then
370: //節点が葉である場合
371: begin
372: //マッチするキーがあるので、それを削除する
373: if (IsMatch = True) then
374: begin
375: //該当するキーを削除して左へ寄せる
376: //マッチを無視して、マッチから右を左へ寄せれば良い
377: for idx := Match to FCount - 1 do
378: begin
379: FKeys[idx] := FKeys[idx + 1];
380: FVals[idx] := FVals[idx + 1];
381: end;
382: FKeys[FCount] := 0;
383: FVals[FCount] := 0;
384: Dec(FCount);
385:
386: //削除によって節点の要素がK個を割った場合
387: //親の節点に要素を1つ要求する
388: if (FCount < FOrder) then result := True;
389:
390: end else
391: //マッチするキーがないのでエラーを返す
392: begin
393: Exception.CreateFmt('Not Find %d in the tree.', [del_key]);
394: end;
395: end else
396: //節点が葉でない場合の処理
397: begin
398: if (IsMatch = True) then
399: begin
400: //該当するキーを削除して、左部分木の右端で置き換える
401: //結果がTrueの場合には、
402: FChildNodes[Match].GetRightMostInTree(key, val);
403: FKeys[Match] := key;
404: FVals[Match] := val;
405:
406: //もらったキーを左部分木から削除する
407: //複数同じキーがあるのであれば、どれが削除されても結果は変わらない
408: IsShort := FChildNodes[Match].InternalDel(key, new_root);
409:
410: end else
411: //マッチするキーが無いので、子の節点へ削除キーを渡す
412: begin
413: //削除の結果、バケットの要素が不足しているかどうかがIsShortに入る
414: IsShort := FChildNodes[Match].InternalDel(del_key, new_root);
415:
416: end;
417:
418: //子節点での削除の結果、要素が足りないといわれたので
419: //右側の節点の要素をもらいに行く
420: //MatchがCount-1である場合は左側からもらう、それ以外は右側から
421: if (IsShort = True) then
422: begin
423: //MatchがCountである場合は左側を残し、それ以外は右側を残す
424: //つまり右端を例外視する
425: if (Match < FCount) then
426: //この場合は、右側を残す
427: begin
428: //右側の子節点の要素がぎりぎりの場合はマージする
429: if (FChildNodes[Match+1].Count = FOrder) then
430: begin
431: //右側の子節点の要素を右寄せする
432: for idx := FOrder - 1 downto 0 do
433: begin
434: FChildNodes[Match+1].Keys[idx+FOrder] := FChildNodes[Match+1].Keys[idx];
435: FChildNodes[Match+1].Vals[idx+FOrder] := FChildNodes[Match+1].Vals[idx];
436: end;
437: for idx := FOrder downto 0 do
438: FChildNodes[Match+1].ChildNodes[idx+FOrder] := FChildNodes[Match+1].ChildNodes[idx];
439:
440: //左側の子節点の残りの要素を右側の子節点へ移動
441: for idx := 0 to FChildNodes[Match].Count - 1 do
442: begin
443: FChildNodes[Match+1].Keys[idx] := FChildNodes[Match].Keys[idx];
444: FChildNodes[Match+1].Vals[idx] := FChildNodes[Match].Vals[idx];
445: end;
446: for idx := 0 to FChildNodes[Match].Count do
447: FChildNodes[Match+1].ChildNodes[idx] := FChildNodes[Match].ChildNodes[idx];
448:
449: //マッチしているキーを右側の子節点の空いているFOrder-1へ移す
450: FChildNodes[Match+1].Keys[FOrder-1] := FKeys[Match];
451: FChildNodes[Match+1].Vals[FOrder-1] := FVals[Match];
452:
453: //最終的に右側の子節点は満杯となる
454: FChildNodes[Match+1].Count := FMaxKeys;
455:
456: //自節点内で譲渡した要素の分を左に詰める
457: for idx := Match to FCount - 1 do
458: begin
459: FKeys[idx] := FKeys[idx+1];
460: FVals[idx] := FVals[idx+1];
461: end;
462: for idx := Match to FCount do
463: FChildNodes[idx] := FChildNodes[idx+1];
464:
465: //要素が1つ減る
466: Dec(FCount);
467:
468: //結果としてバランス条件が崩れた場合、親へ波及する
469: if (FCount < FOrder) then result := True;
470:
471: //ルートの場合はどんどん要素が減ってなくなる場合がある
472: if (FIsRoot = True) and (FCount = 0) then
473: begin
474: new_root := FChildNodes[0];
475: new_root.Count := FMaxKeys;
476: new_root.IsRoot := True;
477: end;
478: end else
479: //右側の子節点から要素をもらえる場合
480: //MatchがCountより小さい場合は右側からもらう
481: begin
482: //右側の子節点の左端の要素をもらう
483: FChildNodes[Match+1].GetLeftMostInNode(key, val, return_node);
484:
485: //左側の子節点の右端へ自分のマッチした要素を追加する
486: FChildNodes[Match].Keys[FChildNodes[Match].count] := FKeys[Match];
487: FChildNodes[Match].Vals[FChildNodes[Match].count] := FVals[Match];
488: FChildNodes[Match].ChildNodes[FChildNodes[Match].count + 1] := return_node;
489: FChildNodes[Match].Count := FChildNodes[Match].Count + 1;
490:
491: //自分のマッチした要素を右側の子節点から返った値で置き換える
492: FKeys[Match] := key;
493: FVals[Match] := val;
494:
495: end;
496: end else
497: //Match=Countの場合
498: begin
499: //左側の子節点の要素がぎりぎりの場合はマージする
500: if (FChildNodes[Match-1].Count = FOrder) then
501: begin
502:
503: //右側の子節点の残りの要素を左側の子節点へ移動
504: for idx := 0 to FChildNodes[Match].Count - 1 do
505: begin
506: FChildNodes[Match-1].Keys[FOrder+idx+1] := FChildNodes[Match].Keys[idx];
507: FChildNodes[Match-1].Vals[FOrder+idx+1] := FChildNodes[Match].Vals[idx];
508: end;
509: for idx := 0 to FChildNodes[Match].Count do
510: FChildNodes[Match-1].ChildNodes[FOrder+idx+1] := FChildNodes[Match].ChildNodes[idx];
511:
512: //マッチしているキーを左側の子節点の右端へ移す
513: FChildNodes[Match-1].Keys[FOrder] := FKeys[Match-1];
514: FChildNodes[Match-1].Vals[FOrder] := FVals[Match-1];
515:
516: //最終的に右側の子節点は満杯となる
517: FChildNodes[Match-1].Count := FMaxKeys;
518:
519: //自節点内で譲渡した要素の分を左に詰める
520: for idx := Match to FCount - 1 do
521: begin
522: FKeys[idx] := FKeys[idx+1];
523: FVals[idx] := FVals[idx+1];
524: end;
525: for idx := Match to FCount do
526: FChildNodes[idx] := FChildNodes[idx+1];
527:
528: //要素が1つ減る
529: Dec(FCount);
530:
531: //結果としてバランス条件が崩れた場合、親へ波及する
532: if (FCount < FOrder) then result := True;
533:
534: //ルートの場合はどんどん要素が減ってなくなる場合がある
535: if (FIsRoot = True) and (FCount = 0) then
536: begin
537: new_root := FChildNodes[Match-1];
538: new_root.Count := FMaxKeys;
539: new_root.IsRoot := True;
540: end;
541: end else
542: //左側の子節点から要素をもらえる場合
543: //MatchがCountである場合は左側からもらう
544: begin
545: //左側の子節点の右端の要素をもらう
546: FChildNodes[Match-1].GetRightMostInNode(key, val, return_node);
547:
548: //右側の子節点の0位置へ自分のマッチした要素を追加する
549: for idx := FChildNodes[Match].Count - 1 downto 0 do
550: begin
551: FChildNodes[Match].Keys[idx+1]:=FChildNodes[Match].Keys[idx];
552: FChildNodes[Match].Vals[idx+1]:=FChildNodes[Match].Vals[idx];
553: end;
554: for idx := FChildNodes[Match].Count downto 0 do
555: FChildNodes[Match].ChildNodes[idx+1]:=FChildNodes[Match].ChildNodes[idx];
556:
557: FChildNodes[Match].Keys[0] := FKeys[Match-1];
558: FChildNodes[Match].Vals[0] := FVals[Match-1];
559: FChildNodes[Match].ChildNodes[0] := return_node;
560: FChildNodes[Match].Count := FChildNodes[Match].Count + 1;
561:
562: //自分のマッチした要素を右側の子節点から返った値で置き換える
563: FKeys[Match-1] := key;
564: FVals[Match-1] := val;
565:
566: end;
567: end;
568: end;
569: end;
570: end;
571:
572: function TBTreeNode.IsLeaf: Boolean;
573: begin
574: result := (FChildNodes[0] = nil);
575: end;
576:
577: procedure TBTreeNode.SetChildNodes(Index: Integer; const Value: TBtreeNode);
578: begin
579: FChildNodes[index] := Value;
580: end;
581:
582: procedure TBTreeNode.SetCount(Value: Integer);
583: begin
584: FCount := Value;
585: end;
586:
587: procedure TBTreeNode.SetIsRoot(const Value: Boolean);
588: begin
589: FIsRoot := Value;
590: end;
591:
592: procedure TBTreeNode.SetKeys(Index: Integer; const Value: Integer);
593: begin
594: FKeys[Index] := Value;
595: end;
596:
597: //Indexを指定した位置に、ChildNodeを挿入する
598: procedure TBTreeNode.InsertChildNode(Index: Integer;
599: const new_node: TBtreeNode);
600: var
601: idx : Integer;
602: begin
603: //追加するキーのために場所を確保する
604: for idx := FCount + 1 downto index + 1 do
605: begin
606: FChildNodes[idx] := FChildNodes[idx - 1];
607: end;
608:
609: FChildNodes[index] := new_node;
610:
611:
612: end;
613:
614: //Indexを指定した位置に、キー＝Valueを挿入する
615: procedure TBTreeNode.InsertKeyVal(Index: Integer; const new_key, new_val: Integer);
616: var
617: idx : Integer;
618: begin
619:
620: //追加するキーのために場所を確保する
621: for idx := FCount downto index + 1 do
622: begin
623: FKeys[idx] := FKeys[idx - 1];
624: FVals[idx] := FVals[idx - 1];
625: end;
626:
627: FKeys[index] := new_key;
628: FVals[index] := new_val;
629:
630: Inc(FCount);
631: end;
632:
633: procedure TBTreeNode.SetVals(Index: Integer; const Value: Integer);
634: begin
635: FVals[Index] := Value;
636: end;
637:
638: { TBtree }
639:
640: procedure TBtree.Add(new_key, new_val: Integer);
641: var
642: created_node, old_root : TBTreeNode;
643: return_key, return_val : Integer;
644: begin
645: //ルートに対して新しいキーを追加した結果、ルートが分割されるかどうかで処理を分ける
646: if(FRoot.InternalAdd(new_key, new_val, created_node, return_key, return_val)=True) then
647: begin
648: old_root := FRoot;
649: old_root.IsRoot := False;
650:
651: FRoot := TBTreeNode.Create(FOrder);
652: FRoot.IsRoot := True;
653:
654: FRoot.Keys[0] := return_key;
655: FRoot.Vals[0] := return_val;
656: FRoot.ChildNodes[0] := old_root;
657: FRoot.ChildNodes[1] := created_node;
658: FRoot.Count := 1;
659: end;
660: end;
661:
662: //B木のコンストラクタ
663: constructor TBtree.Create(Order: Integer);
664: begin
665: inherited Create;
666:
667: FOrder := Order;
668: FRoot := TBtreeNode.Create(Order);
669: FRoot.IsRoot := True;
670: end;
671:
672: //ツリーから要素を削除する
673: procedure TBtree.Del(del_key: Integer);
674: var
675: idx, Match : Integer;
676: new_root : TBTreeNode;
677: begin
678: //ルートに対してキーの削除を指示
679: //FOrderを割るだけなら捨て置くが、要素が0になった場合
680: //子節点をマージして新しいルートにする
681: new_root := nil;
682: if(FRoot.InternalDel(del_key, new_root) = True) then
683: begin
684: if (new_root <> nil) then
685: begin
686: FRoot.Free;
687: FRoot := new_root;
688: end;
689: end;
690: end;
691:
692: //B木のデストラクタ
693: destructor TBtree.Destroy;
694: begin
695: //ルートが不要になった際に連鎖解放されないための仕掛け
696: FRoot.IsRoot := False;
697: FRoot.Free;
698:
699: inherited;
700: end;
701:
702: //ツリーの内部状態を返す
703: function TBtree.DumpNodes: String;
704: begin
705: FRoot.DumpNodes(Result, 0);
706: end;
707:
708: end.さて、今回で「Delphiアルゴリズムトレーニング」は最終回となります。リンクリスト、キュー、AVL木やB木を解説しながら、Delphiでの実装例を通してアルゴリズムをプログラムで実現する際の手法を見てきました。
ぜひ皆さんも、さまざまなアルゴリズムの実装にチャレンジしてみてください。筆者のつたない知識でどこまでアルゴリズムの世界をお伝えできたか心配ですが、多少なりとも皆さまのお役に立てたのであれば幸いです。それでは、またの機会にお会いしましょう。ご愛読ありがとうございました。
 |
2/2 |
| Index | |
| B木から要素を削除する方法を学ぼう | |
| Page1 B木からの要素の削除（葉の場合） B木からの要素の削除（葉でない場合） |
|
 |
Page2 B木の高さが低くなる場合 B木への追加も削除もできるテストプログラム |
| Appendix BTree.pasのソースコード |
|
 |
Delphiアルゴリズムトレーニング |
| Coding Edgeお勧め記事 |
 |
いまさらアルゴリズムを学ぶ意味 コーディングに役立つ！ アルゴリズムの基本（1） コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう |
|
Zope 3の魅力に迫る Zope 3とは何ぞや？（1） Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか？ |
|
貧弱環境プログラミングのススメ 柴田 淳のコーディング天国 高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く？ |
|
Haskellプログラミングの楽しみ方 のんびりHaskell（1） 関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう |
|
ちょっと変わったLisp入門 Gaucheでメタプログラミング（1） Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう |
フィード 2.0／1.0／0.91
Coding Edge フォーラム 新着記事
- プログラムの実行はどのようにして行われるのか、Linuxカーネルのコードから探る （2017/7/20）
C言語の「Hello World！」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。最終回は、Linuxカーネルの中では、プログラムの起動時にはどのような処理が行われているのかを探る - エンジニアならC言語プログラムの終わりに呼び出されるexit()の中身分かってますよね？ （2017/7/13）
C言語の「Hello World！」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。今回は、プログラムの終わりに呼び出されるexit()の中身を探る - VBAにおけるFileDialog操作の基本＆ドライブの空き容量、ファイルのサイズやタイムスタンプの取得方法 （2017/7/10）
指定したドライブの空き容量、ファイルのタイムスタンプや属性を取得する方法、FileDialog／エクスプローラー操作の基本を紹介します - さらば残業！ 面倒くさいエクセル業務を楽にする「Excel VBA」とは （2017/7/6）
日頃発生する“面倒くさい業務”。簡単なプログラミングで効率化できる可能性がある。本稿では、業務で使うことが多い「Microsoft Excel」で使えるVBAを紹介する。※ショートカットキー、アクセスキーの解説あり
 |
|
|
|
|
注目のテーマ
Coding Edge 記事ランキング
本日
月間
転職／派遣情報を探す
Copyright © ITmedia, Inc. All Rights Reserved.