サンプル・プログラム
平衡木
要素の数を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: * ツリーの深さを取得する
1526: * @param pahooBStree $node 探索開始ノード（省略時は呼び出したノードから）
1527: * @param int $depth 現在の深さ（省略時は0）
1528: * @return intツリーの深さ
1529: */
1530: function depth($node=NULL, $depth=0) {
1531: if ($node == NULL) $node = $this;
1532:
1533: //左側
1534: $left = $depth;
1535: if ($node->left != NULL) {
1536: $left = $node->depth($node->left, $depth + 1);
1537: }
1538: //右側
1539: $right = $depth;
1540: if ($node->right != NULL) {
1541: $right = $node->depth($node->right, $depth + 1);
1542: }
1543:
1544: if ($left > $depth) $depth = $left;
1545: if ($right > $depth) $depth = $right;
1546:
1547: return $depth;
1548: }
1549:
1550: /**
1551: * 右回転
1552: * @paramなし
1553: * @returnなし
1554: */
1555: function rotateRight() {
1556: $key = $this->key;
1557: $item = $this->item;
1558: $left = $this->left;
1559: $right1 = $this->right;
1560: $right2 = $this->parent->right;
1561: $this->key = $this->parent->key;
1562: $this->item = $this->parent->item;
1563:
1564: $this->parent->key = $key;
1565: $this->parent->item = $item;
1566: $this->parent->left = $left;
1567: if ($this->parent->left != NULL) {
1568: $this->parent->left->parent = $this->parent;
1569: $this->parent->left->parentLeft = TRUE;
1570: }
1571: $this->parent->right = $this;
1572: $this->parentLeft = FALSE;
1573:
1574: $this->left = $right1;
1575: if ($this->left != NULL) {
1576: $this->left->parent = $this;
1577: $this->left->parentLeft = TRUE;
1578: }
1579: $this->right = $right2;
1580: if ($this->right != NULL) {
1581: $this->right->parent = $this;
1582: $this->right->parentLeft = FALSE;
1583: }
1584: }
1585:
1586: /**
1587: * 左回転
1588: * @paramなし
1589: * @returnなし
1590: */
1591: function rotateLeft() {
1592: $key = $this->key;
1593: $item = $this->item;
1594: $right = $this->right;
1595: $left1 = $this->left;
1596: $left2 = $this->parent->left;
1597: $this->key = $this->parent->key;
1598: $this->item = $this->parent->item;
1599:
1600: $this->parent->key = $key;
1601: $this->parent->item = $item;
1602: $this->parent->right = $right;
1603: if ($this->parent->right != NULL) {
1604: $this->parent->right->parent = $this->parent;
1605: $this->parent->right->parentLeft = FALSE;
1606: }
1607: $this->parent->left = $this;
1608: $this->parentLeft = TRUE;
1609:
1610: $this->left = $left2;
1611: if ($this->left != NULL) {
1612: $this->left->parent = $this;
1613: $this->left->parentLeft = TRUE;
1614: }
1615: $this->right = $left1;
1616: if ($this->right != NULL) {
1617: $this->right->parent = $this;
1618: $this->right->parentLeft = FALSE;
1619: }
1620: }
avlinsert は、二分探索目における insert を同じ処理を行い、そのノードの下に要素を追加する。
続いて、depth メソッドを用いて左右の深さを比較し、1以上あれば、メソッド rotateRight または rotateLeft を実行する。
1626: class pahooAVLtree extends pahooBStree { //AVL木
1627:
1628: /**
1629: * 要素を1つ挿入する（AVL木向け）
1630: * @param mixed $key 格納するキー
1631: * @param mixed $item 格納する要素
1632: * @param pahooAVLtree $node探索開始ノード（省略時は呼び出したノードから）
1633: * @param function $cmp($a, $b) 要素の大小比較関数（省略可能）
1634: * $a > $bならTRUEを返す
1635: * @returnなし
1636: */
1637: function avlinsert($key, $item, $node=NULL, $cmp=NULL) {
1638: if ($node == NULL) $node = $this;
1639:
1640: //普通に要素を追加
1641: //大きい場合（右側へ）
1642: if ((($cmp != NULL) && $cmp($node->key, $key)) || ($node->key > $key)) {
1643: if ($node->left == NULL) {
1644: $node->left = new pahooAVLtree($key, $item, $node, TRUE);
1645: } else {
1646: $node->avlinsert($key, $item, $node->left, $cmp);
1647: }
1648: //小さい場合（左側へ）
1649: } else {
1650: if ($node->right == NULL) {
1651: $node->right = new pahooAVLtree($key, $item, $node, FALSE);
1652: } else {
1653: $node->avlinsert($key, $item, $node->right, $cmp);
1654: }
1655: }
1656:
1657: //平衡させる
1658: $a = $node->depth();
1659: if ($node->parent != NULL) {
1660: if ($node->parentLeft) {
1661: $b = ($node->parent->right != NULL) ? $node->parent->right->depth() : 0;
1662: if ($a - $b >= 1) $node->rotateRight();
1663: } else {
1664: $b = ($node->parent->left != NULL) ? $node->parent->left->depth() : 0;
1665: if ($a - $b >= 1) $node->rotateLeft();
1666: }
1667: }
1668: }
1669:
1670: // End of Class
1671: }
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;
0050:
0051: /*
0052: ** バージョンアップ履歴 ===================================================
0053: *
0054: * @version 1.0 2018/07/24
0055: */
0056: ?>
0057:
これらは、小さい順に並べた配列 $worst を、関数 shuffle にランダムに並べた配列 $rand の2種類を用意する。
それぞれを、pahooBStree に挿入した場合と、pahooAVLtree に挿入した場合とで、ツリー全体の深さを表示する。
まず、二分探索木 pahooBStree では、小さい順に並んだキーを挿入する場合が最悪のケースで、ツリーの深さは要素の数と同じになってしまう。一方、ランダム並びの方は、比較的深くならずに済んでいる。
PythonによるAVL木
0434: """
0435: * ツリーの深さを取得する
0436: * @param pahooBStree $node 探索開始ノード（省略時は呼び出したノードから）
0437: * @param int $depth 現在の深さ（省略時は0）
0438: * @return intツリーの深さ
0439: """
0440: def depth(self, node=None, depth=0):
0441: if (node == None):
0442: node = self
0443: #左側
0444: left = depth
0445: if (node.left != None):
0446: left = node.depth(node.left, depth + 1)
0447: #右側
0448: right = depth
0449: if (node.right != None):
0450: right = node.depth(node.right, depth + 1)
0451:
0452: if (left > depth):
0453: depth = left
0454: if (right > depth):
0455: depth = right
0456:
0457: return depth
0458:
0459: """
0460: * 右回転
0461: * @paramなし
0462: * @returnなし
0463: """
0464: def rotateRight(self):
0465: key = self.key
0466: item = self.item
0467: left = self.left
0468: right1 = self.right
0469: right2 = self.parent.right
0470: self.key = self.parent.key
0471: self.item = self.parent.item
0472:
0473: self.parent.key = key
0474: self.parent.item = item
0475: self.parent.left = left
0476: if (self.parent.left != None):
0477: self.parent.left.parent = self.parent
0478: self.parent.left.parentLeft = True
0479: self.parent.right = self
0480: self.parentLeft = False
0481:
0482: self.left = right1
0483: if (self.left != None):
0484: self.left.parent = self
0485: self.left.parentLeft = True
0486: self.right = right2
0487: if (self.right != None):
0488: self.right.parent = self
0489: self.right.parentLeft = False
0490:
0491: """
0492: * 左回転
0493: * @paramなし
0494: * @returnなし
0495: """
0496: def rotateLeft(self):
0497: key = self.key
0498: item = self.item
0499: right = self.right
0500: left1 = self.left
0501: left2 = self.parent.left
0502: self.key = self.parent.key
0503: self.item = self.parent.item
0504:
0505: self.parent.key = key
0506: self.parent.item = item
0507: self.parent.right = right
0508: if (self.parent.right != None):
0509: self.parent.right.parent = self.parent
0510: self.parent.right.parentLeft = False
0511: self.parent.left = self
0512: self.parentLeft = True
0513:
0514: self.left = left2
0515: if (self.left != None):
0516: self.left.parent = self
0517: self.left.parentLeft = True
0518: self.right = left1
0519: if (self.right != None):
0520: self.right.parent = self
0521: self.right.parentLeft = False
avlinsert は、二分探索目における insert を同じ処理を行い、そのノードの下に要素を追加する。
続いて、depth メソッドを用いて左右の深さを比較し、1以上あれば、メソッド rotateRight または rotateLeft を実行する。
0524: class pahooAVLtree(pahooBStree): #AVL木
0525: """
0526: * 要素を1つ挿入する（AVL木向け）
0527: * @param mixed $key 格納するキー
0528: * @param mixed $item 格納する要素
0529: * @param pahooAVLtree $node探索開始ノード（省略時は呼び出したノードから）
0530: * @param function $cmp($a, $b) 要素の大小比較関数（省略可能）
0531: * $a > $bならTRUEを返す
0532: * @returnなし
0533: """
0534: def avlinsert(self, key, item, node=None, cmp=None):
0535: if (node == None):
0536: node = self
0537:
0538: #ノードがない場合
0539: if (node.key == None):
0540: node.key = key
0541: node.item = item
0542:
0543: #大きい場合（右側へ）
0544: elif (((cmp != None) and eval(cmp)(node.key, key)) or (node.key > key)):
0545: if (node.left == None):
0546: node.left = pahooAVLtree(key, item, node, True)
0547: else:
0548: self.avlinsert(key, item, node.left, cmp)
0549:
0550: #小さい場合（左側へ）
0551: else:
0552: if (node.right == None):
0553: node.right = pahooAVLtree(key, item, node, False);
0554: else:
0555: self.avlinsert(key, item, node.right, cmp)
0556:
0557: #平衡させる
0558: a = node.depth()
0559: if (node.parent != None):
0560: if (node.parentLeft):
0561: b = node.parent.right.depth() if (node.parent.right != None) else 0
0562: if (a - b >= 1):
0563: node.rotateRight()
0564: else:
0565: b = node.parent.left.depth() if (node.parent.left != None) else 0
0566: if (a - b >= 1):
0567: node.rotateLeft()
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);
探索効率が低下しないよう左右のバランスをとった二分探索木のことを平衡木と呼び、とくに AVL木は理想的なバランスを実現できる。
今回は、PHPとPythonのためのAVL木クラスを用意する。