サンプル・プログラム
二分探索木
左側のノードを優先して再帰探索していくと、要素の小さい順に並べる結果になる。そこで、要素の数をNとすると、平均
の比較回数で目的の要素にたどり着くことができ、探索効率が比較的よい。要素の追加より探索・参照が多い場合によく用いられるデータ構造である。
ただ、検索だけを目的にするなら、PHPでは連想配列を、Pythonでは辞書で代用することが可能である。
PHPによる二分探索木
また、1つのノードにはキーと要素の2つのデータを格納することができるようにした。大小比較はキーで行う。
クラスは外部ファイル "pahooDataStructure.php" に分離している。
1341:
1342: /**
1343: * 親ノードがあれば移動する
1344: * @param なし
1345: * @return pahooTree 親ノード／NULL:親ノードがない
1346: */
1347: function moveParent() {
1348: $res = NULL;
1349: if ($this->parentOBJ != NULL) {
1350: $this->parentOBJ->pointer = $this->parentPTR;
1351: $res = $this->parentOBJ;
1352: }
1353: return $res;
1354: }
1355:
1356: /**
1357: * ツリーの内容を成形して返す（リスト型）
1358: * @param なし
1359: * @return string ツリーの内容
1360: */
1361: function list2() {
1362: $outstr = '[ ';
1363: $this->moveRoot(); //ツリーの先頭へ
1364: while (! $this->istail()) { //ツリー末尾まで繰り返し
1365: if (! $this->isroot()) $outstr .= ', ';
1366: $data = $this->get();
1367: //子ノードの場合
1368: if ($data instanceof pahooTree) {
1369: $outstr .= $data->list2();
1370: } else {
1371: $outstr .= print_r($data, TRUE);
1372: }
1373: $this->moveNext(); //次の要素へ
1374: }
1375: return $outstr .' ]';
1376: }
1377:
1378: /**
1379: * ツリーの内容を成形して返す（階層型）
1380: * @param int $depth 階層の深さ
1381: * @return string ツリーの内容
1382: */
1383: function tree($depth=0) {
1384: if ($depth == 0) {
1385: $outstr = '';
1386: } else {
1387: $outstr = str_repeat(' ', $depth);
1388: $outstr .= "|\n";
1389: }
1390: $this->moveRoot(); //ツリーの先頭へ
1391: while (! $this->istail()) { //ツリー末尾まで繰り返し
1392: $data = $this->get();
1393: //子ノードの場合
1394: if ($data instanceof pahooTree) {
1395: $outstr .= $data->tree($depth + 1);
1396: } else {
1397: $outstr .= str_repeat(' ', $depth);
1398: $outstr .= '+ ' . print_r($data, TRUE) . "\n";
1399: }
1400: $this->moveNext(); //次の要素へ
1401: }
1402: return $outstr;
1403: }
1404:
1405: // End of Class
1406: }
1407:
1408: // pahooBStree クラス ========================================================
1409: class pahooBStree { //二分探索木
1410: public $parent; //親ノードのオブジェクト
1411: public $parentLeft; //親ノードの左ならTRUE、右ならFALSE
1412: public $key; //キー
1413: public $item; //要素
1414: public $left; //子ノード（左）のオブジェクト
1415: public $right; //子ノード（右）のオブジェクト
1416: public $error, $errmsg; //エラーフラグ，エラーメッセージ（未使用）
1417:
1418: /**
1419: * コンストラクタ
1420: * @param mixed $key 格納するキー
1421: * @param mixed $item 格納する要素
1422: * @param pahooTree $paret 親ノード／NULL：自らが親ノード
1423: * @param pahooTree $left 親ノードの左ならTRUE、右ならFALSE
1424: * @return なし
1425: */
1426: function __construct($key=NULL, $item=NULL, $parent=NULL, $left=TRUE) {
1427: $this->parent = $parent;
1428: $this->parentLeft = $left;
1429: $this->key = $key;
1430: $this->item = $item;
1431: $this->left = NULL;
1432: $this->right = NULL;
1433: $this->error = FALSE;
1434: $this->errmsg = '';
1435: }
1436:
1437: /**
1438: * 親ノードがあるかどうかを判定する
1439: * @param なし
1440: * @return bool TRUE：親ノードがある／FALSE：親ノードがない
1441: */
1442: function isparent() {
1443: return ($this->parent == NULL) ? FALSE : TRUE;
1444: }
1445:
1446:
1447: /**
1448: * 子ノードがあるかどうかを判定する
1449: * @param なし
1450: * @return bool TRUE：子ノードがある／FALSE：子ノードがない
1451: */
1452: function ischild() {
1453: return (($this->left == NULL) && ($this->right == NULL)) ? FALSE : TRUE;
1454: }
1455:
1456: /**
1457: * 要素を1つ挿入する
1458: * @param mixed $key 格納するキー
1459: * @param mixed $item 格納する要素
1460: * @param pahooBStree $node 探索開始ノード（省略時は呼び出したノードから）
1461: * @param function $cmp($a, $b) 要素の大小比較関数（省略可能）
1462: * $a > $b なら TRUEを返す
1463: * @return なし
1464: */
1465: function insert($key, $item, $node=NULL, $cmp=NULL) {
1466: if ($node == NULL) $node = $this;
1467:
1468: //大きい場合（右側へ）
1469: if ((($cmp != NULL) && $cmp($node->key, $key)) || ($node->key > $key)) {
1470: if ($node->left == NULL) {
1471: $node->left = new pahooBStree($key, $item, $node, TRUE);
1472: } else {
1473: $this->insert($key, $item, $node->left, $cmp);
1474: }
1475: //小さい場合（左側へ）
1476: } else {
1477: if ($node->right == NULL) {
1478: $node->right = new pahooBStree($key, $item, $node, FALSE);
1479: } else {
1480: $this->insert($key, $item, $node->right, $cmp);
1481: }
1482: }
1483: }
1484:
1485: /**
1486: * 要素を探索する
1487: * @param mixed $key 探索キー
1488: * @param pahooBStree $node 探索開始ノード（省略時は呼び出したノードから）
1489: * @return mixed 要素の値
1490: */
1491: function search($key, $node=NULL) {
1492: if ($node == NULL) $node = $this;
1493:
1494: //左側
1495: if ($node->left != NULL) {
1496: $res = $this->search($key, $node->left);
1497: if ($res != NULL) return $res;
1498: }
1499: //ヒット
1500: if ($node->key == $key) return $node->item;
1501: //右側
1502: if ($node->right != NULL) {
1503: $res = $this->search($key, $node->right);
1504: if ($res != NULL) return $res;
1505: }
1506: return NULL;
1507: }
1508:
1509: /**
1510: * 要素を1つ削除する
1511: * @param mixed $key 削除するキー
1512: * @param pahooBStree $node 探索開始ノード（省略時は呼び出したノードから）
1513: * @return なし
1514: */
1515: function delete($key, $node=NULL) {
1516: if ($node == NULL) $node = $this;
1517: //左側
1518: if ($node->left != NULL) $this->delete($key, $node->left);
1519: //削除
1520: if ($node->key == $key) {
1521: $node->key = NULL;
1522: $node->item = NULL;
1523: }
1524: //右側
1525: if ($node->right != NULL) $this->delete($key, $node->right);
| メソッド | 機能 |
|---|---|
| pahooBStree() | コンストラクタ。格納するキー、要素を引数とする。また、親ノード、親ノードの左右の識別を引数とすることが可能で、これらの引数を省略するとルートに格納する。 |
| isparent() | 親ノードがあるかどうかを判定する。 |
| ischild() | 子ノードがあるかどうかを判定する。 |
| insert() | キー、要素を1つ追加する。追加するノードや、キーの大小比較関数を指定できる。 |
| delete() | キー、要素を1つ削除する。 |
| count() | ツリーに含まれる要素数をカウントする。 |
| tree2array() | ツリーの内容を連想配列に入れて返す。ツリーのキーを連想配列の添字に、ツリーの要素を連想配列の値にする。連想配列はキーの小さい順になるが、重複キーがある場合の結果は不定。 |
| list() | ツリーの内容を成形して返す（リスト型）。結果はキーの小さい順になるが、重複キーがある場合の結果は不定。 |
11: //データ構造クラス
12: require_once('pahooDataStructure.php');
13:
14: // メイン・プログラム ======================================================
15: $bstree = new pahooBStree(); //二分探索木を用意
16: $min = 1; //最小値
17: $max = 10000; //最大値
18: $loop = 20; //ループ回数
19:
20: //要素追加
21: printf("\n要素追加‥‥");
22: for ($i = 0; $i < $loop; $i++) {
23: $k = mt_rand($min, $max); //キー
24: $item = 'hoge' . $k; //要素
25: $bstree->insert($k, $item); //キー、要素を追加
26: if ($i == ($loop / 2)) $key = $k; //探索対象キー
27: if ($i != 0) printf(", ");
28: printf("%d:%s", $k, $item);
29: }
30:
31: //一覧
32: printf("\n\n●一覧");
33: $cnt = $bstree->count();
34: printf(" %d個\n", $cnt);
35: printf("%s\n", $bstree->list());
36:
37: //二分探索
38: printf("\n●二分探索\n");
39: $item = $bstree->search($key);
40: printf("%d:%s", $key, $item);
41:
42: //削除
43: printf("\n\n●削除");
44: $bstree->delete($key);
45: $cnt = $bstree->count();
46: printf(" %d個\n", $cnt);
47: printf("%s\n", $bstree->list());
48:
49: $bstree = NULL;
Pythonによる二分探索木
# pahooBStree クラス ========================================================
class pahooBStree: #二分探索木
"""
* コンストラクタ
* @param auto item 格納する要素
* @param pahooTree paret 親ノード／NULL：自らが親ノード
* @param pahooTree left 親ノードの左ならTRUE、右ならFALSE
* @return なし
"""
def __init__(self, key=None, item=None, parent=None, left=True):
self.parent = parent #親ノードのオブジェクト
self.parentLeft = left #親ノードの左ならTrue、右ならFalse
self.key = key #キー
self.item = item #要素
self.left = None #子ノード（左）のオブジェクト
self.right = None #子ノード（右）のオブジェクト
self.error = False #エラーフラグ
self.errmsg = '' #エラーメッセージ
"""
* 親ノードがあるかどうかを判定する
* @param なし
* @return bool True：親ノードがある／False：親ノードがない
"""
def isparent():
return False if (self.parent == None) else True
"""
* 子ノードがあるかどうかを判定する
* @param なし
* @return bool True：子ノードがある／False：子ノードがない
"""
def ischild():
return False if ((self.left == None) and (self.right == None)) else True
"""
* 要素を1つ追加する
* @param mixed key 格納するキー
* @param mixed item 格納する要素
* @param pahooBStree node 探索開始ノード（省略時は呼び出したノードから）
* @param def cmp(a, b) 要素の大小比較関数（省略可能）
* a > b なら Trueを返す
* @return なし
"""
def insert(self, key, item, node=None, cmp=None):
if (node == None):
node = self
#ノードがない場合
if (node.key == None):
node.key = key
node.item = item
#大きい場合（右側へ）
elif (((cmp != None) and eval(cmp)(node.key, key)) or (node.key > key)):
if (node.left == None):
node.left = pahooBStree(key, item, node, True)
else:
self.insert(key, item, node.left, cmp)
#小さい場合（左側へ）
else:
if (node.right == None):
node.right = pahooBStree(key, item, node, False);
else:
self.insert(key, item, node.right, cmp)
"""
* 要素を探索する
* @param mixed key 探索キー
* @param pahooBStree node 探索開始ノード（省略時は呼び出したノードから）
* @return mixed 要素の値
"""
def search(self, key, node=None):
if (node == None):
node = self
#左側
if (node.left != None):
res = self.search(key, node.left)
if (res != None):
return res
#ヒット
if (node.key == key):
return node.item
#右側
if (node.right != None):
res = self.search(key, node.right)
if (res != None):
return res
return None
"""
* 要素を1つ削除する
* @param mixed key 削除するキー
* @param pahooBStree node 探索開始ノード（省略時は呼び出したノードから）
* @return なし
"""
def delete(self, key, node=None):
if (node == None):
node = self
#左側
if (node.left != None):
self.delete(key, node.left)
#削除
if (node.key == key):
node.key = None
node.item = None
#右側
if (node.right != None):
self.delete(key, node.right)
"""
* ツリーに含まれる要素数をカウントする
* @param pahooBStree node 探索開始ノード（省略時は呼び出したノードから）
* @return int 要素数
"""
def count(self, node=None):
if (node == None):
node = self
res = 0
#要素
if (node.key != None):
res += 1
#左側
if (node.left != None):
res += self.count(node.left)
#右側
if (node.right != None):
res += self.count(node.right)
return res
"""
* ツリーの内容を辞書に入れて返す
* @param pahooBStree $node 探索開始ノード（省略時は呼び出したノードから）
* @return array 連想配列
"""
def tree2array(self, node=None):
if (node == None):
node = self
arr = dict()
#左側
if (node.left != None):
arr.update(self.tree2array(node.left))
#要素
if (node.key != None):
arr[node.key] = node.item
#右側
if (node.right != None):
arr.update(self.tree2array(node.right))
return arr;
"""
* ツリーの内容を成形して返す（リスト型）
* @param pahooBStree node 探索開始ノード（省略時は呼び出したノードから）
* @return string ツリーの内容（※重複キーがある場合の結果は不定）
"""
def list(self, node=None):
arr = self.tree2array(node)
res = "[ "
cnt = 0
for key, val in arr.items():
if (cnt > 0):
res += ", "
res += (str(key) + ":" + val)
cnt += 1
res += " ]"
import sys
import random
#データ構造クラス
import pahooDataStructure
# メイン・プログラム ======================================================
bstree = pahooDataStructure.pahooBStree() #二分探索木を用意
min = 1 #最小値
max = 10000 #最大値
loop = 20 #ループ回数
#要素追加
sys.stdout.write("\n●要素追加\n")
for i in range(loop):
k = random.randrange(min, max) #キー
item = "hoge" + str(k) #要素
bstree.insert(k, item) #キー、要素を追加
if (i == (loop / 2)):
key = k #探索対象キー
if (i != 0):
sys.stdout.write(", ")
sys.stdout.write("{0:d}".format(k))
sys.stdout.write(":{}".format(item))
#一覧
sys.stdout.write("\n\n●一覧")
cnt = bstree.count();
sys.stdout.write(" {0:d}個\n".format(cnt))
sys.stdout.write("{}\n".format(bstree.list()))
#二分探索
sys.stdout.write("\n●二分探索\n")
item = bstree.search(key);
sys.stdout.write("{0:d}:".format(key))
sys.stdout.write("{}".format(item))
#削除
sys.stdout.write("\n\n●削除")
bstree.delete(key);
cnt = bstree.count();
sys.stdout.write(" {0:d}個\n".format(cnt))
sys.stdout.write("{}\n".format(bstree.list()))
