数据结构笔记总结(5.11)删除二分搜索树的最大元素和最小元素

二分搜索树的最小值和最大值

首先要寻找二分搜索树的最小值和最大值,对于二分搜索树来说,每一个节点左子树的值都小于这个节点的值,所以在二分搜索树中相应最小值一定是从根节点开始不停的向左走直到走不动为止,那个值一定就是最小值。

在图中就是13,最大值同理,在图中就是42。

代码演示

寻找二分搜素树中最小和最大元素

// 寻找二分搜索树的最小元素
public E minimum(){
    if(size == 0)
        throw new IllegalArgumentException("BST is empty");

    Node minNode = minimum(root);
    return minNode.e;
}

// 返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node){
    if( node.left == null )
        return node;

    return minimum(node.left);
}

// 寻找二分搜索树的最大元素
public E maximum(){
    if(size == 0)
        throw new IllegalArgumentException("BST is empty");

    return maximum(root).e;
}

// 返回以node为根的二分搜索树的最大值所在的节点
private Node maximum(Node node){
    if( node.right == null )
        return node;

    return maximum(node.right);
}

删除二分搜索树的最小值

首先我们要删除图中的最小值,其实就是左子树的叶子节点13,删除13,不需要改变任何结构,同理删除13之后的二分搜素树最小值是15,直接删掉就好了。

此时就要注意了,此时二分搜素树最小值是22,但是它有右子树,这种情况下该怎么办呢?

其实也很简单,只需将22这个节点删除,然后将它的整个右子树都变成41的左子树就完成了删除操作。

删除最大值也同理!

代码演示

// 从二分搜索树中删除最小值所在节点, 返回最小值
public E removeMin(){
    E ret = minimum();
    root = removeMin(root);
    return ret;
}

// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private Node removeMin(Node node){

    if(node.left == null){
        Node rightNode = node.right;
        node.right = null;
        size --;
        return rightNode;
    }

    node.left = removeMin(node.left);
    return node;
}

// 从二分搜索树中删除最大值所在节点
public E removeMax(){
    E ret = maximum();
    root = removeMax(root);
    return ret;
}

// 删除掉以node为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
private Node removeMax(Node node){

    if(node.right == null){
        Node leftNode = node.left;
        node.left = null;
        size --;
        return leftNode;
    }

    node.right = removeMax(node.right);
    return node;
}

测试用例

最后简单测试一下我们编写的删除二分搜索树的最大元素和最小元素代码

import java.util.ArrayList;
import java.util.Random;

public class Main {

    public static void main(String[] args) {

        BST bst = new BST<>();
        Random random = new Random();

        int n = 1000;

        // test removeMin
        for(int i = 0 ; i < n ; i ++)
            bst.add(random.nextInt(10000));

        ArrayList nums = new ArrayList<>();
        while(!bst.isEmpty())
            nums.add(bst.removeMin());

        System.out.println(nums);
        for(int i = 1 ; i < nums.size() ; i ++)
            if(nums.get(i - 1) > nums.get(i))
                throw new IllegalArgumentException("Error!");
        System.out.println("removeMin test completed.");


        // test removeMax
        for(int i = 0 ; i < n ; i ++)
            bst.add(random.nextInt(10000));

        nums = new ArrayList<>();
        while(!bst.isEmpty())
            nums.add(bst.removeMax());

        System.out.println(nums);
        for(int i = 1 ; i < nums.size() ; i ++)
            if(nums.get(i - 1) < nums.get(i))
                throw new IllegalArgumentException("Error!");
        System.out.println("removeMax test completed.");
    }
}

运行结果如下

[2, 11, 72, 75, 83, 89, 97, 99, 105, 114, 117, 125, 126, 131, 162, 166, 184, 192, 204, 218, 226, 251, 253, 279, 285, 292, 299, 302, 327, 328, 330, 337, 346, 354, 355, 389, 402, 421, 424, 442, 444, 454, 459, 468, 484, 504, 505, 509, 523, 559, 585, 588, 590, 595, 614, 615, 624, 646, 658, 661, 693, 694, 698, 713, 715, 718, 726, 733, 741, 746, 756, 759, 761, 764, 766, 769, 800, 834, 844, 850, 851, 853, 875, 876, 880, 901, 902, 909, 912, 914, 917, 923, 926, 927, 932, 945, 947, 951, 955, 961, 971, 982, 1000, 1007, 1016, 1019, 1036, 1078, 1079, 1099, 1101, 1103, 1106, 1110, 1121, 1164, 1208, 1227, 1246, 1260, 1274, 1289, 1292, 1296, 1302, 1318, 1324, 1336, 1348, 1400, 1401, 1418, 1420, 1443, 1447, 1462, 1482, 1490, 1508, 1528, 1536, 1548, 1558, 1562, 1571, 1574, 1584, 1588, 1593, 1594, 1596, 1613, 1620, 1621, 1622, 1639, 1645, 1652, 1659, 1660, 1675, 1682, 1686, 1692, 1701, 1704, 1719, 1727, 1732, 1741, 1776, 1782, 1787, 1797, 1804, 1806, 1816, 1826, 1827, 1833, 1839, 1859, 1882, 1884, 1895, 1914, 1915, 1917, 1927, 1939, 1950, 1952, 1973, 1974, 2021, 2029, 2031, 2035, 2053, 2063, 2080, 2088, 2109, 2111, 2168, 2183, 2213, 2221, 2224, 2225, 2239, 2260, 2264, 2269, 2275, 2283, 2284, 2298, 2302, 2330, 2354, 2362, 2367, 2378, 2387, 2391, 2397, 2414, 2416, 2421, 2441, 2452, 2455, 2462, 2466, 2468, 2490, 2492, 2505, 2509, 2510, 2528, 2547, 2562, 2576, 2601, 2618, 2627, 2629, 2630, 2632, 2645, 2656, 2679, 2681, 2687, 2694, 2712, 2717, 2743, 2752, 2787, 2801, 2805, 2881, 2886, 2890, 2899, 2919, 2926, 2931, 2939, 2940, 2946, 2948, 2958, 2966, 2981, 2982, 2988, 3021, 3022, 3062, 3080, 3084, 3085, 3107, 3111, 3115, 3126, 3139, 3142, 3147, 3148, 3151, 3165, 3171, 3177, 3195, 3201, 3207, 3230, 3233, 3234, 3236, 3268, 3272, 3280, 3283, 3293, 3301, 3312, 3328, 3329, 3338, 3351, 3352, 3376, 3384, 3391, 3412, 3422, 3432, 3441, 3444, 3458, 3468, 3493, 3497, 3510, 3517, 3527, 3541, 3546, 3554, 3555, 3569, 3574, 3592, 3594, 3605, 3612, 3614, 3620, 3624, 3627, 3716, 3727, 3743, 3744, 3746, 3749, 3750, 3761, 3767, 3771, 3783, 3796, 3804, 3840, 3853, 3855, 3864, 3873, 3881, 3888, 3890, 3904, 3937, 3945, 3948, 3949, 3957, 3963, 3964, 3977, 3985, 3991, 3995, 4016, 4034, 4058, 4070, 4082, 4084, 4104, 4108, 4124, 4128, 4170, 4171, 4182, 4189, 4206, 4207, 4210, 4217, 4218, 4225, 4226, 4263, 4276, 4287, 4288, 4293, 4305, 4340, 4355, 4369, 4372, 4373, 4376, 4377, 4385, 4391, 4394, 4395, 4397, 4402, 4409, 4420, 4425, 4428, 4429, 4439, 4447, 4452, 4466, 4479, 4493, 4502, 4521, 4530, 4541, 4547, 4550, 4580, 4582, 4592, 4612, 4615, 4616, 4625, 4629, 4630, 4634, 4644, 4655, 4658, 4674, 4675, 4677, 4679, 4692, 4696, 4738, 4741, 4750, 4767, 4768, 4775, 4777, 4804, 4814, 4816, 4824, 4834, 4852, 4873, 4941, 4942, 4953, 4957, 4960, 4966, 4987, 4989, 4999, 5008, 5017, 5023, 5032, 5038, 5047, 5055, 5084, 5094, 5097, 5126, 5128, 5158, 5162, 5173, 5174, 5177, 5183, 5206, 5212, 5225, 5233, 5245, 5247, 5276, 5282, 5283, 5285, 5324, 5332, 5338, 5355, 5357, 5377, 5381, 5409, 5415, 5418, 5448, 5453, 5457, 5458, 5495, 5504, 5538, 5552, 5560, 5578, 5579, 5594, 5596, 5601, 5609, 5613, 5637, 5643, 5644, 5652, 5655, 5656, 5657, 5674, 5677, 5691, 5699, 5701, 5713, 5716, 5723, 5724, 5731, 5736, 5741, 5749, 5750, 5758, 5769, 5778, 5779, 5782, 5783, 5788, 5789, 5790, 5823, 5832, 5843, 5862, 5874, 5889, 5892, 5907, 5949, 5952, 5963, 5972, 5975, 5977, 5979, 6008, 6017, 6042, 6055, 6057, 6067, 6075, 6077, 6079, 6090, 6120, 6124, 6136, 6152, 6153, 6157, 6170, 6171, 6208, 6218, 6235, 6236, 6237, 6239, 6254, 6259, 6261, 6266, 6279, 6290, 6299, 6328, 6333, 6343, 6354, 6366, 6368, 6371, 6373, 6380, 6385, 6392, 6401, 6403, 6410, 6428, 6436, 6441, 6448, 6467, 6476, 6514, 6520, 6541, 6545, 6548, 6558, 6561, 6566, 6570, 6602, 6616, 6621, 6630, 6633, 6690, 6697, 6710, 6714, 6720, 6732, 6778, 6787, 6793, 6795, 6803, 6807, 6814, 6816, 6831, 6843, 6861, 6880, 6885, 6899, 6908, 6917, 6918, 6924, 6926, 6935, 6938, 6942, 6944, 6950, 6966, 6975, 7014, 7020, 7038, 7056, 7075, 7077, 7086, 7114, 7130, 7155, 7166, 7172, 7174, 7206, 7223, 7239, 7251, 7277, 7285, 7295, 7297, 7298, 7308, 7309, 7311, 7327, 7338, 7348, 7349, 7418, 7433, 7437, 7445, 7467, 7468, 7521, 7522, 7529, 7543, 7548, 7557, 7584, 7597, 7601, 7616, 7630, 7641, 7644, 7654, 7669, 7672, 7673, 7697, 7712, 7730, 7734, 7736, 7754, 7760, 7766, 7773, 7784, 7787, 7797, 7814, 7823, 7831, 7833, 7836, 7838, 7852, 7861, 7891, 7913, 7914, 7919, 7921, 7936, 7941, 7963, 7971, 7977, 7980, 8002, 8010, 8013, 8017, 8022, 8028, 8034, 8037, 8042, 8043, 8048, 8055, 8063, 8069, 8088, 8100, 8109, 8110, 8112, 8122, 8124, 8131, 8134, 8143, 8173, 8179, 8187, 8188, 8189, 8197, 8227, 8228, 8235, 8240, 8244, 8254, 8279, 8284, 8289, 8296, 8316, 8321, 8329, 8334, 8338, 8344, 8345, 8349, 8388, 8401, 8429, 8450, 8465, 8471, 8478, 8501, 8519, 8534, 8548, 8574, 8584, 8593, 8599, 8637, 8644, 8653, 8659, 8665, 8673, 8695, 8706, 8724, 8730, 8732, 8751, 8753, 8761, 8771, 8801, 8809, 8813, 8815, 8828, 8830, 8847, 8872, 8878, 8881, 8902, 8917, 8936, 8939, 8940, 8941, 8950, 8952, 8956, 8965, 8968, 8991, 8998, 9006, 9037, 9058, 9071, 9078, 9079, 9089, 9094, 9097, 9099, 9103, 9118, 9145, 9148, 9152, 9163, 9182, 9212, 9227, 9229, 9231, 9233, 9234, 9237, 9247, 9265, 9266, 9290, 9319, 9325, 9329, 9340, 9347, 9351, 9388, 9411, 9427, 9452, 9485, 9514, 9519, 9520, 9524, 9538, 9546, 9549, 9550, 9557, 9559, 9562, 9580, 9594, 9598, 9599, 9602, 9637, 9641, 9652, 9655, 9668, 9674, 9704, 9707, 9787, 9791, 9801, 9811, 9812, 9814, 9827, 9842, 9846, 9848, 9885, 9888, 9890, 9892, 9906, 9914, 9927, 9947, 9956, 9966, 9975, 9977, 9997, 9999]
removeMin test completed.
[9988, 9985, 9983, 9972, 9971, 9935, 9928, 9926, 9919, 9909, 9899, 9884, 9863, 9860, 9855, 9812, 9805, 9802, 9798, 9796, 9793, 9776, 9768, 9765, 9751, 9746, 9733, 9714, 9704, 9677, 9670, 9656, 9645, 9643, 9642, 9638, 9628, 9607, 9605, 9603, 9596, 9558, 9544, 9533, 9528, 9497, 9495, 9478, 9458, 9455, 9444, 9428, 9427, 9425, 9417, 9407, 9402, 9387, 9380, 9359, 9348, 9342, 9329, 9316, 9311, 9304, 9301, 9298, 9293, 9265, 9259, 9254, 9252, 9243, 9241, 9221, 9218, 9204, 9198, 9195, 9185, 9183, 9181, 9163, 9162, 9145, 9134, 9132, 9125, 9110, 9109, 9105, 9098, 9083, 9082, 9080, 9032, 9018, 9002, 8995, 8989, 8954, 8950, 8942, 8939, 8926, 8909, 8905, 8902, 8900, 8897, 8894, 8880, 8867, 8864, 8863, 8842, 8829, 8821, 8816, 8814, 8805, 8788, 8776, 8762, 8760, 8755, 8747, 8742, 8741, 8724, 8718, 8664, 8659, 8656, 8651, 8648, 8634, 8632, 8623, 8617, 8612, 8551, 8549, 8541, 8539, 8531, 8527, 8526, 8520, 8515, 8512, 8504, 8482, 8478, 8466, 8465, 8464, 8450, 8429, 8418, 8399, 8396, 8393, 8392, 8387, 8376, 8373, 8370, 8357, 8349, 8345, 8307, 8293, 8280, 8268, 8257, 8256, 8251, 8235, 8225, 8220, 8218, 8216, 8208, 8195, 8162, 8161, 8130, 8128, 8122, 8109, 8094, 8076, 8072, 8069, 8068, 8063, 8061, 8060, 8055, 8053, 8048, 8035, 8033, 8021, 8014, 7970, 7964, 7947, 7939, 7930, 7928, 7924, 7900, 7898, 7888, 7866, 7860, 7841, 7838, 7814, 7807, 7762, 7747, 7733, 7730, 7723, 7687, 7681, 7641, 7626, 7616, 7612, 7603, 7599, 7593, 7592, 7540, 7538, 7512, 7498, 7494, 7492, 7469, 7457, 7428, 7425, 7414, 7413, 7389, 7384, 7380, 7376, 7346, 7332, 7314, 7296, 7278, 7252, 7250, 7245, 7211, 7194, 7192, 7191, 7186, 7175, 7173, 7172, 7159, 7158, 7156, 7118, 7117, 7115, 7109, 7105, 7104, 7098, 7088, 7085, 7066, 7056, 7053, 7042, 7027, 7016, 7015, 7013, 6997, 6992, 6981, 6955, 6954, 6942, 6941, 6938, 6936, 6929, 6911, 6894, 6885, 6873, 6869, 6827, 6822, 6804, 6802, 6768, 6767, 6754, 6748, 6747, 6740, 6739, 6694, 6692, 6682, 6678, 6670, 6659, 6651, 6648, 6624, 6616, 6612, 6606, 6601, 6593, 6588, 6552, 6543, 6533, 6525, 6522, 6511, 6510, 6494, 6493, 6484, 6483, 6481, 6474, 6469, 6431, 6422, 6420, 6401, 6399, 6375, 6370, 6348, 6341, 6330, 6325, 6324, 6307, 6302, 6301, 6291, 6282, 6273, 6263, 6259, 6252, 6238, 6231, 6224, 6220, 6205, 6199, 6195, 6182, 6154, 6128, 6127, 6119, 6114, 6111, 6095, 6088, 6073, 6068, 6052, 6050, 6030, 6026, 6013, 6006, 5989, 5960, 5948, 5946, 5945, 5933, 5927, 5918, 5893, 5892, 5890, 5882, 5872, 5868, 5855, 5849, 5841, 5832, 5826, 5813, 5785, 5770, 5758, 5755, 5749, 5748, 5742, 5739, 5737, 5736, 5723, 5717, 5708, 5707, 5700, 5686, 5673, 5668, 5662, 5661, 5660, 5659, 5637, 5626, 5618, 5617, 5616, 5612, 5589, 5588, 5585, 5581, 5558, 5552, 5528, 5520, 5493, 5491, 5478, 5462, 5459, 5447, 5418, 5414, 5413, 5408, 5400, 5399, 5396, 5384, 5371, 5362, 5360, 5356, 5351, 5338, 5318, 5276, 5271, 5264, 5245, 5244, 5239, 5221, 5200, 5188, 5175, 5174, 5161, 5159, 5158, 5153, 5146, 5109, 5096, 5079, 5068, 5062, 5037, 5025, 5007, 4998, 4974, 4967, 4961, 4942, 4922, 4919, 4890, 4843, 4826, 4811, 4802, 4800, 4793, 4791, 4763, 4757, 4755, 4732, 4728, 4725, 4687, 4686, 4683, 4632, 4628, 4604, 4572, 4571, 4520, 4517, 4511, 4509, 4503, 4501, 4494, 4492, 4464, 4445, 4442, 4441, 4437, 4425, 4379, 4359, 4358, 4346, 4332, 4305, 4301, 4291, 4280, 4272, 4260, 4257, 4237, 4222, 4217, 4206, 4201, 4189, 4183, 4179, 4172, 4160, 4159, 4144, 4143, 4138, 4130, 4125, 4121, 4114, 4096, 4046, 4017, 4006, 3991, 3982, 3977, 3973, 3946, 3942, 3939, 3932, 3903, 3892, 3891, 3885, 3882, 3881, 3874, 3870, 3856, 3847, 3822, 3808, 3797, 3782, 3755, 3753, 3752, 3727, 3699, 3696, 3695, 3672, 3666, 3654, 3640, 3637, 3619, 3603, 3588, 3587, 3581, 3579, 3577, 3558, 3556, 3554, 3537, 3536, 3507, 3446, 3440, 3434, 3420, 3408, 3405, 3398, 3377, 3365, 3354, 3348, 3346, 3342, 3337, 3320, 3298, 3283, 3265, 3258, 3255, 3238, 3179, 3164, 3160, 3130, 3127, 3124, 3111, 3095, 3087, 3080, 3077, 3073, 3058, 3026, 2992, 2990, 2987, 2977, 2975, 2958, 2956, 2938, 2935, 2918, 2901, 2893, 2890, 2882, 2881, 2873, 2862, 2855, 2849, 2845, 2844, 2842, 2839, 2836, 2821, 2777, 2768, 2767, 2761, 2753, 2749, 2745, 2695, 2652, 2631, 2626, 2625, 2616, 2611, 2599, 2594, 2591, 2584, 2579, 2575, 2559, 2546, 2544, 2530, 2524, 2498, 2489, 2486, 2477, 2476, 2467, 2458, 2456, 2455, 2444, 2443, 2430, 2428, 2423, 2414, 2403, 2399, 2397, 2393, 2373, 2360, 2348, 2323, 2283, 2282, 2281, 2279, 2269, 2266, 2262, 2257, 2256, 2243, 2223, 2219, 2192, 2180, 2171, 2169, 2162, 2147, 2129, 2127, 2113, 2107, 2106, 2101, 2099, 2071, 2045, 2035, 2032, 2009, 2007, 2005, 1955, 1947, 1938, 1918, 1909, 1905, 1902, 1893, 1889, 1878, 1872, 1855, 1854, 1848, 1817, 1816, 1815, 1814, 1801, 1794, 1718, 1703, 1692, 1683, 1679, 1665, 1661, 1649, 1645, 1629, 1626, 1604, 1562, 1542, 1501, 1498, 1496, 1491, 1488, 1483, 1476, 1475, 1465, 1458, 1450, 1443, 1441, 1422, 1415, 1410, 1376, 1363, 1344, 1339, 1334, 1333, 1332, 1322, 1315, 1313, 1303, 1300, 1289, 1273, 1267, 1265, 1263, 1237, 1223, 1220, 1216, 1202, 1201, 1193, 1182, 1159, 1141, 1116, 1114, 1072, 1065, 1058, 1048, 1042, 1031, 1023, 1014, 1007, 997, 972, 960, 959, 953, 943, 928, 916, 903, 896, 895, 885, 883, 868, 864, 859, 843, 824, 823, 811, 790, 789, 785, 784, 780, 774, 759, 757, 756, 739, 724, 723, 722, 701, 700, 672, 671, 662, 651, 639, 631, 613, 608, 597, 578, 559, 558, 552, 549, 546, 543, 542, 540, 539, 530, 524, 520, 507, 506, 490, 470, 451, 444, 437, 433, 426, 409, 404, 400, 396, 364, 347, 337, 335, 321, 312, 296, 285, 276, 263, 261, 247, 238, 232, 230, 219, 216, 206, 196, 188, 175, 165, 150, 141, 131, 129, 110, 103, 80, 68, 37, 16]
removeMax test completed.

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(5.11)删除二分搜索树的最大元素和最小元素

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多