サンプル・プログラム
二分探索木
左側のノードを優先して再帰探索していくと、要素の小さい順に並べる結果になる。そこで、要素の数をNとすると、平均 の比較回数で目的の要素にたどり着くことができ、探索効率が比較的よい。
要素の追加より探索・参照が多い場合によく用いられるデータ構造である。
ただ、検索だけを目的にするなら、PHPでは連想配列を、Pythonでは辞書で代用することが可能である。
PHPによる二分探索木
また、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, $node, TRUE);
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, $node, FALSE);
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() | コンストラクタ。格納するキー、要素を引数とする。また、親ノード、親ノードの左右の識別を引数とすることが可能で、これらの引数を省略するとルートに格納する。 |
isparent() | 親ノードがあるかどうかを判定する。 |
ischild() | 子ノードがあるかどうかを判定する。 |
insert() | キー、要素を1つ追加する。追加するノードや、キーの大小比較関数を指定できる。 |
delete() | キー、要素を1つ削除する。 |
count() | ツリーに含まれる要素数をカウントする。 |
tree2array() | ツリーの内容を連想配列に入れて返す。ツリーのキーを連想配列の添字に、ツリーの要素を連想配列の値にする。連想配列はキーの小さい順になるが、重複キーがある場合の結果は不定。 |
list() | ツリーの内容を成形して返す(リスト型)。結果はキーの小さい順になるが、重複キーがある場合の結果は不定。 |
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;
Pythonによる二分探索木
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__(self, key=None, item=None, parent=None, left=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 == None) else True
0283:
0284: """
0285: * 子ノードがあるかどうかを判定する
0286: * @paramなし
0287: * @return bool True:子ノードがある/False:子ノードがない
0288: """
0289: def ischild():
0290: return False if ((self.left == None) and (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(self, key, item, node=None, cmp=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 != None) and eval(cmp)(node.key, key)) or (node.key > key)):
0312: if (node.left == None):
0313: node.left = pahooBStree(key, item, node, True)
0314: else:
0315: self.insert(key, item, node.left, cmp)
0316:
0317: #小さい場合(左側へ)
0318: else:
0319: if (node.right == None):
0320: node.right = pahooBStree(key, item, node, False);
0321: else:
0322: self.insert(key, item, node.right, cmp)
0323:
0324: """
0325: * 要素を探索する
0326: * @param mixed key 探索キー
0327: * @param pahooBStree node探索開始ノード(省略時は呼び出したノードから)
0328: * @return mixed 要素の値
0329: """
0330: def search(self, key, node=None):
0331: if (node == None):
0332: node = self
0333:
0334: #左側
0335: if (node.left != None):
0336: res = self.search(key, node.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(key, node.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(self, key, node=None):
0356: if (node == None):
0357: node = self
0358:
0359: #左側
0360: if (node.left != None):
0361: self.delete(key, node.left)
0362: #削除
0363: if (node.key == key):
0364: node.key = None
0365: node.item = None
0366: #右側
0367: if (node.right != None):
0368: self.delete(key, node.right)
0369:
0370: """
0371: * ツリーに含まれる要素数をカウントする
0372: * @param pahooBStree node 探索開始ノード(省略時は呼び出したノードから)
0373: * @return int 要素数
0374: """
0375: def count(self, node=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(self, node=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(self, node=None):
0420: arr = self.tree2array(node)
0421: res = "[ "
0422: cnt = 0
0423: for key, val in arr.items():
0424: if (cnt > 0):
0425: res += ", "
0426: res += (str(key) + ":" + val)
0427: cnt += 1
0428: res += " ]"
0429:
0430: return res
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(min, max) #キー
0026: item = "hoge" + str(k) #要素
0027: bstree.insert(k, item) #キー、要素を追加
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()))