二分木

PHP アルゴリズム

BTreeを書いた．集合型ということで．
setと最小値を取り出すminpopのみサポート．木のバランスが崩れたときの再構築とかは考えていない．

<?php
// BTree.php

// set
class BTree
{
    public $num = null;
    public $left = null;
    public $right = null;

    public function set($x)
    {
        if ($this->num === null) {
            $this->num = $x;
        }
        else {
            if ($this->num > $x) {
                $call = "left";
            }
            else if ($this->num < $x) {
                $call = "right";
            }
            else {
                return ;
            }

            if ($this->{$call} === null) {
                $this->{$call} = new BTree();
            }
            $this->{$call}->set($x);
        }
    }

    public function minpop()
    {
        $tmp_num = 0;

        if ($this->left !== null) {
            $tmp_num = $this->left->minpop();
            if ($this->left->num == null) { // if right hand is nothing
                $this->left = null;
            }
        }
        else {
            $tmp_num = $this->num;
            if ($tmp_num === null) {
                throw new Exception("Set is empty!");
            }

            if ($this->right !== null) {
                $this->num = $this->right->num;
                $this->left = $this->right->left;
                $this->right = $this->right->right;
            }
            else {
                $this->num = null;
            }
        }

        return $tmp_num;
    }
}


function output_btree(&$t, $debug = false)
{
    if ($t->left !== null) {
        if ($debug) echo "\tleft: ";
        output_btree($t->left);
    }
    echo (($debug)?"\t":"") , $t->num , ", ", (($debug)?"\n":"");
    if ($t->right !== null) {
        if ($debug) echo "\tright: ";
        output_btree($t->right);
    }
}

<?php
// test.init.php

require_once 'BTree.php';

$hoge = new BTree();
$hoge->set(5);
$hoge->set(7);
$hoge->set(2);
$hoge->set(10);
$hoge->set(1);
$hoge->set(8);
//var_dump($hoge);

echo "\ninit!\n"; output_btree($hoge, true);

echo "\npop!\n\t"; var_dump($hoge->minpop()); echo "output!\n"; output_btree($hoge) ."\n";
echo "\npop!\n\t"; var_dump($hoge->minpop()); echo "output!\n"; output_btree($hoge) ."\n";
echo "\npop!\n\t"; var_dump($hoge->minpop()); echo "output!\n"; output_btree($hoge) ."\n";

echo "SET:\t" , 1, "\n"; $hoge->set(1); echo "output!\n"; output_btree($hoge);
echo "\npop!\n\t"; var_dump($hoge->minpop()); echo "output!\n"; output_btree($hoge);
echo "\npop!\n\t"; var_dump($hoge->minpop()); echo "output!\n"; output_btree($hoge);

% php test.init.php

init!
        left: 1, 2,     5,
        right: 7, 8, 10,
pop!
        int(1)
output!
2, 5, 7, 8, 10,
pop!
        int(2)
output!
5, 7, 8, 10,
pop!
        int(5)
output!
7, 8, 10, SET:  1
output!
1, 7, 8, 10,
pop!
        int(1)
output!
7, 8, 10,
pop!
        int(7)
output!
8, 10, 
<?php
// test.rand.php

require_once 'BTree.php';

$set = new BTree();

foreach (range(0, 1000) as $s) {
    $set->set(mt_rand(0, 10000));
}

echo "initialized:\n";
output_btree($set); echo "\n";
echo "pop:\n";
var_dump($set->minpop());
echo "popped:\n";
output_btree($set); echo "\n";

% php test.rand.php
initialized:
17, 19, 27, 45, 55, 90, 92, 97, 102, 111, 112, 114, 118, 119, 126, 145, 195, 216, 220, 223, 231, 232, 233, 237, 265, 271, 276, 282, 289, 293, 301, 313, 315, 355, 357, 368, 369, 373, 379, 388, 392, 394, 399, 410, 413, 431, 433, 437, 449, 454, 457, 462, 470, 472, 480, 482, 492, 500, 502, 519, 534, 545, 547, 568, 575, 597, 620, 621, 634, 647, 650, 655, 670, 675, 677, 696, 698, 709, 710, 728, 736, 750, 751, 760, 768, 774, 784, 818, 823, 829, 845, 849, 861, 865, 916, 917, 921, 952, 966, 984, 987, 989, 998, 999, 1006, 1007, 1011, 1019, 1028, 1058, 1084, 1099, 1107, 1112, 1121, 1131, 1144, 1145, 1151, 1158, 1160, 1171, 1176, 1177,1181, 1198, 1201, 1203, 1211, 1216, 1222, 1227, 1236, 1276, 1310, 1311, 1312, 1314, 1316, 1329, 1332, 1339, 1341, 1348, 1354, 1359, 1362, 1380, 1395, 1400, 1402, 1407, 1417, 1420, 1426, 1447, 1464, 1481, 1489, 1490, 1497, 1514, 1515, 1521, 1526, 1528, 1533, 1538, 1551, 1553, 1558, 1564, 1583, 1598, 1605, 1607, 1613, 1614, 1618, 1634, 1636, 1642, 1662, 1670, 1675, 1689, 1691, 1698, 1709, 1719, 1742, 1747, 1756, 1758, 1768, 1774, 1778, 1794, 1796, 1813, 1822, 1832, 1839, 1843, 1846, 1853, 1865, 1873, 1879, 1892, 1894, 1899, 1918, 1920, 1923, 1924, 1925, 1927, 1945, 1957, 1958, 1961, 1966, 1983, 2001, 2004, 2011, 2016, 2017, 2026, 2038, 2042, 2051, 2071, 2079, 2080, 2116, 2122, 2128, 2131, 2135, 2147, 2162, 2168, 2173, 2182, 2185, 2205, 2218, 2283, 2287, 2349, 2365, 2374, 2375, 2383, 2395, 2408, 2418, 2419, 2423, 2425, 2428, 2437, 2439, 2444, 2460, 2485, 2489, 2491, 2492, 2496, 2497, 2499, 2505, 2508, 2514, 2539, 2564, 2572, 2573, 2577, 2607, 2628, 2637, 2642, 2645, 2679, 2681, 2686, 2689, 2695, 2698, 2704, 2735, 2738, 2760, 2766, 2773, 2786, 2792, 2793, 2794, 2804, 2820, 2821, 2832, 2834, 28
35, 2840, 2855, 2865, 2866, 2877, 2882, 2893, 2903, 2951, 2966, 2975, 2988, 3010, 3031, 3036, 3037, 3043, 3060, 3066, 3072, 3073, 3077, 3115, 3120, 3125, 3128, 3150, 3157, 3159, 3181, 3199, 3205, 3222, 3245, 3249, 3258, 3263, 3269, 3294, 3302, 3304, 3344, 3362, 3368, 3374, 3392, 3395, 3406, 3424, 3432, 3435, 3439, 3440, 3443, 3446, 3457, 3476, 3484, 3492, 3493, 3510, 3513, 3519, 3524, 3552, 3553, 3555, 3565, 3578, 3595, 3601, 3650, 3674, 3686, 3694, 3702, 3704, 3708, 3728, 3731, 3740, 3757, 3781, 3806, 3808, 3823, 3824, 3830, 3841, 3852, 3854, 3888, 3892, 3899, 3903, 3904, 3908, 3916, 3950, 3985, 3995, 4001, 4006, 4009, 4033, 4041, 4058, 4076, 4080, 4088, 4102, 4130, 4131, 4135, 4148, 4158, 4165, 4174, 4177, 4190, 4193, 4210, 4212, 4219, 4226, 4260, 4262, 4264, 4270, 4274, 4281, 4285, 4294, 4330, 4337, 4363, 4364, 4369, 4382, 4386, 4432, 4441, 4462, 4470, 4471, 4478, 4481, 4499, 4508, 4518, 4548, 4559, 4561, 4566, 4573, 4577, 4593, 4607, 4636, 4638, 4641, 4642, 4646, 4659, 4660, 4675, 4679, 4691, 4706, 4709, 4735, 4754, 4771, 4773, 4775, 4792, 4802, 4806, 4813, 4819, 4821, 4822, 4837, 4844, 4849, 4852, 4874, 4885, 4908, 4909, 4923, 4933, 4934, 4946, 4962, 4969, 5007, 5009, 5010, 5087, 5088, 5107, 5117, 5119, 5126, 5147, 5148, 5149, 5173, 5177, 5178, 5181, 5199, 5208, 5212, 5239, 5252, 5263, 5293, 5301, 5305, 5310, 5313, 5321, 5322, 5330, 5365, 5374, 5381, 5383, 5408, 5430, 5447, 5451, 5452, 5456, 5459, 5469, 5471, 5477, 5490, 5495, 5503, 5529, 5542, 5550, 5551, 5564, 5577, 5610, 5612, 5627, 5657, 5660, 5698, 5714, 5722, 5731, 5734, 5743, 5745, 5746, 5770, 5787, 5788, 5806, 5812, 5813, 5821, 5830, 5846, 5849, 5888, 5892, 5912, 5925, 5944, 5945, 5953, 5959, 5963, 5982, 6012, 6018, 6019, 6021, 6047, 6054, 6090, 6099, 6111, 6123, 6143, 6147, 6149, 6180, 6193, 6199, 6212, 6223, 6265, 6268, 6277, 6306, 6310, 6321, 6327, 6334, 6337, 6348, 6351, 6352, 6358, 6379, 6389, 6395, 6404, 6405, 6411, 6417, 6427, 6431, 6435, 6439, 6459, 6470, 6484, 6486, 6497, 6521, 6549, 6554, 6559, 6570, 6587, 6593, 6603, 6617, 6625, 6634, 6635, 6653, 6655, 6657, 6666, 6693, 6707, 6708, 6734, 6736, 6741, 6742, 6773, 6775, 6786, 6794, 6818, 6822, 6840, 6849, 6894, 6895, 6905, 6911, 6915, 6941, 6970, 6993, 7006, 7008, 7017, 7029, 7031, 7039, 7054, 7056, 7065, 7079, 7084, 7146, 7149, 7150, 7154, 7159, 7183, 7187, 7203, 7211, 7213, 7249, 7255, 7268, 7279, 7325, 7342, 7353, 7367, 7402, 7428, 7431, 7436, 7440, 7458, 7461, 7470, 7480, 7507, 7522, 7539, 7546, 7547, 7548, 7551, 7571, 7572, 7582, 7595, 7603, 7623, 7652, 7663, 7672, 7689, 7692, 7701, 7707, 7730, 7743, 7750, 7754, 7759, 7772, 7775, 7790, 7802, 7807, 7809, 7812, 7834, 7837, 7851, 7862, 7863, 7867, 7879, 7885, 7886, 7888, 7890, 7897, 7915, 7927, 7947, 7956, 7958, 7962, 7966, 7968, 7971, 7976, 7984, 8020, 8039, 8045, 8056, 8064, 8076, 8103, 8109, 8125, 8149, 8157, 8179, 8203, 8224, 8261, 8263, 8264, 8265, 8268, 8279, 8285, 8291, 8295, 8310, 8330, 8353, 8355, 8364, 8388, 8400, 8413, 8434, 8443, 8456, 8461, 8465, 8466, 8474, 8480, 8517, 8537, 8569, 8573, 8576, 8582, 8585, 8588, 8627, 8636, 8670, 8684, 8734, 8735, 8743, 8745, 8752, 8764, 8774, 8775, 8776, 8783, 8794, 8802, 8805, 8820, 8821, 8859, 8866, 8868, 8869, 8874, 8880, 8882, 8883, 8887, 8892, 8904, 8911, 8912, 8929, 8945, 8977, 8981, 8985, 9009, 9011, 9017, 9026, 9040, 9044, 9055, 9072, 9082, 9091, 9096, 9100, 9126, 9128, 9130, 9136, 9142, 9145, 9146, 9151, 9157, 9159, 9162, 9174, 9193, 9225, 9226, 9239, 9246, 9251, 9265, 9275, 9279, 9291, 9300, 9318, 9328, 9332, 9346, 9358, 9361, 9366, 9371, 9377, 9379, 9389, 9390, 9411, 9423, 9425, 9428, 9431, 9459, 9463, 9472, 9482, 9483, 9488, 9502, 9504, 9506, 9512, 9522, 9535, 9552, 9568, 9574, 9614, 9617, 9622, 9626, 9628, 9652, 9657, 9666, 9715, 9718, 9736, 9739, 9745, 9752, 9753, 9757, 9777, 9788, 9789, 9791, 9816, 9832, 9840, 9843, 9848, 9856, 9873, 9879, 9890, 9906, 9909, 9918, 9951, 9954, 9955, 9957, 9960, 9980, 9986, 10000,
pop:
int(17)
popped:
19, 27, 45, 55, 90, 92, 97, 102, 111, 112, 114, 118, 119, 126, 145, 195, 216, 220, 223, 231, 232, 233, 237, 265, 271, 276, 282, 289, 293, 301, 313, 315, 355, 357, 368, 369, 373, 379, 388, 392, 394, 399, 410, 413, 431, 433, 437, 449, 454, 457, 462, 470, 472, 480, 482, 492, 500, 502, 519, 534, 545, 547, 568, 575, 597, 620, 621, 634, 647, 650, 655, 670, 675, 677, 696, 698, 709, 710, 728, 736, 750, 751, 760, 768, 774, 784, 818, 823, 829, 845, 849, 861, 865, 916, 917, 921, 952, 966, 984, 987, 989, 998, 999, 1006, 1007, 1011, 1019, 1028, 1058, 1084, 1099, 1107, 1112, 1121, 1131, 1144, 1145, 1151, 1158, 1160, 1171, 1176, 1177, 1181, 1198, 1201, 1203, 1211, 1216, 1222, 1227, 1236, 1276, 1310, 1311, 1312, 1314, 1316, 1329, 1332, 1339, 1341, 1348, 1354, 1359, 1362, 1380, 1395, 1400, 1402, 1407, 1417, 1420, 1426, 1447, 1464, 1481, 1489, 1490, 1497, 1514, 1515, 1521, 1526, 1528, 1533, 1538, 1551, 1553, 1558, 1564, 1583, 1598, 1605, 1607, 1613, 1614, 1618, 1634, 1636, 1642, 1662, 1670, 1675, 1689, 1691, 1698, 1709, 1719, 1742, 1747, 1756, 1758, 1768, 1774, 1778, 1794, 1796, 1813, 1822, 1832, 1839, 1843, 1846, 1853, 1865, 1873, 1879, 1892, 1894, 1899, 1918, 1920, 1923, 1924, 1925, 1927, 1945, 1957, 1958, 1961, 1966, 1983, 2001, 2004, 2011, 2016, 2017, 2026, 2038, 2042, 2051, 2071, 2079, 2080, 2116, 2122, 2128, 2131, 2135, 2147, 2162, 2168, 2173, 2182, 2185, 2205, 2218, 2283, 2287, 2349, 2365, 2374, 2375, 2383, 2395, 2408, 2418, 2419, 2423, 2425, 2428, 2437, 2439, 2444, 2460, 2485, 2489, 2491, 2492, 2496, 2497, 2499, 2505, 2508, 2514, 2539, 2564, 2572, 2573, 2577, 2607, 2628, 2637, 2642, 2645, 2679, 2681, 2686, 2689, 2695, 2698, 2704, 2735, 2738, 2760, 2766, 2773, 2786, 2792, 2793, 2794, 2804, 2820, 2821, 2832, 2834, 2835, 2840, 2855, 2865, 2866, 2877, 2882, 2893, 2903, 2951, 2966, 2975, 2988, 3010, 3031, 3036, 3037, 3043, 3060, 3066, 3072, 3073, 3077, 3115, 3120, 3125, 3128, 3150, 3157, 3159, 3181, 3199, 3205, 3222, 3245, 3249, 3258, 3263, 3269, 3294, 3302, 3304, 3344, 3362, 3368, 3374, 3392, 3395, 3406, 3424, 3432, 3435, 3439, 3440, 3443, 3446, 3457, 3476, 3484, 3492, 3493, 3510, 3513, 3519, 3524, 3552, 3553, 3555, 3565, 3578, 3595, 3601, 3650, 3674, 3686, 3694, 3702, 3704, 3708, 3728, 3731, 3740, 3757, 3781, 3806, 3808, 3823, 3824, 3830, 3841, 3852, 3854, 3888, 3892, 3899, 3903, 3904, 3908, 3916, 3950, 3985, 3995, 4001, 4006, 4009, 4033, 4041, 4058, 4076, 4080, 4088, 4102, 4130, 4131, 4135, 4148, 4158, 4165, 4174, 4177, 4190, 4193, 4210, 4212, 4219, 4226, 4260, 4262, 4264, 4270, 4274, 4281, 4285, 4294, 4330, 4337, 4363, 4364, 4369, 4382, 4386, 4432, 4441, 4462, 4470, 4471, 4478, 4481, 4499, 4508, 4518, 4548, 4559, 4561, 4566, 4573, 4577, 4593, 4607, 4636, 4638, 4641, 4642, 4646, 4659, 4660, 4675, 4679, 4691, 4706, 4709, 4735, 4754, 4771, 4773, 4775, 4792, 4802, 4806, 4813, 4819, 4821, 4822, 4837, 4844, 4849, 4852, 4874, 4885, 4908, 4909, 4923, 4933, 4934, 4946, 4962, 4969, 5007, 5009, 5010, 5087, 5088, 5107, 5117, 5119, 5126, 5147, 5148, 5149, 5173, 5177, 5178, 5181, 5199, 5208, 5212, 5239, 5252, 5263, 5293, 5301, 5305, 5310, 5313, 5321, 5322, 5330, 5365, 5374, 5381, 5383, 5408, 5430, 5447, 5451, 5452, 5456, 5459, 5469, 5471, 5477, 5490, 5495, 5503, 5529, 5542, 5550, 5551, 5564, 5577, 5610, 5612, 5627, 5657, 5660, 5698, 5714, 5722, 5731, 5734, 5743, 5745, 5746, 5770, 5787, 5788, 5806, 5812, 5813, 5821, 5830, 5846, 5849, 5888, 5892, 5912, 5925, 5944, 5945, 5953, 5959, 5963, 5982, 6012, 6018, 6019, 6021, 6047, 6054, 6090, 6099, 6111, 6123, 6143, 6147, 6149, 6180, 6193, 6199, 6212, 6223, 6265, 6268, 6277, 6306, 6310, 6321, 6327, 6334, 6337, 6348, 6351, 6352, 6358, 6379, 6389, 6395, 6404, 6405, 6411, 6417, 6427, 6431, 6435, 6439, 6459, 6470, 6484, 6486, 6497, 6521, 6549, 6554, 6559, 6570, 6587, 6593, 6603, 6617, 6625, 6634, 6635, 6653, 6655, 6657, 6666, 6693, 6707, 6708, 6734, 6736, 6741, 6742, 6773, 6775, 6786, 6794, 6818, 6822, 6840, 6849, 6894, 6895, 6905, 6911, 6915, 6941, 6970, 6993, 7006, 7008, 7017, 7029, 7031, 7039, 7054, 7056, 7065, 7079, 7084, 7146, 7149, 7150, 7154, 7159, 7183, 7187, 7203, 7211, 7213, 7249, 7255, 7268, 7279, 7325, 7342, 7353, 7367, 7402, 7428, 7431, 7436, 7440, 7458, 7461, 7470, 7480, 7507, 7522, 7539, 7546, 7547, 7548, 7551, 7571, 7572, 7582, 7595, 7603, 7623, 7652, 7663, 7672, 7689, 7692, 7701, 7707, 7730, 7743, 7750, 7754, 7759, 7772, 7775, 7790, 7802, 7807, 7809, 7812, 7834, 7837, 7851, 7862, 7863, 7867, 7879, 7885, 7886, 7888, 7890, 7897, 7915, 7927, 7947, 7956, 7958, 7962, 7966, 7968, 7971, 7976, 7984, 8020, 8039, 8045, 8056, 8064, 8076, 8103, 8109, 8125, 8149, 8157, 8179, 8203, 8224, 8261, 8263, 8264, 8265, 8268, 8279, 8285, 8291, 8295, 8310, 8330, 8353, 8355, 8364, 8388, 8400, 8413, 8434, 8443, 8456, 8461, 8465, 8466, 8474, 8480, 8517, 8537, 8569, 8573, 8576, 8582, 8585, 8588, 8627, 8636, 8670, 8684, 8734, 8735, 8743, 8745, 8752, 8764, 8774, 8775, 8776, 8783, 8794, 8802, 8805, 8820, 8821, 8859, 8866, 8868, 8869, 8874, 8880, 8882, 8883, 8887, 8892, 8904, 8911, 8912, 8929, 8945, 8977, 8981, 8985, 9009, 9011, 9017, 9026, 9040, 9044, 9055, 9072, 9082, 9091, 9096, 9100, 9126, 9128, 9130, 9136, 9142, 9145, 9146, 9151, 9157, 9159, 9162, 9174, 9193, 9225, 9226, 9239, 9246, 9251, 9265, 9275, 9279, 9291, 9300, 9318, 9328, 9332, 9346, 9358, 9361, 9366, 9371, 9377, 9379, 9389, 9390, 9411, 9423, 9425, 9428, 9431, 9459, 9463, 9472, 9482, 9483, 9488, 9502, 9504, 9506, 9512, 9522, 9535, 9552, 9568, 9574, 9614, 9617, 9622, 9626, 9628, 9652, 9657, 9666, 9715, 9718, 9736, 9739, 9745, 9752, 9753, 9757, 9777, 9788, 9789, 9791, 9816, 9832, 9840, 9843, 9848, 9856, 9873, 9879, 9890, 9906, 9909, 9918, 9951, 9954, 9955, 9957, 9960, 9980, 9986, 10000,