二分探索木

二分木
ツリー構造のうち、あるノードからの分岐先を2つに制限したものを二分木 (にぶんぎ) (binary tree)という。要素の順序を維持しながらデータの追加・削除を行うときに利用するデータ構造である。

サンプル・プログラム

二分探索木

二分探索木
二分木において、常に左のノードに自分より小さな要素をぶら下げるようにしてノードを追加していくものを二分探索木 (にぶんたんさくぎ) (binary search tree)と呼ぶ。
左側のノードを優先して再帰探索していくと、要素の小さい順に並べる結果になる。そこで、要素の数をNとすると、平均 mimetex の比較回数で目的の要素にたどり着くことができ、探索効率が比較的よい。
要素の追加より探索・参照が多い場合によく用いられるデータ構造である。

ただ、検索だけを目的にするなら、PHPでは連想配列を、Pythonでは辞書で代用することが可能である。

PHPによる二分探索木

PHPには二分探索木は用意されていない。そこで、二分探索木クラス pahooBStree を作成した。二分探索木は一般的なツリー構造より単純なので、pahooTree は継承していない。
また、1つのノードにはキーと要素の2つのデータを格納することができるようにした。大小比較はキーで行う。
クラスは外部ファイル "pahooDataStructure.php" に分離している。

1341: // pahooBStreeクラス ========================================================
1342: class pahooBStree {              //二分探索木
1343:     public $parent;              //親ノードのオブジェクト
1344:     public $parentLeft;          //親ノードの左ならTRUE、右ならFALSE
1345:     public $key;                 //キー
1346:     public $item;                    //要素
1347:     public $left;                    //子ノード(左)のオブジェクト
1348:     public $right;                   //子ノード(右)のオブジェクト
1349:     public $error$errmsg;      //エラーフラグ,エラーメッセージ(未使用)
1350: 
1351: /**
1352:  * コンストラクタ
1353:  * @param mixed     $key   格納するキー
1354:  * @param mixed     $item  格納する要素
1355:  * @param pahooTree $paret 親ノード/NULL:自らが親ノード
1356:  * @param pahooTree $left  親ノードの左ならTRUE、右ならFALSE
1357:  * @returnなし
1358: */
1359: function __construct($key=NULL$item=NULL$parent=NULL$left=TRUE) {
1360:     $this->parent = $parent;
1361:     $this->parentLeft = $left;
1362:     $this->key    = $key;
1363:     $this->item   = $item;
1364:     $this->left   = NULL;
1365:     $this->right  = NULL;
1366:     $this->error  = FALSE;
1367:     $this->errmsg = '';
1368: }
1369: 
1370: /**
1371:  * 親ノードがあるかどうかを判定する
1372:  * @paramなし
1373:  * @return bool TRUE:親ノードがある/FALSE:親ノードがない
1374: */
1375: function isparent() {
1376:     return ($this->parent == NULL) ? FALSE : TRUE;
1377: }
1378: 
1379: 
1380: /**
1381:  * 子ノードがあるかどうかを判定する
1382:  * @paramなし
1383:  * @return bool TRUE:子ノードがある/FALSE:子ノードがない
1384: */
1385: function ischild() {
1386:     return (($this->left == NULL) && ($this->right == NULL)) ? FALSE : TRUE;
1387: }
1388: 
1389: /**
1390:  * 要素を1つ追加する
1391:  * @param mixed     $key    格納するキー
1392:  * @param mixed     $item   格納する要素
1393:  * @param pahooBStree $node探索開始ノード(省略時は呼び出したノードから)
1394:  * @param function $cmp($a, $b)  要素の大小比較関数(省略可能)
1395:  *                      $a > $bならTRUEを返す
1396:  * @returnなし
1397: */
1398: function insert($key$item$node=NULL$cmp=NULL) {
1399:     if ($node == NULL)      $node = $this;
1400: 
1401:     //大きい場合(右側へ)
1402:     if ((($cmp != NULL) && $cmp($node->key$key)) || ($node->key > $key)) {
1403:         if ($node->left == NULL) {
1404:             $node->left = new pahooBStree($key$item$nodeTRUE);
1405:         } else {
1406:             $this->insert($key$item$node->left$cmp);
1407:         }
1408:     //小さい場合(左側へ)
1409:     } else {
1410:         if ($node->right == NULL) {
1411:             $node->right = new pahooBStree($key$item$nodeFALSE);
1412:         } else {
1413:             $this->insert($key$item$node->right$cmp);
1414:         }
1415:     }
1416: }
1417: 
1418: /**
1419:  * 要素を探索する
1420:  * @param mixed       $key  探索キー
1421:  * @param pahooBStree $node探索開始ノード(省略時は呼び出したノードから)
1422:  * @return mixed 要素の値
1423: */
1424: function search($key$node=NULL) {
1425:     if ($node == NULL)      $node = $this;
1426: 
1427:     //左側
1428:     if ($node->left != NULL) {
1429:         $res = $this->search($key$node->left);
1430:         if ($res != NULL)    return $res;
1431:     }
1432:     //ヒット
1433:     if ($node->key == $key)  return $node->item;
1434:     //右側
1435:     if ($node->right != NULL) {
1436:         $res = $this->search($key$node->right);
1437:         if ($res != NULL)    return $res;
1438:     }
1439:     return NULL;
1440: }
1441: 
1442: /**
1443:  * 要素を1つ削除する
1444:  * @param mixed       $key  削除するキー
1445:  * @param pahooBStree $node探索開始ノード(省略時は呼び出したノードから)
1446:  * @returnなし
1447: */
1448: function delete($key$node=NULL) {
1449:     if ($node == NULL)      $node = $this;
1450:     //左側
1451:     if ($node->left != NULL)  $this->delete($key$node->left);
1452:     //削除
1453:     if ($node->key == $key) {
1454:         $node->key = NULL;
1455:         $node->item = NULL;
1456:     }
1457:     //右側
1458:     if ($node->right != NULL$this->delete($key$node->right);
1459: }
1460: 
1461: /**
1462:  * ツリーに含まれる要素数をカウントする
1463:  * @param pahooBStree $node  探索開始ノード(省略時は呼び出したノードから)
1464:  * @return int 要素数
1465: */
1466: function count($node=NULL) {
1467:     if ($node == NULL)  $node = $this;
1468:     $res = 0;
1469: 
1470:     //要素
1471:     if ($node->key != NULL)   $res++;
1472:     //左側
1473:     if ($node->left != NULL)  $res += $this->count($node->left);
1474:     //右側
1475:     if ($node->right != NULL$res += $this->count($node->right);
1476: 
1477:     return $res;
1478: }
1479: 
1480: /**
1481:  * ツリーの内容を連想配列に入れて返す
1482:  * @param pahooBStree $node  探索開始ノード(省略時は呼び出したノードから)
1483:  * @return array 連想配列(※重複キーがある場合の結果は不定)
1484: */
1485: function tree2array($node=NULL) {
1486:     if ($node == NULL)  $node = $this;
1487:     $arr = array();
1488: 
1489:     //左側
1490:     if ($node->left != NULL) {
1491:         $arr = $arr + $this->tree2array($node->left);
1492:     }
1493:     //要素
1494:     if ($node->key != NULL) {
1495:         $arr[$node->key] = $node->item;
1496:     }
1497:     //右側
1498:     if ($node->right != NULL) {
1499:         $arr = $arr + $this->tree2array($node->right);
1500:     }
1501: 
1502:     return $arr;
1503: }
1504: 
1505: /**
1506:  * ツリーの内容を成形して返す(リスト型)
1507:  * @param pahooBStree $node探索開始ノード(省略時は呼び出したノードから)
1508:  * @return stringツリーの内容(※重複キーがある場合の結果は不定)
1509: */
1510: function list($node=NULL) {
1511:     $arr = $this->tree2array($node);
1512:     $res = '';
1513:     $cnt = 0;
1514:     foreach ($arr as $key=>$val) {
1515:         if ($cnt > 0)   $res .= '';
1516:         $res .= ($key .':' . $val);
1517:         $cnt++;
1518:     }
1519:     $res .= ' ]';
1520: 
1521:     return $res;
1522: }
1523: 
1524: // End of Class
1525: }

二分探索木 pahooBStree クラスには、以下のメソッドを用意した。
メソッド機能
pahooBStree()コンストラクタ。格納するキー、要素を引数とする。また、親ノード、親ノードの左右の識別を引数とすることが可能で、これらの引数を省略するとルートに格納する。
isparent()親ノードがあるかどうかを判定する。
ischild()子ノードがあるかどうかを判定する。
insert()キー、要素を1つ追加する。追加するノードや、キーの大小比較関数を指定できる。
delete()キー、要素を1つ削除する。
count()ツリーに含まれる要素数をカウントする。
tree2array()ツリーの内容を連想配列に入れて返す。ツリーのキーを連想配列の添字に、ツリーの要素を連想配列の値にする。連想配列はキーの小さい順になるが、重複キーがある場合の結果は不定。
list()ツリーの内容を成形して返す(リスト型)。結果はキーの小さい順になるが、重複キーがある場合の結果は不定。

 

二分探索木 pahooBStree クラスを使ったサンプル・プログラムとして、ランダムに整数を発生させ、それをキーとして二分探索木に登録し、その一覧(キーの小さい順)を表示させたり、キーを削除したりするものが "dt03-42-01.php" である。

0011: //データ構造クラス
0012: require_once('pahooDataStructure.php');
0013: 
0014: // メイン・プログラム ======================================================
0015: $bstree = new pahooBStree();         //二分探索木を用意
0016: $min = 1;                                //最小値
0017: $max = 10000;                            //最大値
0018: $loop = 20;                          //ループ回数
0019: 
0020: //要素追加
0021: printf("\n要素追加‥‥");
0022: for ($i = 0; $i < $loop$i++) {
0023:     $k = mt_rand($min$max);                //キー
0024:     $item = 'hoge' . $k;                 //要素
0025:     $bstree->insert($k$item);           //キー、要素を追加
0026:     if ($i == ($loop / 2))  $key = $k;       //探索対象キー
0027:     if ($i != 0) printf("");
0028:     printf("%d:%s", $k$item);
0029: }
0030: 
0031: //一覧
0032: printf("\n\n●一覧");
0033: $cnt = $bstree->count();
0034: printf(" %d個\n", $cnt);
0035: printf("%s\n", $bstree->list());
0036: 
0037: //二分探索
0038: printf("\n●二分探索\n");
0039: $item = $bstree->search($key);
0040: printf("%d:%s", $key$item);
0041: 
0042: //削除
0043: printf("\n\n●削除");
0044: $bstree->delete($key);
0045: $cnt = $bstree->count();
0046: printf(" %d個\n", $cnt);
0047: printf("%s\n", $bstree->list());
0048: 
0049: $bstree = NULL;

実行結果は下図の通り。
PHPによる二分探索木

Pythonによる二分探索木

Pythonには二分探索木は用意されていない。そこで、PHPの二分探索木クラス pahooBStree を移植した。クラスは外部ファイル "pahooDataStructure.py" に分離している。PHPと同じメソッドを用意した。

0258: class pahooBStree:           #二分探索木
0259:     """
0260:      * コンストラクタ
0261:      * @param auto      item  格納する要素
0262:      * @param pahooTree paret 親ノード/NULL:自らが親ノード
0263:      * @param pahooTree left  親ノードの左ならTRUE、右ならFALSE
0264:      * @returnなし
0265:     
"""
0266:     def __init__(selfkey=Noneitem=Noneparent=Noneleft=True):
0267:         self.parent = parent         #親ノードのオブジェクト
0268:         self.parentLeft = left           #親ノードの左ならTrue、右ならFalse
0269:         self.key    = key                #キー
0270:         self.item   = item               #要素
0271:         self.left   = None               #子ノード(左)のオブジェクト
0272:         self.right  = None               #子ノード(右)のオブジェクト
0273:         self.error  = False          #エラーフラグ
0274:         self.errmsg = ''                #エラーメッセージ
0275: 
0276:     """
0277:      * 親ノードがあるかどうかを判定する
0278:      * @paramなし
0279:      * @return bool True:親ノードがある/False:親ノードがない
0280:     
"""
0281:     def isparent():
0282:         return False if (self.parent == Noneelse True
0283: 
0284:     """
0285:      * 子ノードがあるかどうかを判定する
0286:      * @paramなし
0287:      * @return bool True:子ノードがある/False:子ノードがない
0288:     
"""
0289:     def ischild():
0290:         return False if ((self.left == Noneand (self.right == None)) else True
0291: 
0292:     """
0293:      * 要素を1つ追加する
0294:      * @param mixed       key  格納するキー
0295:      * @param mixed       item格納する要素
0296:      * @param pahooBStree node探索開始ノード(省略時は呼び出したノードから)
0297:      * @param def cmp(a, b)  要素の大小比較関数(省略可能)
0298:      *                 a > bならTrueを返す
0299:      * @returnなし
0300:     
"""
0301:     def insert(selfkeyitemnode=Nonecmp=None):
0302:         if (node == None):
0303:             node = self
0304: 
0305:         #ノードがない場合
0306:         if (node.key == None):
0307:             node.key = key
0308:             node.item = item
0309: 
0310:         #大きい場合(右側へ)
0311:         elif (((cmp != Noneand eval(cmp)(node.keykey)) or (node.key > key)):
0312:             if (node.left == None):
0313:                 node.left = pahooBStree(keyitemnodeTrue)
0314:             else:
0315:                 self.insert(keyitemnode.leftcmp)
0316: 
0317:         #小さい場合(左側へ)
0318:         else:
0319:             if (node.right == None):
0320:                 node.right = pahooBStree(keyitemnodeFalse);
0321:             else:
0322:                 self.insert(keyitemnode.rightcmp)
0323: 
0324:         """
0325:      * 要素を探索する
0326:      * @param mixed       key  探索キー
0327:      * @param pahooBStree node探索開始ノード(省略時は呼び出したノードから)
0328:      * @return mixed 要素の値
0329:         
"""
0330:     def search(selfkeynode=None):
0331:         if (node == None):
0332:             node = self
0333: 
0334:         #左側
0335:         if (node.left != None):
0336:             res = self.search(keynode.left)
0337:             if (res != None):
0338:                 return res
0339:         #ヒット
0340:         if (node.key == key):
0341:             return node.item
0342:         #右側
0343:         if (node.right != None):
0344:             res = self.search(keynode.right)
0345:             if (res != None):
0346:                 return res
0347:         return None
0348: 
0349:     """
0350:      * 要素を1つ削除する
0351:      * @param mixed       key  削除するキー
0352:      * @param pahooBStree node探索開始ノード(省略時は呼び出したノードから)
0353:      * @returnなし
0354:     
"""
0355:     def delete(selfkeynode=None):
0356:         if (node == None):
0357:             node = self
0358: 
0359:         #左側
0360:         if (node.left != None):
0361:             self.delete(keynode.left)
0362:         #削除
0363:         if (node.key == key):
0364:             node.key = None
0365:             node.item = None
0366:         #右側
0367:         if (node.right != None):
0368:             self.delete(keynode.right)
0369: 
0370:     """
0371:      * ツリーに含まれる要素数をカウントする
0372:      * @param pahooBStree node  探索開始ノード(省略時は呼び出したノードから)
0373:      * @return int 要素数
0374:     
"""
0375:     def count(selfnode=None):
0376:         if (node == None):
0377:             node = self
0378:         res = 0
0379: 
0380:         #要素
0381:         if (node.key != None):
0382:             res += 1
0383:         #左側
0384:         if (node.left != None):
0385:             res += self.count(node.left)
0386:         #右側
0387:         if (node.right != None):
0388:             res += self.count(node.right)
0389: 
0390:         return res
0391: 
0392:     """
0393:      * ツリーの内容を辞書に入れて返す
0394:      * @param pahooBStree $node  探索開始ノード(省略時は呼び出したノードから)
0395:      * @return array 連想配列
0396:     
"""
0397:     def tree2array(selfnode=None):
0398:         if (node == None):
0399:             node = self
0400:         arr = dict()
0401: 
0402:         #左側
0403:         if (node.left != None):
0404:             arr.update(self.tree2array(node.left))
0405:         #要素
0406:         if (node.key != None):
0407:             arr[node.key] = node.item
0408:         #右側
0409:         if (node.right != None):
0410:             arr.update(self.tree2array(node.right))
0411: 
0412:         return arr;
0413: 
0414:     """
0415:      * ツリーの内容を成形して返す(リスト型)
0416:      * @param pahooBStree node探索開始ノード(省略時は呼び出したノードから)
0417:      * @return stringツリーの内容(※重複キーがある場合の結果は不定)
0418:     
"""
0419:     def list(selfnode=None):
0420:         arr = self.tree2array(node)
0421:         res = ""
0422:         cnt = 0
0423:         for keyval in arr.items():
0424:             if (cnt > 0):
0425:                 res += ""
0426:             res += (str(key) + ":" + val)
0427:             cnt += 1
0428:         res += " ]"
0429: 
0430:         return res

サンプル・プログラム "dt03-42-02.py" も、PHPの移植である。実行結果も同じである。

0010: import sys
0011: import random
0012: 
0013: #データ構造クラス
0014: import pahooDataStructure
0015: 
0016: # メイン・プログラム ======================================================
0017: bstree = pahooDataStructure.pahooBStree()                #二分探索木を用意
0018: min = 1                             #最小値
0019: max = 10000                     #最大値
0020: loop = 20                           #ループ回数
0021: 
0022: #要素追加
0023: sys.stdout.write("\n●要素追加\n")
0024: for i in range(loop):
0025:     k = random.randrange(minmax)       #キー
0026:     item = "hoge" + str(k)              #要素
0027:     bstree.insert(kitem)               #キー、要素を追加
0028:     if (i == (loop / 2)):
0029:         key = k                         #探索対象キー
0030:     if (i != 0):
0031:         sys.stdout.write("")
0032:     sys.stdout.write("{0:d}".format(k))
0033:     sys.stdout.write(":{}".format(item))
0034: 
0035: #一覧
0036: sys.stdout.write("\n\n●一覧")
0037: cnt = bstree.count();
0038: sys.stdout.write(" {0:d}個\n".format(cnt))
0039: sys.stdout.write("{}\n".format(bstree.list()))
0040: 
0041: #二分探索
0042: sys.stdout.write("\n●二分探索\n")
0043: item = bstree.search(key);
0044: sys.stdout.write("{0:d}:".format(key))
0045: sys.stdout.write("{}".format(item))
0046: 
0047: #削除
0048: sys.stdout.write("\n\n●削除")
0049: bstree.delete(key);
0050: cnt = bstree.count();
0051: sys.stdout.write(" {0:d}個\n".format(cnt))
0052: sys.stdout.write("{}\n".format(bstree.list()))

(この項おわり)
header