サンプル・プログラム
平衡木
要素の数をnとすると、最悪の場合の探索回数は
で表される。
となり、本来の探索速度を発揮できる。このようなデータ構造を平衡木（balanced tree）と呼ぶ。
木の回転
右回転というのは、親ノードの左側の子ノード「2」を親ノード「4」の位置へ移動させ、親ノード「4」を親の右ノードへ移動させる。二分探索目の順序を保つよう、それぞれの子ノードの付け替えを行う。
右回転では、上図右側のツリーで、要素「4」の注目する。
左回転とは逆に、親ノードの右側の子ノード「4」を親ノード「2」の位置へ移動させ、親ノード「2」を親の左ノードへ移動させる。二分探索目の順序を保つよう、それぞれの子ノードの付け替えを行う。
右回転を行うと、順序関係は保ったまま木の左側が短くなり、右側が長くなる。
左回転を行うと、順序関係を保ったまま木の右側が短くなり、左側が長くなる。
AVL木
AVL木（Adelson-Velskii and Landis' tree）は、1962年（昭和37年）、ソ連の数学者ゲオルギー・アデルソン・ヴェルスキーとエフゲニー・ランディスが発表した平衡木である。2人の名をとって、この名が付いている。AVL木では、左右の高さの差が1以下になる。
AVL木は、要素の挿入を行うときにバランスさせてやればいい。
つまり、二分探索木における insert を実行し、その時点で左右の深さ depth を比較し、1以上の差があれば、回転を実行する。
PHPによるAVL木
1524: //右側
1525: if ($node->right != NULL) $this->delete($key, $node->right);
1526: }
1527:
1528: /**
1529: * ツリーに含まれる要素数をカウントする
1530: * @param pahooBStree $node 探索開始ノード（省略時は呼び出したノードから）
1531: * @return int 要素数
1532: */
1533: function count($node=NULL) {
1534: if ($node == NULL) $node = $this;
1535: $res = 0;
1536:
1537: //要素
1538: if ($node->key != NULL) $res++;
1539: //左側
1540: if ($node->left != NULL) $res += $this->count($node->left);
1541: //右側
1542: if ($node->right != NULL) $res += $this->count($node->right);
1543:
1544: return $res;
1545: }
1546:
1547: /**
1548: * ツリーの内容を連想配列に入れて返す
1549: * @param pahooBStree $node 探索開始ノード（省略時は呼び出したノードから）
1550: * @return array 連想配列（※重複キーがある場合の結果は不定）
1551: */
1552: function tree2array($node=NULL) {
1553: if ($node == NULL) $node = $this;
1554: $arr = array();
1555:
1556: //左側
1557: if ($node->left != NULL) {
1558: $arr = $arr + $node->tree2array($node->left);
1559: }
1560: //要素
1561: if ($node->key != NULL) {
1562: $arr[$node->key] = $node->item;
1563: }
1564: //右側
1565: if ($node->right != NULL) {
1566: $arr = $arr + $node->tree2array($node->right);
1567: }
1568:
1569: return $arr;
1570: }
1571:
1572: /**
1573: * ツリーの内容を成形して返す（リスト型）
1574: * @param pahooBStree $node 探索開始ノード（省略時は呼び出したノードから）
1575: * @return string ツリーの内容（※重複キーがある場合の結果は不定）
1576: */
1577: function list2($node=NULL) {
1578: $arr = $this->tree2array($node);
1579: $res = '[ ';
1580: $cnt = 0;
1581: foreach ($arr as $key=>$val) {
1582: if ($cnt > 0) $res .= ', ';
1583: $res .= ($key .':' . $val);
1584: $cnt++;
1585: }
1586: $res .= ' ]';
1587:
1588: return $res;
1589: }
1590:
1591: /**
1592: * ツリーの深さを取得する
1593: * @param pahooBStree $node 探索開始ノード（省略時は呼び出したノードから）
1594: * @param int $depth 現在の深さ（省略時は0）
1595: * @return int ツリーの深さ
1596: */
1597: function depth($node=NULL, $depth=0) {
1598: if ($node == NULL) $node = $this;
1599:
1600: //左側
1601: $left = $depth;
1602: if ($node->left != NULL) {
1603: $left = $node->depth($node->left, $depth + 1);
1604: }
1605: //右側
1606: $right = $depth;
1607: if ($node->right != NULL) {
1608: $right = $node->depth($node->right, $depth + 1);
1609: }
1610:
1611: if ($left > $depth) $depth = $left;
1612: if ($right > $depth) $depth = $right;
1613:
1614: return $depth;
1615: }
1616:
1617: /**
1618: * 右回転
1619: * @param なし
1620: * @return なし
avlinsert は、二分探索目における insert を同じ処理を行い、そのノードの下に要素を追加する。
続いて、depth メソッドを用いて左右の深さを比較し、1以上あれば、メソッド rotateRight または rotateLeft を実行する。
1626: $right1 = $this->right;
1627: $right2 = $this->parent->right;
1628: $this->key = $this->parent->key;
1629: $this->item = $this->parent->item;
1630:
1631: $this->parent->key = $key;
1632: $this->parent->item = $item;
1633: $this->parent->left = $left;
1634: if ($this->parent->left != NULL) {
1635: $this->parent->left->parent = $this->parent;
1636: $this->parent->left->parentLeft = TRUE;
1637: }
1638: $this->parent->right = $this;
1639: $this->parentLeft = FALSE;
1640:
1641: $this->left = $right1;
1642: if ($this->left != NULL) {
1643: $this->left->parent = $this;
1644: $this->left->parentLeft = TRUE;
1645: }
1646: $this->right = $right2;
1647: if ($this->right != NULL) {
1648: $this->right->parent = $this;
1649: $this->right->parentLeft = FALSE;
1650: }
1651: }
1652:
1653: /**
1654: * 左回転
1655: * @param なし
1656: * @return なし
1657: */
1658: function rotateLeft() {
1659: $key = $this->key;
1660: $item = $this->item;
1661: $right = $this->right;
1662: $left1 = $this->left;
1663: $left2 = $this->parent->left;
1664: $this->key = $this->parent->key;
1665: $this->item = $this->parent->item;
1666:
1667: $this->parent->key = $key;
1668: $this->parent->item = $item;
1669: $this->parent->right = $right;
1670: if ($this->parent->right != NULL) {
1671: $this->parent->right->parent = $this->parent;
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;
50:
51: /*
52: ** バージョンアップ履歴 ===================================================
53: *
54: * @version 1.0 2018/07/24
55: */
56: ?>
57:
58:
これらは、小さい順に並べた配列 $worst を、関数 shuffle にランダムに並べた配列 $rand の2種類を用意する。
それぞれを、pahooBStree に挿入した場合と、pahooAVLtree に挿入した場合とで、ツリー全体の深さを表示する。
まず、二分探索木 pahooBStree では、小さい順に並んだキーを挿入する場合が最悪のケースで、ツリーの深さは要素の数と同じになってしまう。一方、ランダム並びの方は、比較的深くならずに済んでいる。
PythonによるAVL木
"""
* ツリーの深さを取得する
* @param pahooBStree $node 探索開始ノード（省略時は呼び出したノードから）
* @param int $depth 現在の深さ（省略時は0）
* @return int ツリーの深さ
"""
def depth(self, node=None, depth=0):
if (node == None):
node = self
#左側
left = depth
if (node.left != None):
left = node.depth(node.left, depth + 1)
#右側
right = depth
if (node.right != None):
right = node.depth(node.right, depth + 1)
if (left > depth):
depth = left
if (right > depth):
depth = right
return depth
"""
* 右回転
* @param なし
* @return なし
"""
def rotateRight(self):
key = self.key
item = self.item
left = self.left
right1 = self.right
right2 = self.parent.right
self.key = self.parent.key
self.item = self.parent.item
self.parent.key = key
self.parent.item = item
self.parent.left = left
if (self.parent.left != None):
self.parent.left.parent = self.parent
self.parent.left.parentLeft = True
self.parent.right = self
self.parentLeft = False
self.left = right1
if (self.left != None):
self.left.parent = self
self.left.parentLeft = True
self.right = right2
if (self.right != None):
self.right.parent = self
self.right.parentLeft = False
"""
* 左回転
* @param なし
* @return なし
"""
def rotateLeft(self):
key = self.key
item = self.item
right = self.right
left1 = self.left
left2 = self.parent.left
self.key = self.parent.key
self.item = self.parent.item
self.parent.key = key
self.parent.item = item
self.parent.right = right
if (self.parent.right != None):
self.parent.right.parent = self.parent
self.parent.right.parentLeft = False
self.parent.left = self
self.parentLeft = True
self.left = left2
if (self.left != None):
self.left.parent = self
self.left.parentLeft = True
self.right = left1
if (self.right != None):
self.right.parent = self
self.right.parentLeft = False
avlinsert は、二分探索目における insert を同じ処理を行い、そのノードの下に要素を追加する。
続いて、depth メソッドを用いて左右の深さを比較し、1以上あれば、メソッド rotateRight または rotateLeft を実行する。
class pahooAVLtree(pahooBStree): #AVL木
"""
* 要素を1つ挿入する（AVL木向け）
* @param mixed $key 格納するキー
* @param mixed $item 格納する要素
* @param pahooAVLtree $node 探索開始ノード（省略時は呼び出したノードから）
* @param function $cmp($a, $b) 要素の大小比較関数（省略可能）
* $a > $b なら TRUEを返す
* @return なし
"""
def avlinsert(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 = pahooAVLtree(key, item, node, True)
else:
self.avlinsert(key, item, node.left, cmp)
#小さい場合（左側へ）
else:
if (node.right == None):
node.right = pahooAVLtree(key, item, node, False);
else:
self.avlinsert(key, item, node.right, cmp)
#平衡させる
a = node.depth()
if (node.parent != None):
if (node.parentLeft):
b = node.parent.right.depth() if (node.parent.right != None) else 0
if (a - b >= 1):
node.rotateRight()
else:
b = node.parent.left.depth() if (node.parent.left != None) else 0
if (a - b >= 1):
node.rotateLeft()
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);
探索効率が低下しないよう左右のバランスをとった二分探索木のことを平衡木と呼び、とくに AVL木は理想的なバランスを実現できる。
今回は、PHPとPythonのためのAVL木クラスを用意する。