{"id":507,"date":"2019-03-08T15:40:15","date_gmt":"2019-03-08T07:40:15","guid":{"rendered":"https:\/\/fick707.com\/?p=507"},"modified":"2019-03-08T15:40:39","modified_gmt":"2019-03-08T07:40:39","slug":"java-treemap-deep-analysis","status":"publish","type":"post","link":"https:\/\/fick707.com\/?p=507","title":{"rendered":"java TreeMap\u6df1\u5165\u5206\u6790"},"content":{"rendered":"
\n

\u8f6c\u8f7d\u81ea\uff1ahttps:\/\/www.cnblogs.com\/pony1223\/p\/7892401.html<\/p>\n

\u4e00\u3001\u8ba4\u8bc6TreeMap<\/strong><\/p>\n

\u4e4b\u524d\u7684\u6587\u7ae0\u8bb2\u89e3\u4e86HashMap\uff0c\u5b83\u4fdd\u8bc1\u4e86\u4ee5O(1)\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u8fdb\u884c\u589e\u3001\u5220\u3001\u6539\u3001\u67e5\uff0c\u4ece\u5b58\u50a8\u89d2\u5ea6\u8003\u8651\uff0c\u8fd9\u4e24\u79cd\u6570\u636e\u7ed3\u6784\u662f\u975e\u5e38\u4f18\u79c0\u7684\u3002<\/p>\n

\u5c3d\u7ba1\u5982\u6b64\uff0cHashMap\u8fd8\u662f\u6709\u81ea\u5df1\u7684\u5c40\u9650\u6027—-\u5b83\u4eec\u4e0d\u5177\u5907\u7edf\u8ba1\u6027\u80fd\uff0c\u6216\u8005\u8bf4\u5b83\u4eec\u7684\u7edf\u8ba1\u6027\u80fd\u65f6\u95f4\u590d\u6742\u5ea6\u5e76\u4e0d\u662f\u5f88\u597d\u624d\u66f4\u51c6\u786e\uff0c\u6240\u6709\u7684\u7edf\u8ba1\u5fc5\u987b\u904d\u5386\u6240\u6709Entry\uff0c\u56e0\u6b64\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(N)<\/strong>\u3002\u6bd4\u5982Map\u7684Key\u67091\u30012\u30013\u30014\u30015\u30016\u30017\uff0c\u6211\u73b0\u5728\u8981\u7edf\u8ba1\uff1a<\/p>\n

    \n
  1. \u6240\u6709Key\u6bd43\u5927\u7684\u952e\u503c\u5bf9\u6709\u54ea\u4e9b<\/li>\n
  2. Key\u6700\u5c0f\u7684\u548cKey\u6700\u5927\u7684\u662f\u54ea\u4e24\u4e2a<\/li>\n<\/ol>\n

    \u5c31\u7c7b\u4f3c\u8fd9\u4e9b\u64cd\u4f5c\uff0cHashMap\u505a\u5f97\u6bd4\u8f83\u5dee\uff0c\u6b64\u65f6\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528TreeMap\u3002TreeMap\u7684Key\u6309\u7167\u81ea\u7136\u987a\u5e8f\u8fdb\u884c\u6392\u5e8f\u6216\u8005\u6839\u636e\u521b\u5efa\u6620\u5c04\u65f6\u63d0\u4f9b\u7684Comparator\u63a5\u53e3\u8fdb\u884c\u6392\u5e8f\u3002TreeMap\u4e3a\u589e\u3001\u5220\u3001\u6539\u3001\u67e5\u8fd9\u4e9b\u64cd\u4f5c\u63d0\u4f9b\u4e86log(N)\u7684\u65f6\u95f4\u5f00\u9500<\/strong>\uff0c\u4ece\u5b58\u50a8\u89d2\u5ea6\u800c\u8a00\uff0c\u8fd9\u6bd4HashMap\u7684O(1)\u65f6\u95f4\u590d\u6742\u5ea6\u8981\u5dee\u4e9b\uff1b\u4f46\u662f\u5728\u7edf\u8ba1\u6027\u80fd\u4e0a\uff0cTreeMap\u540c\u6837\u53ef\u4ee5\u4fdd\u8bc1log(N)\u7684\u65f6\u95f4\u5f00\u9500\uff0c\u8fd9\u53c8\u6bd4HashMap\u7684O(N)\u65f6\u95f4\u590d\u6742\u5ea6\u597d\u4e0d\u5c11\u3002<\/p>\n

    \u56e0\u6b64\u603b\u7ed3\u800c\u8a00\uff1a\u5982\u679c\u53ea\u9700\u8981\u5b58\u50a8\u529f\u80fd\uff0c\u4f7f\u7528HashMap\u662f\u4e00\u79cd\u66f4\u597d\u7684\u9009\u62e9\uff1b\u5982\u679c\u8fd8\u9700\u8981\u4fdd\u8bc1\u7edf\u8ba1\u6027\u80fd\u6216\u8005\u9700\u8981\u5bf9Key\u6309\u7167\u4e00\u5b9a\u89c4\u5219\u8fdb\u884c\u6392\u5e8f\uff0c\u90a3\u4e48\u4f7f\u7528TreeMap\u662f\u4e00\u79cd\u66f4\u597d\u7684\u9009\u62e9\u3002<\/p>\n

    \u4e8c\u3001\u7ea2\u9ed1\u6811\u4ecb\u7ecd<\/strong><\/p>\n

    \u7ea2\u9ed1\u6811\u53c8\u79f0\u7ea2-\u9ed1\u4e8c\u53c9\u6811\uff0c\u5b83\u9996\u5148\u662f\u4e00\u9897\u4e8c\u53c9\u6811\uff0c\u5b83\u5177\u4f53\u4e8c\u53c9\u6811\u6240\u6709\u7684\u7279\u6027\u3002\u540c\u65f6\u7ea2\u9ed1\u6811\u66f4\u662f\u4e00\u9897\u81ea\u5e73\u8861\u7684\u6392\u5e8f\u4e8c\u53c9\u6811\u3002
    \n\u6211\u4eec\u77e5\u9053\u4e00\u9897\u57fa\u672c\u7684\u4e8c\u53c9\u6811\u4ed6\u4eec\u90fd\u9700\u8981\u6ee1\u8db3\u4e00\u4e2a\u57fa\u672c\u6027\u8d28–\u5373\u6811\u4e2d\u7684\u4efb\u4f55\u8282\u70b9\u7684\u503c\u5927\u4e8e\u5b83\u7684\u5de6\u5b50\u8282\u70b9\uff0c\u4e14\u5c0f\u4e8e\u5b83\u7684\u53f3\u5b50\u8282\u70b9\u3002\u6309\u7167\u8fd9\u4e2a\u57fa\u672c\u6027\u8d28\u4f7f\u5f97\u6811\u7684\u68c0\u7d22\u6548\u7387\u5927\u5927\u63d0\u9ad8\u3002\u6211\u4eec\u77e5\u9053\u5728\u751f\u6210\u4e8c\u53c9\u6811\u7684\u8fc7\u7a0b\u662f\u975e\u5e38\u5bb9\u6613\u5931\u8861\u7684\uff0c\u6700\u574f\u7684\u60c5\u51b5\u5c31\u662f\u4e00\u8fb9\u5012\uff08\u53ea\u6709\u53f3\/\u5de6\u5b50\u6811\uff09\uff0c\u8fd9\u6837\u52bf\u5fc5\u4f1a\u5bfc\u81f4\u4e8c\u53c9\u6811\u7684\u68c0\u7d22\u6548\u7387\u5927\u5927\u964d\u4f4e\uff08O(n)\uff09\uff0c\u6240\u4ee5\u4e3a\u4e86\u7ef4\u6301\u4e8c\u53c9\u6811\u7684\u5e73\u8861\uff0c\u5927\u725b\u4eec\u63d0\u51fa\u4e86\u5404\u79cd\u5b9e\u73b0\u7684\u7b97\u6cd5\uff0c\u5982\uff1aAVL\uff0cSBT\uff0c\u4f38\u5c55\u6811\uff0cTREAP \uff0c\u7ea2\u9ed1\u6811\u7b49\u7b49\u3002
    \n\u5e73\u8861\u4e8c\u53c9\u6811\u5fc5\u987b\u5177\u5907\u5982\u4e0b\u7279\u6027\uff1a\u5b83\u662f\u4e00\u68f5\u7a7a\u6811\u6216\u5b83\u7684\u5de6\u53f3\u4e24\u4e2a\u5b50\u6811\u7684\u9ad8\u5ea6\u5dee\u7684\u7edd\u5bf9\u503c\u4e0d\u8d85\u8fc71\uff0c\u5e76\u4e14\u5de6\u53f3\u4e24\u4e2a\u5b50\u6811\u90fd\u662f\u4e00\u68f5\u5e73\u8861\u4e8c\u53c9\u6811\u3002\u4e5f\u5c31\u662f\u8bf4\u8be5\u4e8c\u53c9\u6811\u7684\u4efb\u4f55\u4e00\u4e2a\u7b49\u7b49\u5b50\u8282\u70b9\uff0c\u5176\u5de6\u53f3\u5b50\u6811\u7684\u9ad8\u5ea6\u90fd\u76f8\u8fd1\u3002<\/p>\n

    \"\"<\/p>\n

    \u7ea2\u9ed1\u6811\u987e\u540d\u601d\u4e49\u5c31\u662f\u8282\u70b9\u662f\u7ea2\u8272\u6216\u8005\u9ed1\u8272\u7684\u5e73\u8861\u4e8c\u53c9\u6811\uff0c\u5b83\u901a\u8fc7\u989c\u8272\u7684\u7ea6\u675f\u6765\u7ef4\u6301\u7740\u4e8c\u53c9\u6811\u7684\u5e73\u8861\u3002\u5bf9\u4e8e\u4e00\u68f5\u6709\u6548\u7684\u7ea2\u9ed1\u6811\u4e8c\u53c9\u6811\u800c\u8a00\u6211\u4eec\u5fc5\u987b\u589e\u52a0\u5982\u4e0b\u89c4\u5219\uff1a<\/p>\n

    1\u3001\u6bcf\u4e2a\u8282\u70b9\u90fd\u53ea\u80fd\u662f\u7ea2\u8272\u6216\u8005\u9ed1\u8272<\/p>\n

    2\u3001\u6839\u8282\u70b9\u662f\u9ed1\u8272<\/p>\n

    3\u3001\u6bcf\u4e2a\u53f6\u8282\u70b9\uff08NIL\u8282\u70b9\uff0c\u7a7a\u8282\u70b9\uff09\u662f\u9ed1\u8272\u7684\u3002<\/p>\n

    4\u3001\u5982\u679c\u4e00\u4e2a\u7ed3\u70b9\u662f\u7ea2\u7684\uff0c\u5219\u5b83\u4e24\u4e2a\u5b50\u8282\u70b9\u90fd\u662f\u9ed1\u7684\u3002\u4e5f\u5c31\u662f\u8bf4\u5728\u4e00\u6761\u8def\u5f84\u4e0a\u4e0d\u80fd\u51fa\u73b0\u76f8\u90bb\u7684\u4e24\u4e2a\u7ea2\u8272\u7ed3\u70b9\u3002<\/p>\n

    5\u3001\u4ece\u4efb\u4e00\u8282\u70b9\u5230\u5176\u6bcf\u4e2a\u53f6\u5b50\u7684\u6240\u6709\u8def\u5f84\u90fd\u5305\u542b\u76f8\u540c\u6570\u76ee\u7684\u9ed1\u8272\u8282\u70b9\u3002<\/p>\n

    \u8fd9\u4e9b\u7ea6\u675f\u5f3a\u5236\u4e86\u7ea2\u9ed1\u6811\u7684\u5173\u952e\u6027\u8d28: \u4ece\u6839\u5230\u53f6\u5b50\u7684\u6700\u957f\u7684\u53ef\u80fd\u8def\u5f84\u4e0d\u591a\u4e8e\u6700\u77ed\u7684\u53ef\u80fd\u8def\u5f84\u7684\u4e24\u500d\u957f\u3002\u7ed3\u679c\u662f\u8fd9\u68f5\u6811\u5927\u81f4\u4e0a\u662f\u5e73\u8861\u7684\u3002\u56e0\u4e3a\u64cd\u4f5c\u6bd4\u5982\u63d2\u5165\u3001\u5220\u9664\u548c\u67e5\u627e\u67d0\u4e2a\u503c\u7684\u6700\u574f\u60c5\u51b5\u65f6\u95f4\u90fd\u8981\u6c42\u4e0e\u6811\u7684\u9ad8\u5ea6\u6210\u6bd4\u4f8b\uff0c\u8fd9\u4e2a\u5728\u9ad8\u5ea6\u4e0a\u7684\u7406\u8bba\u4e0a\u9650\u5141\u8bb8\u7ea2\u9ed1\u6811\u5728\u6700\u574f\u60c5\u51b5\u4e0b\u90fd\u662f\u9ad8\u6548\u7684\uff0c\u800c\u4e0d\u540c\u4e8e\u666e\u901a\u7684\u4e8c\u53c9\u67e5\u627e\u6811\u3002\u6240\u4ee5\u7ea2\u9ed1\u6811\u5b83\u662f\u590d\u6742\u800c\u9ad8\u6548\u7684\uff0c\u5176\u68c0\u7d22\u6548\u7387O(log\u00a0n<\/em>)\u3002\u4e0b\u56fe\u4e3a\u4e00\u9897\u5178\u578b\u7684\u7ea2\u9ed1\u4e8c\u53c9\u6811\u3002<\/p>\n

    \"\"<\/p>\n

    \u5bf9\u4e8e\u7ea2\u9ed1\u4e8c\u53c9\u6811\u800c\u8a00\u5b83\u4e3b\u8981\u5305\u62ec\u4e09\u5927\u57fa\u672c\u64cd\u4f5c\uff1a\u5de6\u65cb\u3001\u53f3\u65cb\u3001\u7740\u8272\u3002<\/p>\n

    \"\"\u5de6\u8fb9\u65cb\u8f6c<\/p>\n

    \"\"\u53f3\u8fb9\u65cb\u8f6c<\/p>\n

    \uff08\u56fe\u7247\u6765\u81ea\uff1ahttp:\/\/www.cnblogs.com\/yangecnu\/p\/Introduce-Red-Black-Tree.html<\/a>\uff09<\/p>\n

    \u6ce8\uff1a\u7531\u4e8e\u672c\u6587\u4e3b\u8981\u662f\u8bb2\u89e3Java\u4e2dTreeMap\uff0c\u6240\u4ee5\u5e76\u6ca1\u6709\u5bf9\u7ea2\u9ed1\u6811\u8fdb\u884c\u975e\u5e38\u6df1\u5165\u7684\u4e86\u89e3\u548c\u7814\u7a76\uff0c\u5982\u679c\u60f3\u5bf9\u5176\u8fdb\u884c\u66f4\u52a0\u6df1\u5165\u7684\u7814\u7a76\u63d0\u4f9b\u51e0\u7bc7\u8f83\u597d\u7684\u535a\u6587\uff1a<\/p>\n

    1\u3001\u7ea2\u9ed1\u6811\u7cfb\u5217\u96c6\u9526<\/a><\/p>\n

    2\u3001\u7ea2\u9ed1\u6811\u6570\u636e\u7ed3\u6784\u5256\u6790<\/a><\/p>\n

    3\u3001\u7ea2\u9ed1\u6811<\/a><\/p>\n

    \u4e09\u3001TreeMap\u7684\u6570\u636e\u7ed3\u6784<\/strong><\/p>\n

    \n
    public class TreeMap<K,V>\n    extends AbstractMap<K,V>\n    implements NavigableMap<K,V>, Cloneable, java.io.Serializable<\/pre>\n<\/div>\n
    TreeMap\u7ee7\u627fAbstractMap\uff0c\u5b9e\u73b0NavigableMap\u3001Cloneable\u3001Serializable\u4e09\u4e2a\u63a5\u53e3\u3002\u5176\u4e2dAbstractMap\u8868\u660eTreeMap\u4e3a\u4e00\u4e2aMap\u5373\u652f\u6301key-value\u7684\u96c6\u5408\uff0c NavigableMap\uff08\u66f4\u591a<\/a>\uff09\u5219\u610f\u5473\u7740\u5b83\u652f\u6301\u4e00\u7cfb\u5217\u7684\u5bfc\u822a\u65b9\u6cd5\uff0c\u5177\u5907\u9488\u5bf9\u7ed9\u5b9a\u641c\u7d22\u76ee\u6807\u8fd4\u56de\u6700\u63a5\u8fd1\u5339\u914d\u9879\u7684\u5bfc\u822a\u65b9\u6cd5 \u3002<\/p>\n
    TreeMap\u4e2d\u540c\u65f6\u4e5f\u5305\u542b\u4e86\u5982\u4e0b\u51e0\u4e2a\u91cd\u8981\u7684\u5c5e\u6027\uff1a<\/p>\n
    \n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
    \/\/\u6bd4\u8f83\u5668\uff0c\u56e0\u4e3aTreeMap\u662f\u6709\u5e8f\u7684\uff0c\u901a\u8fc7comparator\u63a5\u53e3\u6211\u4eec\u53ef\u4ee5\u5bf9TreeMap\u7684\u5185\u90e8\u6392\u5e8f\u8fdb\u884c\u7cbe\u5bc6\u7684\u63a7\u5236\n        private final Comparator<? super K> comparator;\n        \/\/TreeMap\u7ea2-\u9ed1\u8282\u70b9\uff0c\u4e3aTreeMap\u7684\u5185\u90e8\u7c7b\n        private transient Entry<K,V> root = null;\n        \/\/\u5bb9\u5668\u5927\u5c0f\n        private transient int size = 0;\n        \/\/TreeMap\u4fee\u6539\u6b21\u6570\n        private transient int modCount = 0;\n        \/\/\u7ea2\u9ed1\u6811\u7684\u8282\u70b9\u989c\u8272--\u7ea2\u8272\n        private static final boolean RED = false;\n        \/\/\u7ea2\u9ed1\u6811\u7684\u8282\u70b9\u989c\u8272--\u9ed1\u8272\n        private static final boolean BLACK = true;<\/pre>\n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
    \u5bf9\u4e8e\u53f6\u5b50\u8282\u70b9Entry\u662fTreeMap\u7684\u5185\u90e8\u7c7b\uff0c\u5b83\u6709\u51e0\u4e2a\u91cd\u8981\u7684\u5c5e\u6027\uff1a<\/p>\n
    \n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
            \/\/\u952e\n        K key;\n        \/\/\u503c\n        V value;\n        \/\/\u5de6\u5b69\u5b50\n        Entry<K,V> left = null;\n        \/\/\u53f3\u5b69\u5b50\n        Entry<K,V> right = null;\n        \/\/\u7236\u4eb2\n        Entry<K,V> parent;\n        \/\/\u989c\u8272\n        boolean color = BLACK;<\/pre>\n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
    \u56db\u3001\u6838\u5fc3\u65b9\u6cd5put \u5206\u6790<\/strong><\/p>\n
    \u5206\u6790put\u65b9\u6cd5\u7684\u8fc7\u7a0b\uff0c\u6211\u4eec\u91c7\u7528\u5b9e\u4f8b\u6765\u8fdb\u884c\u5206\u6790\uff0c\u4e0b\u9762\u6211\u4eec\u662f\u6211\u4eec\u5199\u7684\u4e00\u6bb5\u4ee3\u7801\uff1a<\/p>\n
    \n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
    package com.pony1223;\n\nimport java.util.Map;\nimport java.util.TreeMap;\n\npublic class MapDemo\n{\n    public static void main(String[] args) \n    {\n        TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();\n        treeMap.put(10, \"10\");\n        treeMap.put(83, \"83\");\n        treeMap.put(15, \"15\");\n        treeMap.put(72, \"72\");\n        treeMap.put(20, \"20\");\n        treeMap.put(60, \"60\");\n        treeMap.put(30, \"30\");\n        treeMap.put(50, \"50\");\n\n        for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {\n            System.out.println(entry.getKey() + \":\" + entry.getValue());\n        }\n        \n    }\n\n}<\/pre>\n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
    \u6211\u4eec\u6253\u5370\u7ed3\u679c\u53d1\u73b0\uff1a<\/p>\n
    \"\"<\/p>\n
    \u4e8b\u5b9e\u518d\u6b21\u8bc1\u660eTreeMap\u662f\u6709\u5e8f\u7684\u3002<\/p>\n
    \u63a5\u4e0b\u6765\u7684\u5185\u5bb9\u4f1a\u7ed9\u51fa\u63d2\u5165\u6bcf\u6761\u6570\u636e\u4e4b\u540e\u7ea2\u9ed1\u6811\u7684\u6570\u636e\u7ed3\u6784\u662f\u4ec0\u4e48\u6837\u5b50\u7684\u3002\u9996\u5148\u770b\u4e00\u4e0btreeMap\u7684put\u65b9\u6cd5\u7684\u4ee3\u7801\u5b9e\u73b0\uff1a<\/p>\n
    \n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
    public V put(K key, V value) {\n           \/\/\u7528t\u8868\u793a\u4e8c\u53c9\u6811\u7684\u5f53\u524d\u8282\u70b9\n            Entry<K,V> t = root;\n            \/\/t\u4e3anull\u8868\u793a\u4e00\u4e2a\u7a7a\u6811\uff0c\u5373TreeMap\u4e2d\u6ca1\u6709\u4efb\u4f55\u5143\u7d20\uff0c\u76f4\u63a5\u63d2\u5165\n            if (t == null) {\n                \/\/\u6bd4\u8f83key\u503c\uff0c\u4e2a\u4eba\u89c9\u5f97\u8fd9\u53e5\u4ee3\u7801\u6ca1\u6709\u4efb\u4f55\u610f\u4e49\uff0c\u7a7a\u6811\u8fd8\u9700\u8981\u6bd4\u8f83\u3001\u6392\u5e8f\uff1f\n                compare(key, key); \/\/ type (and possibly null) check\n                \/\/\u5c06\u65b0\u7684key-value\u952e\u503c\u5bf9\u521b\u5efa\u4e3a\u4e00\u4e2aEntry\u8282\u70b9\uff0c\u5e76\u5c06\u8be5\u8282\u70b9\u8d4b\u4e88\u7ed9root\n                root = new Entry<>(key, value, null);\n                \/\/\u5bb9\u5668\u7684size = 1\uff0c\u8868\u793aTreeMap\u96c6\u5408\u4e2d\u5b58\u5728\u4e00\u4e2a\u5143\u7d20\n                size = 1;\n                \/\/\u4fee\u6539\u6b21\u6570 + 1\n                modCount++;\n                return null;\n            }\n            int cmp;     \/\/cmp\u8868\u793akey\u6392\u5e8f\u7684\u8fd4\u56de\u7ed3\u679c\n            Entry<K,V> parent;   \/\/\u7236\u8282\u70b9\n            \/\/ split comparator and comparable paths\n            Comparator<? super K> cpr = comparator;    \/\/\u6307\u5b9a\u7684\u6392\u5e8f\u7b97\u6cd5\n            \/\/\u5982\u679ccpr\u4e0d\u4e3a\u7a7a\uff0c\u5219\u91c7\u7528\u65e2\u5b9a\u7684\u6392\u5e8f\u7b97\u6cd5\u8fdb\u884c\u521b\u5efaTreeMap\u96c6\u5408\n            if (cpr != null) {\n                do {\n                    parent = t;      \/\/parent\u6307\u5411\u4e0a\u6b21\u5faa\u73af\u540e\u7684t\n                    \/\/\u6bd4\u8f83\u65b0\u589e\u8282\u70b9\u7684key\u548c\u5f53\u524d\u8282\u70b9key\u7684\u5927\u5c0f\n                    cmp = cpr.compare(key, t.key);\n                    \/\/cmp\u8fd4\u56de\u503c\u5c0f\u4e8e0\uff0c\u8868\u793a\u65b0\u589e\u8282\u70b9\u7684key\u5c0f\u4e8e\u5f53\u524d\u8282\u70b9\u7684key\uff0c\u5219\u4ee5\u5f53\u524d\u8282\u70b9\u7684\u5de6\u5b50\u8282\u70b9\u4f5c\u4e3a\u65b0\u7684\u5f53\u524d\u8282\u70b9\n                    if (cmp < 0)\n                        t = t.left;\n                    \/\/cmp\u8fd4\u56de\u503c\u5927\u4e8e0\uff0c\u8868\u793a\u65b0\u589e\u8282\u70b9\u7684key\u5927\u4e8e\u5f53\u524d\u8282\u70b9\u7684key\uff0c\u5219\u4ee5\u5f53\u524d\u8282\u70b9\u7684\u53f3\u5b50\u8282\u70b9\u4f5c\u4e3a\u65b0\u7684\u5f53\u524d\u8282\u70b9\n                    else if (cmp > 0)\n                        t = t.right;\n                    \/\/cmp\u8fd4\u56de\u503c\u7b49\u4e8e0\uff0c\u8868\u793a\u4e24\u4e2akey\u503c\u76f8\u7b49\uff0c\u5219\u65b0\u503c\u8986\u76d6\u65e7\u503c\uff0c\u5e76\u8fd4\u56de\u65b0\u503c\n                    else\n                        return t.setValue(value);\n                } while (t != null);\n            }\n            \/\/\u5982\u679ccpr\u4e3a\u7a7a\uff0c\u5219\u91c7\u7528\u9ed8\u8ba4\u7684\u6392\u5e8f\u7b97\u6cd5\u8fdb\u884c\u521b\u5efaTreeMap\u96c6\u5408\n            else {\n                if (key == null)     \/\/key\u503c\u4e3a\u7a7a\u629b\u51fa\u5f02\u5e38\n                    throw new NullPointerException();\n                \/* \u4e0b\u9762\u5904\u7406\u8fc7\u7a0b\u548c\u4e0a\u9762\u4e00\u6837 *\/\n                Comparable<? super K> k = (Comparable<? super K>) key;\n                do {\n                    parent = t;\n                    cmp = k.compareTo(t.key);\n                    if (cmp < 0)\n                        t = t.left;\n                    else if (cmp > 0)\n                        t = t.right;\n                    else\n                        return t.setValue(value);\n                } while (t != null);\n            }\n            \/\/\u5c06\u65b0\u589e\u8282\u70b9\u5f53\u505aparent\u7684\u5b50\u8282\u70b9\n            Entry<K,V> e = new Entry<>(key, value, parent);\n            \/\/\u5982\u679c\u65b0\u589e\u8282\u70b9\u7684key\u5c0f\u4e8eparent\u7684key\uff0c\u5219\u5f53\u505a\u5de6\u5b50\u8282\u70b9\n            if (cmp < 0)\n                parent.left = e;\n          \/\/\u5982\u679c\u65b0\u589e\u8282\u70b9\u7684key\u5927\u4e8eparent\u7684key\uff0c\u5219\u5f53\u505a\u53f3\u5b50\u8282\u70b9\n            else\n                parent.right = e;\n            \/*\n             *  \u4e0a\u9762\u5df2\u7ecf\u5b8c\u6210\u4e86\u6392\u5e8f\u4e8c\u53c9\u6811\u7684\u7684\u6784\u5efa\uff0c\u5c06\u65b0\u589e\u8282\u70b9\u63d2\u5165\u8be5\u6811\u4e2d\u7684\u5408\u9002\u4f4d\u7f6e\n             *  \u4e0b\u9762fixAfterInsertion()\u65b9\u6cd5\u5c31\u662f\u5bf9\u8fd9\u68f5\u6811\u8fdb\u884c\u8c03\u6574\u3001\u5e73\u8861\uff0c\u5177\u4f53\u8fc7\u7a0b\u53c2\u8003\u4e0a\u9762\u7684\u4e94\u79cd\u60c5\u51b5\n             *\/\n            fixAfterInsertion(e);\n            \/\/TreeMap\u5143\u7d20\u6570\u91cf + 1\n            size++;\n            \/\/TreeMap\u5bb9\u5668\u4fee\u6539\u6b21\u6570 + 1\n            modCount++;\n            return null;\n        }<\/pre>\n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
    \u4ece\u8fd9\u6bb5\u4ee3\u7801\uff0c\u5148\u603b\u7ed3\u4e00\u4e0bTreeMap\u6dfb\u52a0\u6570\u636e\u7684\u51e0\u4e2a\u6b65\u9aa4\uff1a
    \n1.\u83b7\u53d6\u6839\u8282\u70b9\uff0c\u6839\u8282\u70b9\u4e3a\u7a7a\uff0c\u4ea7\u751f\u4e00\u4e2a\u6839\u8282\u70b9\uff0c\u5c06\u5176\u7740\u8272\u4e3a\u9ed1\u8272\uff0c\u9000\u51fa\u4f59\u4e0b\u6d41\u7a0b
    \n2.\u83b7\u53d6\u6bd4\u8f83\u5668\uff0c\u5982\u679c\u4f20\u5165\u7684Comparator\u63a5\u53e3\u4e0d\u4e3a\u7a7a\uff0c\u4f7f\u7528\u4f20\u5165\u7684Comparator\u63a5\u53e3\u5b9e\u73b0\u7c7b\u8fdb\u884c\u6bd4\u8f83\uff1b\u5982\u679c\u4f20\u5165\u7684Comparator\u63a5\u53e3\u4e3a\u7a7a\uff0c\u5c06Key\u5f3a\u8f6c\u4e3aComparable\u63a5\u53e3\u8fdb\u884c\u6bd4\u8f83
    \n3.\u4ece\u6839\u8282\u70b9\u5f00\u59cb\u9010\u4e00\u4f9d\u7167\u89c4\u5b9a\u7684\u6392\u5e8f\u7b97\u6cd5\u8fdb\u884c\u6bd4\u8f83\uff0c\u53d6\u6bd4\u8f83\u503ccmp\uff0c\u5982\u679ccmp=0\uff0c\u8868\u793a\u63d2\u5165\u7684Key\u5df2\u5b58\u5728\uff1b\u5982\u679ccmp>0\uff0c\u53d6\u5f53\u524d\u8282\u70b9\u7684\u53f3\u5b50\u8282\u70b9\uff1b\u5982\u679ccmp<0\uff0c\u53d6\u5f53\u524d\u8282\u70b9\u7684\u5de6\u5b50\u8282\u70b9
    \n4.\u6392\u9664\u63d2\u5165\u7684Key\u5df2\u5b58\u5728\u7684\u60c5\u51b5\uff0c\u7b2c\uff083\uff09\u6b65\u7684\u6bd4\u8f83\u4e00\u76f4\u6bd4\u8f83\u5230\u5f53\u524d\u8282\u70b9t\u7684\u5de6\u5b50\u8282\u70b9\u6216\u53f3\u5b50\u8282\u70b9\u4e3anull\uff0c\u6b64\u65f6t\u5c31\u662f\u6211\u4eec\u5bfb\u627e\u5230\u7684\u8282\u70b9\uff0ccmp>0\u5219\u51c6\u5907\u5f80t\u7684\u53f3\u5b50\u8282\u70b9\u63d2\u5165\u65b0\u8282\u70b9\uff0ccmp<0\u5219\u51c6\u5907\u5f80t\u7684\u5de6\u5b50\u8282\u70b9\u63d2\u5165\u65b0\u8282\u70b9
    \n5.new\u51fa\u4e00\u4e2a\u65b0\u8282\u70b9\uff0c\u9ed8\u8ba4\u4e3a\u9ed1\u8272\uff0c\u6839\u636ecmp\u7684\u503c\u5411t\u7684\u5de6\u8fb9\u6216\u8005\u53f3\u8fb9\u8fdb\u884c\u63d2\u5165
    \n6.\u63d2\u5165\u4e4b\u540e\u8fdb\u884c\u4fee\u590d\uff0c\u5305\u62ec\u5de6\u65cb\u3001\u53f3\u65cb\u3001\u91cd\u65b0\u7740\u8272\u8fd9\u4e9b\u64cd\u4f5c\uff0c\u8ba9\u6811\u4fdd\u6301\u5e73\u8861\u6027
    \n\u7b2c1~\u7b2c5\u6b65\u90fd\u6ca1\u6709\u4ec0\u4e48\u95ee\u9898\uff0c\u7ea2\u9ed1\u6811\u6700\u6838\u5fc3\u7684\u5e94\u5f53\u662f\u7b2c6\u6b65\u63d2\u5165\u6570\u636e\u4e4b\u540e\u8fdb\u884c\u7684\u4fee\u590d\u5de5\u4f5c\uff0c\u5bf9\u5e94\u7684Java\u4ee3\u7801\u662fTreeMap\u4e2d\u7684fixAfterInsertion\u65b9\u6cd5\uff0c\u4e0b\u9762\u770b\u4e00\u4e0bput\u6bcf\u4e2a\u6570\u636e\u4e4b\u540eTreeMap\u90fd\u505a\u4e86\u4ec0\u4e48\u64cd\u4f5c\uff0c\u501f\u6b64\u6765\u7406\u6e05TreeMap\u7684\u5b9e\u73b0\u539f\u7406\u3002<\/p>\n
    put(10, “10”)<\/strong><\/p>\n
    \u9996\u5148\u662fput(10, “10”)\uff0c\u7531\u4e8e\u6b64\u65f6TreeMap\u4e2d\u6ca1\u6709\u4efb\u4f55\u8282\u70b9\uff0c\u56e0\u6b6410\u4e3a\u6839\u4e14\u6839\u8282\u70b9\u4e3a\u9ed1\u8272\u8282\u70b9\uff0cput(10, “10”)\u4e4b\u540e\u7684\u6570\u636e\u7ed3\u6784\u4e3a\uff1a<\/p>\n
    \"\"<\/p>\n
    put(83, “83”)<\/strong><\/p>\n
    \u63a5\u7740\u662fput(83, “83”)\uff0c\u8fd9\u4e00\u6b65\u4e5f\u4e0d\u96be\uff0c83\u6bd410\u5927\uff0c\u56e0\u6b64\u572810\u7684\u53f3\u8282\u70b9\u4e0a\uff0c\u5373\u6267\u884c\u4e0a\u9762\u4ee3\u7801\u4e2ddo{}\u4ee3\u7801\u5757\uff0c\u5b83\u662f\u5b9e\u73b0\u6392\u5e8f\u4e8c\u53c9\u6811\u7684\u6838\u5fc3\u7b97\u6cd5\uff0c\u901a\u8fc7\u8be5\u7b97\u6cd5\u6211\u4eec\u53ef\u4ee5\u786e\u8ba4\u65b0\u589e\u8282\u70b9\u5728\u8be5\u6811\u7684\u6b63\u786e\u4f4d\u7f6e\u3002\u627e\u5230\u6b63\u786e\u4f4d\u7f6e\u540e\u5c06\u63d2\u5165\u5373\u53ef\uff0c\u4f46\u662f\u7531\u4e8e83\u4e0d\u662f\u6839\u8282\u70b9\uff0c\u6211\u77e5\u9053TreeMap\u7684\u5e95\u5c42\u5b9e\u73b0\u662f\u7ea2\u9ed1\u6811\uff0c\u7ea2\u9ed1\u6811\u662f\u4e00\u68f5\u5e73\u8861\u6392\u5e8f\u4e8c\u53c9\u6811\uff0c\u666e\u901a\u7684\u6392\u5e8f\u4e8c\u53c9\u6811\u53ef\u80fd\u4f1a\u51fa\u73b0\u5931\u8861\u7684\u60c5\u51b5\uff0c\u6240\u4ee5\u4e0b\u4e00\u6b65\u5c31\u662f\u8981\u8fdb\u884c\u8c03\u6574\u3002fixAfterInsertion(e); \u8c03\u6574\u7684\u8fc7\u7a0b\u52a1\u5fc5\u4f1a\u6d89\u53ca\u5230\u7ea2\u9ed1\u6811\u7684\u5de6\u65cb\u3001\u53f3\u65cb\u3001\u7740\u8272\u4e09\u4e2a\u57fa\u672c\u64cd\u4f5c\u3002<\/p>\n
    \n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
     1 \/**\n 2      * \u65b0\u589e\u8282\u70b9\u540e\u7684\u4fee\u590d\u64cd\u4f5c\n 3      * x \u8868\u793a\u65b0\u589e\u8282\u70b9\n 4      *\/\n 5      private void fixAfterInsertion(Entry<K,V> x) {\n 6             x.color = RED;    \/\/\u65b0\u589e\u8282\u70b9\u7684\u989c\u8272\u4e3a\u7ea2\u8272\n 7 \n 8             \/\/\u5faa\u73af \u76f4\u5230 x\u4e0d\u662f\u6839\u8282\u70b9\uff0c\u4e14x\u7684\u7236\u8282\u70b9\u4e0d\u4e3a\u7ea2\u8272\n 9             while (x != null && x != root && x.parent.color == RED) {\n10                 \/\/\u5982\u679cX\u7684\u7236\u8282\u70b9\uff08P\uff09\u662f\u5176\u7236\u8282\u70b9\u7684\u7236\u8282\u70b9\uff08G\uff09\u7684\u5de6\u8282\u70b9\n11                 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {\n12                     \/\/\u83b7\u53d6X\u7684\u53d4\u8282\u70b9(U)\n13                     Entry<K,V> y = rightOf(parentOf(parentOf(x)));\n14                     \/\/\u5982\u679cX\u7684\u53d4\u8282\u70b9\uff08U\uff09 \u4e3a\u7ea2\u8272\uff08\u60c5\u51b5\u4e09\uff09\n15                     if (colorOf(y) == RED) {     \n16                         \/\/\u5c06X\u7684\u7236\u8282\u70b9\uff08P\uff09\u8bbe\u7f6e\u4e3a\u9ed1\u8272\n17                         setColor(parentOf(x), BLACK);\n18                         \/\/\u5c06X\u7684\u53d4\u8282\u70b9\uff08U\uff09\u8bbe\u7f6e\u4e3a\u9ed1\u8272\n19                         setColor(y, BLACK);\n20                         \/\/\u5c06X\u7684\u7236\u8282\u70b9\u7684\u7236\u8282\u70b9\uff08G\uff09\u8bbe\u7f6e\u7ea2\u8272\n21                         setColor(parentOf(parentOf(x)), RED);\n22                         x = parentOf(parentOf(x));\n23                     }\n24                     \/\/\u5982\u679cX\u7684\u53d4\u8282\u70b9\uff08U\u4e3a\u9ed1\u8272\uff09\uff1b\u8fd9\u91cc\u4f1a\u5b58\u5728\u4e24\u79cd\u60c5\u51b5\uff08\u60c5\u51b5\u56db\u3001\u60c5\u51b5\u4e94\uff09\n25                     else {   \n26                         \/\/\u5982\u679cX\u8282\u70b9\u4e3a\u5176\u7236\u8282\u70b9\uff08P\uff09\u7684\u53f3\u5b50\u6811\uff0c\u5219\u8fdb\u884c\u5de6\u65cb\u8f6c\uff08\u60c5\u51b5\u56db\uff09\n27                         if (x == rightOf(parentOf(x))) {\n28                             \/\/\u5c06X\u7684\u7236\u8282\u70b9\u4f5c\u4e3aX\n29                             x = parentOf(x);\n30                             \/\/\u53f3\u65cb\u8f6c\n31                             rotateLeft(x);\n32                         }\n33                         \/\/\uff08\u60c5\u51b5\u4e94\uff09\n34                         \/\/\u5c06X\u7684\u7236\u8282\u70b9\uff08P\uff09\u8bbe\u7f6e\u4e3a\u9ed1\u8272\n35                         setColor(parentOf(x), BLACK);\n36                         \/\/\u5c06X\u7684\u7236\u8282\u70b9\u7684\u7236\u8282\u70b9\uff08G\uff09\u8bbe\u7f6e\u7ea2\u8272\n37                         setColor(parentOf(parentOf(x)), RED);\n38                         \/\/\u4ee5X\u7684\u7236\u8282\u70b9\u7684\u7236\u8282\u70b9\uff08G\uff09\u4e3a\u4e2d\u5fc3\u53f3\u65cb\u8f6c\n39                         rotateRight(parentOf(parentOf(x)));\n40                     }\n41                 }\n42                 \/\/\u5982\u679cX\u7684\u7236\u8282\u70b9\uff08P\uff09\u662f\u5176\u7236\u8282\u70b9\u7684\u7236\u8282\u70b9\uff08G\uff09\u7684\u53f3\u8282\u70b9\n43                 else {\n44                     \/\/\u83b7\u53d6X\u7684\u53d4\u8282\u70b9\uff08U\uff09\n45                     Entry<K,V> y = leftOf(parentOf(parentOf(x)));\n46                   \/\/\u5982\u679cX\u7684\u53d4\u8282\u70b9\uff08U\uff09 \u4e3a\u7ea2\u8272\uff08\u60c5\u51b5\u4e09\uff09\n47                     if (colorOf(y) == RED) {\n48                         \/\/\u5c06X\u7684\u7236\u8282\u70b9\uff08P\uff09\u8bbe\u7f6e\u4e3a\u9ed1\u8272\n49                         setColor(parentOf(x), BLACK);\n50                         \/\/\u5c06X\u7684\u53d4\u8282\u70b9\uff08U\uff09\u8bbe\u7f6e\u4e3a\u9ed1\u8272\n51                         setColor(y, BLACK);\n52                         \/\/\u5c06X\u7684\u7236\u8282\u70b9\u7684\u7236\u8282\u70b9\uff08G\uff09\u8bbe\u7f6e\u7ea2\u8272\n53                         setColor(parentOf(parentOf(x)), RED);\n54                         x = parentOf(parentOf(x));\n55                     }\n56                   \/\/\u5982\u679cX\u7684\u53d4\u8282\u70b9\uff08U\u4e3a\u9ed1\u8272\uff09\uff1b\u8fd9\u91cc\u4f1a\u5b58\u5728\u4e24\u79cd\u60c5\u51b5\uff08\u60c5\u51b5\u56db\u3001\u60c5\u51b5\u4e94\uff09\n57                     else {\n58                         \/\/\u5982\u679cX\u8282\u70b9\u4e3a\u5176\u7236\u8282\u70b9\uff08P\uff09\u7684\u53f3\u5b50\u6811\uff0c\u5219\u8fdb\u884c\u5de6\u65cb\u8f6c\uff08\u60c5\u51b5\u56db\uff09\n59                         if (x == leftOf(parentOf(x))) {\n60                             \/\/\u5c06X\u7684\u7236\u8282\u70b9\u4f5c\u4e3aX\n61                             x = parentOf(x);\n62                            \/\/\u53f3\u65cb\u8f6c\n63                             rotateRight(x);\n64                         }\n65                         \/\/\uff08\u60c5\u51b5\u4e94\uff09\n66                         \/\/\u5c06X\u7684\u7236\u8282\u70b9\uff08P\uff09\u8bbe\u7f6e\u4e3a\u9ed1\u8272\n67                         setColor(parentOf(x), BLACK);\n68                         \/\/\u5c06X\u7684\u7236\u8282\u70b9\u7684\u7236\u8282\u70b9\uff08G\uff09\u8bbe\u7f6e\u7ea2\u8272\n69                         setColor(parentOf(parentOf(x)), RED);\n70                         \/\/\u4ee5X\u7684\u7236\u8282\u70b9\u7684\u7236\u8282\u70b9\uff08G\uff09\u4e3a\u4e2d\u5fc3\u53f3\u65cb\u8f6c\n71                         rotateLeft(parentOf(parentOf(x)));\n72                     }\n73                 }\n74             }\n75             \/\/\u5c06\u6839\u8282\u70b9G\u5f3a\u5236\u8bbe\u7f6e\u4e3a\u9ed1\u8272\n76             root.color = BLACK;\n77         }<\/pre>\n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
    \u6211\u4eec\u770b\u7b2c6\u884c\u7684\u4ee3\u7801\uff0c\u5b83\u5c06\u9ed8\u8ba4\u7684\u63d2\u5165\u7684\u90a3\u4e2a\u8282\u70b9\u7740\u8272\u6210\u4e3a<\/strong>\u7ea2\u8272<\/strong>\uff0c\u8fd9\u5f88\u597d\u7406\u89e3\uff1a<\/p>\n
    \u6839\u636e\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\uff083\uff09\uff0c\u7ea2\u9ed1\u6811\u8981\u6c42\u4ece\u6839\u8282\u70b9\u5230\u53f6\u5b50\u6240\u6709\u53f6\u5b50\u8282\u70b9\u4e0a\u7ecf\u8fc7\u7684\u9ed1\u8272\u8282\u70b9\u4e2a\u6570\u662f\u76f8\u540c\u7684\uff0c\u56e0\u6b64\u5982\u679c\u63d2\u5165\u7684\u8282\u70b9\u7740\u8272\u4e3a\u9ed1\u8272\uff0c\u90a3\u5fc5\u7136\u6709\u53ef\u80fd\u5bfc\u81f4\u67d0\u6761\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf\u5927\u4e8e\u5176\u4ed6\u8def\u5f84\u4e0a\u7684\u9ed1\u8272\u8282\u70b9\u6570\u91cf\uff0c\u56e0\u6b64\u9ed8\u8ba4\u63d2\u5165\u7684\u8282\u70b9\u5fc5\u987b\u662f\u7ea2\u8272\u7684\uff0c\u4ee5\u6b64\u6765\u7ef4\u6301\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\uff083\uff09.<\/p>\n
    \u5f53\u7136\u63d2\u5165\u8282\u70b9\u7740\u8272\u4e3a\u7ea2\u8272\u8282\u70b9\u540e\uff0c\u6709\u53ef\u80fd\u5bfc\u81f4\u7684\u95ee\u9898\u662f\u8fdd\u53cd\u6027\u8d28\uff082\uff09\uff0c\u5373\u51fa\u73b0\u8fde\u7eed\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\uff0c\u8fd9\u5c31\u9700\u8981\u901a\u8fc7\u65cb\u8f6c\u64cd\u4f5c\u53bb\u6539\u53d8\u6811\u7684\u7ed3\u6784\uff0c\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u3002<\/p>\n
    \u63a5\u7740\u770b<\/p>\n
    while (x != null && x != root && x.parent.color == RED)<\/pre>\n
    \u7684\u5224\u65ad\uff0c\u524d\u4e24\u4e2a\u6761\u4ef6\u90fd\u6ee1\u8db3\uff0c\u4f46\u662f\u56e0\u4e3a83\u8fd9\u4e2a\u8282\u70b9\u7684\u7236\u8282\u70b9\u662f\u6839\u8282\u70b9\u7684\uff0c\u6839\u8282\u70b9\u662f\u9ed1\u8272\u8282\u70b9\uff0c\u56e0\u6b64\u8fd9\u4e2a\u6761\u4ef6\u4e0d\u6ee1\u8db3\uff0cwhile\u5faa\u73af\u4e0d\u8fdb\u53bb\uff0c\u76f4\u63a5\u6267\u884c\u4e00\u6b21<\/p>\n
    root.color = BLACK;<\/pre>\n
    \u884c\u7684\u4ee3\u7801\u7ed9\u6839\u8282\u70b9\u7740\u8272\u4e3a\u9ed1\u8272\uff08\u56e0\u4e3a\u5728\u65cb\u8f6c\u8fc7\u7a0b\u4e2d\u6709\u53ef\u80fd\u5bfc\u81f4\u6839\u8282\u70b9\u4e3a\u7ea2\u8272\uff0c\u800c\u7ea2\u9ed1\u6811\u7684\u6839\u8282\u70b9\u5fc5\u987b\u662f\u9ed1\u8272\uff0c\u56e0\u6b64\u6700\u540e\u4e0d\u7ba1\u6839\u8282\u70b9\u662f\u4e0d\u662f\u9ed1\u8272\uff0c\u90fd\u8981\u91cd\u65b0\u7740\u8272\u786e\u4fdd\u6839\u8282\u70b9\u662f\u9ed1\u8272\u7684\uff09\u3002<\/p>\n
    \u90a3\u4e48put(83, “83”)\u4e4b\u540e\uff0c\u6574\u4e2a\u6811\u7684\u7ed3\u6784\u53d8\u4e3a\uff1a<\/p>\n
    \"\"<\/p>\n
    \u4e00\u3001\u4e3a\u6839\u8282\u70b9<\/p>\n
    \u82e5\u65b0\u63d2\u5165\u7684\u8282\u70b9N\u6ca1\u6709\u7236\u8282\u70b9\uff0c\u5219\u76f4\u63a5\u5f53\u505a\u6839\u636e\u8282\u70b9\u63d2\u5165\u5373\u53ef\uff0c\u540c\u65f6\u5c06\u989c\u8272\u8bbe\u7f6e\u4e3a\u9ed1\u8272<\/p>\n
    \u4e8c\u3001\u7236\u8282\u70b9\u4e3a\u9ed1\u8272<\/p>\n
    \u8fd9\u79cd\u60c5\u51b5\u65b0\u8282\u70b9N\u540c\u6837\u662f\u76f4\u63a5\u63d2\u5165\uff0c\u540c\u65f6\u989c\u8272\u4e3a\u7ea2\u8272\uff0c\u7531\u4e8e\u6839\u636e\u89c4\u5219\u56db\u5b83\u4f1a\u5b58\u5728\u4e24\u4e2a\u9ed1\u8272\u7684\u53f6\u5b50\u8282\u70b9\uff0c\u503c\u4e3anull\u3002\u540c\u65f6\u7531\u4e8e\u65b0\u589e\u8282\u70b9N\u4e3a\u7ea2\u8272\uff0c\u6240\u4ee5\u901a\u8fc7\u5b83\u7684\u5b50\u8282\u70b9\u7684\u8def\u5f84\u4f9d\u7136\u4f1a\u4fdd\u5b58\u7740\u76f8\u540c\u7684\u9ed1\u8272\u8282\u70b9\u6570\uff0c\u540c\u6837\u6ee1\u8db3\u89c4\u52195\u3002<\/p>\n
    \u5728\u770bput(15, “15”)\u4e4b\u524d\uff0c\u5fc5\u987b\u8981\u5148\u8fc7\u4e00\u4e0bfixAfterInsertion\u65b9\u6cd5\u3002\u7b2c11\u884c\uff5e\u7b2c41\u884c\u7684\u4ee3\u7801\u548c\u7b2c43\u884c~\u7b2c73\u884c\u7684\u4ee3\u7801\u662f\u4e00\u6837\u7684\uff0c\u65e0\u975e\u4e00\u4e2a\u662f\u64cd\u4f5c\u5de6\u5b50\u6811\u53e6\u4e00\u4e2a\u662f\u64cd\u4f5c\u53f3\u5b50\u6811\u800c\u5df2\uff0c\u56e0\u6b64\u5c31\u770b\u524d\u4e00\u534a\uff1a<\/p>\n
    \n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n
     1 while (x != null && x != root && x.parent.color == RED) {\n 2     if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {\n 3         Entry<K,V> y = rightOf(parentOf(parentOf(x)));\n 4         if (colorOf(y) == RED) {\n 5             setColor(parentOf(x), BLACK);\n 6             setColor(y, BLACK);\n 7             setColor(parentOf(parentOf(x)), RED);\n 8             x = parentOf(parentOf(x));\n 9         } else {\n10             if (x == rightOf(parentOf(x))) {\n11                 x = parentOf(x);\n12                 rotateLeft(x);\n13             }\n14             setColor(parentOf(x), BLACK);\n15             setColor(parentOf(parentOf(x)), RED);\n16             rotateRight(parentOf(parentOf(x)));\n17         }\n18     }\n19     ....\n20 }<\/pre>\n
    \"\u590d\u5236\u4ee3\u7801\"<\/a><\/span><\/div>\n<\/div>\n
    \u7b2c2\u884c\u7684\u5224\u65ad\u6ce8\u610f\u4e00\u4e0b\uff0c\u7528\u8bed\u8a00\u63cf\u8ff0\u51fa\u6765\u5c31\u662f\uff1a\u5224\u65ad\u5f53\u524d\u8282\u70b9\u7684\u7236\u8282\u70b9\u4e0e\u5f53\u524d\u8282\u70b9\u7684\u7236\u8282\u70b9\u7684\u7236\u8282\u70b9\u7684\u5de6\u5b50\u8282\u70b9\u662f\u5426\u540c\u4e00\u4e2a\u8282\u70b9<\/strong>\u3002\u7ffb\u8bd1\u4e00\u4e0b\u5c31\u662f\uff1a\u5f53\u524d\u8282\u70b9\u662f\u5426\u5de6\u5b50\u8282\u70b9\u63d2\u5165.<\/strong><\/p>\n
    \u5728\u4e0a\u9762\u4ee3\u7801\u4e2d\u8bf4\u5230\u7684\u60c5\u51b5\u4e09\u3001\u56db\u3001\u4e94\u7684\u610f\u601d\u662f\uff1b<\/strong><\/p>\n
    \u4e09\u3001\u82e5\u7236\u8282\u70b9P\u548cP\u7684\u5144\u5f1f\u8282\u70b9U\u90fd\u4e3a\u7ea2\u8272<\/strong><\/p>\n
    \u5bf9\u4e8e\u8fd9\u79cd\u60c5\u51b5\u82e5\u76f4\u63a5\u63d2\u5165\u80af\u5b9a\u4f1a\u51fa\u73b0\u4e0d\u5e73\u8861\u73b0\u8c61\uff08\u4e0d\u80fd\u51fa\u73b0\u4e24\u4e2a\u8fde\u7740\u7684\u7ea2\u8272\uff09\u3002\u600e\u4e48\u5904\u7406\uff1fP\u3001U\u8282\u70b9\u53d8\u9ed1\u3001G\u8282\u70b9\u53d8\u7ea2\u3002\u8fd9\u65f6\u7531\u4e8e\u7ecf\u8fc7\u8282\u70b9P\u3001U\u7684\u8def\u5f84\u90fd\u5fc5\u987b\u7ecf\u8fc7G\u6240\u4ee5\u5728\u8fd9\u4e9b\u8def\u5f84\u4e0a\u9762\u7684\u9ed1\u8282\u70b9\u6570\u76ee\u8fd8\u662f\u76f8\u540c\u7684\u3002\u4f46\u662f\u7ecf\u8fc7\u4e0a\u9762\u7684\u5904\u7406\uff0c\u53ef\u80fdG\u8282\u70b9\u7684\u7236\u8282\u70b9\u4e5f\u662f\u7ea2\u8272\uff0c\u8fd9\u4e2a\u65f6\u5019\u6211\u4eec\u9700\u8981\u5c06G\u8282\u70b9\u5f53\u505a\u65b0\u589e\u8282\u70b9\u9012\u5f52\u5904\u7406\u3002<\/p>\n
    \"\"<\/p>\n
    \u56db\u3001\u82e5\u7236\u8282\u70b9P\u4e3a\u7ea2\u8272\uff0c\u53d4\u7236\u8282\u70b9U\u4e3a\u9ed1\u8272\u6216\u8005\u7f3a\u5c11\uff0c\u4e14\u65b0\u589e\u8282\u70b9N\u4e3aP\u8282\u70b9\u7684\u53f3\u5b69\u5b50<\/h3>\n
    \u5bf9\u4e8e\u8fd9\u79cd\u60c5\u51b5\u6211\u4eec\u5bf9\u65b0\u589e\u8282\u70b9N\u3001P\u8fdb\u884c\u4e00\u6b21\u5de6\u65cb\u8f6c\u3002\u8fd9\u91cc\u6240\u4ea7\u751f\u7684\u7ed3\u679c\u5176\u5b9e\u5e76\u6ca1\u6709\u5b8c\u6210\uff0c\u8fd8\u4e0d\u662f\u5e73\u8861\u7684\uff08\u8fdd\u53cd\u4e86\u89c4\u5219\u56db\uff09\uff0c\u8fd9\u662f\u6211\u4eec\u9700\u8981\u8fdb\u884c\u60c5\u51b55\u7684\u64cd\u4f5c\u3002<\/p>\n
    \"\"<\/p>\n
    \u4e94\u3001\u7236\u8282\u70b9P\u4e3a\u7ea2\u8272\uff0c\u53d4\u7236\u8282\u70b9U\u4e3a\u9ed1\u8272\u6216\u8005\u7f3a\u5c11\uff0c\u65b0\u589e\u8282\u70b9N\u4e3a\u7236\u8282\u70b9P\u5de6\u5b69\u5b50<\/h3>\n
    \u8fd9\u79cd\u60c5\u51b5\u6709\u53ef\u80fd\u662f\u7531\u4e8e\u60c5\u51b5\u56db\u800c\u4ea7\u751f\u7684\uff0c\u4e5f\u6709\u53ef\u80fd\u4e0d\u662f\u3002\u5bf9\u4e8e\u8fd9\u79cd\u60c5\u51b5\u5148\u5df2P\u8282\u70b9\u4e3a\u4e2d\u5fc3\u8fdb\u884c\u53f3\u65cb\u8f6c\uff0c\u5728\u65cb\u8f6c\u540e\u4ea7\u751f\u7684\u6811\u4e2d\uff0c\u8282\u70b9P\u662f\u8282\u70b9N\u3001G\u7684\u7236\u8282\u70b9\u3002\u4f46\u662f\u8fd9\u68f5\u6811\u5e76\u4e0d\u89c4\u8303\uff0c\u5b83\u8fdd\u53cd\u4e86\u89c4\u52194\uff0c\u6240\u4ee5\u6211\u4eec\u5c06P\u3001G\u8282\u70b9\u7684\u989c\u8272\u8fdb\u884c\u4ea4\u6362\uff0c\u4f7f\u4e4b\u5176\u6ee1\u8db3\u89c4\u8303\u3002\u5f00\u59cb\u65f6\u6240\u6709\u7684\u8def\u5f84\u90fd\u9700\u8981\u7ecf\u8fc7G\u5176\u4ed6\u4eec\u7684\u9ed1\u8272\u8282\u70b9\u6570\u4e00\u6837\uff0c\u4f46\u662f\u73b0\u5728\u6240\u6709\u7684\u8def\u5f84\u6539\u4e3a\u7ecf\u8fc7P\uff0c\u4e14P\u4e3a\u6574\u68f5\u6811\u7684\u552f\u4e00\u9ed1\u8272\u8282\u70b9\uff0c\u6240\u4ee5\u8c03\u6574\u540e\u7684\u6811\u540c\u6837\u6ee1\u8db3\u89c4\u83035\u3002<\/p>\n
    \"\"<\/p>\n
    \u603b\u7ed3\uff1a\u5bf9\u4e8e\u7b2c\u56db\u79cd\u60c5\u51b5\u548c\u7b2c\u4e94\u79cd\u60c5\u51b5\u800c\u8a00\u8fd9\u4e24\u79cd\u63d2\u5165\u65b9\u5f0f\u7684\u5904\u7406\u662f\u4e0d\u540c\u7684\uff0c\u533a\u522b\u662f\u7b2c\u56db\u79cd\u60c5\u51b5\u63d2\u5165\u591a\u4e00\u6b65\u5de6\u65cb\u64cd\u4f5c\u3002\u80fd\u770b\u51fa\uff0c\u7ea2\u9ed1\u6811\u7684\u63d2\u5165\u6700\u591a\u53ea\u9700\u8981\u8fdb\u884c\u4e24\u6b21\u65cb\u8f6c\uff0c\u4e0d\u7ba1\u8fd9\u68f5\u7ea2\u9ed1\u6811\u591a\u4e48\u590d\u6742\uff0c\u90fd\u53ef\u4ee5\u6839\u636e\u8fd9\u4e94\u79cd\u60c5\u51b5\u6765\u8fdb\u884c\u751f\u6210\u3002<\/strong><\/p>\n
    \"\"<\/p>\n
    \u5176\u4e2d\u5de6\u8fb9\u7684\u662f\u5de6\u5b50\u6811\u5916\u4fa7\u63d2\u5165\uff0c\u53f3\u8fb9\u7684\u662f\u5de6\u5b50\u6811\u5185\u4fa7\u63d2\u5165<\/p>\n
    put(15, “15”)<\/strong><\/p>\n
    \u770b\u5b8cfixAfterInsertion\u65b9\u6cd5\u6d41\u7a0b\u4e4b\u540e\uff0c\u7ee7\u7eed\u6dfb\u52a0\u6570\u636e\uff0c\u8fd9\u6b21\u6dfb\u52a0\u7684\u662fput(15, “15”)\uff0c15\u6bd410\u5927\u4e14\u6bd483\u5c0f\uff0c\u56e0\u6b6415\u6700\u7ec8\u5e94\u5f53\u662f83\u7684\u5de6\u5b50\u8282\u70b9\uff0c\u9ed8\u8ba4\u63d2\u5165\u7684\u662f\u7ea2\u8272\u8282\u70b9\uff0c\u56e0\u6b64\u9996\u5148\u5c0615\u4f5c\u4e3a\u7ea2\u8272\u8282\u70b9\u63d2\u516583\u7684\u5de6\u5b50\u8282\u70b9\u540e\u7684\u7ed3\u6784\u5e94\u5f53\u662f\uff1a<\/p>\n
    \"\"<\/p>\n
    \u4f46\u662f\u663e\u7136\u8fd9\u91cc\u8fdd\u53cd\u4e86\u7ea2\u9ed1\u6811\u7684\u6027\u8d28\uff082\uff09\uff0c\u5373\u8fde\u7eed\u51fa\u73b0\u4e86\u4e24\u4e2a\u7ea2\u8272\u8282\u70b9\uff0c\u56e0\u6b64\u6b64\u65f6\u5fc5\u987b\u8fdb\u884c\u65cb\u8f6c\u3002\u56de\u770b\u524d\u9762fixAfterInsertion\u7684\u6d41\u7a0b\uff0c\u4e0a\u9762\u6f14\u793a\u7684\u662f\u5de6\u5b50\u6811\u63d2\u5165\u6d41\u7a0b\uff0c\u53f3\u5b50\u6811\u4e00\u6837\uff0c\u53ef\u4ee5\u770b\u5230\u8fd9\u662f\u53f3\u5b50\u6811\u5185\u4fa7\u63d2\u5165\uff0c\u9700\u8981\u8fdb\u884c\u4e24\u6b21\u65cb\u8f6c\u64cd\u4f5c\uff1a<\/p>\n
      \n
    1. \u5bf9\u65b0\u63d2\u5165\u8282\u70b9\u7684\u7236\u8282\u70b9\u8fdb\u884c\u4e00\u6b21\u53f3\u65cb\u64cd\u4f5c<\/li>\n
    2. \u65b0\u63d2\u5165\u8282\u70b9\u7684\u7236\u8282\u70b9\u7740\u8272\u4e3a\u9ed1\u8272\uff0c\u65b0\u63d2\u5165\u8282\u70b9\u7684\u7956\u7236\u8282\u70b9\u7740\u8272\u4e3a\u7ea2\u8272<\/li>\n
    3. \u5bf9\u65b0\u63d2\u5165\u8282\u70b9\u7684\u7956\u7236\u8282\u70b9\u8fdb\u884c\u4e00\u6b21\u5de6\u65cb\u64cd\u4f5c<\/li>\n<\/ol>\n
      \u65cb\u8f6c\u662f\u7ea2\u9ed1\u6811\u4e2d\u6700\u96be\u7406\u89e3\u4e5f\u662f\u6700\u6838\u5fc3\u7684\u64cd\u4f5c\uff0c\u53f3\u65cb\u548c\u5de6\u65cb\u662f\u5bf9\u79f0\u7684\u64cd\u4f5c\uff0c\u6211\u4e2a\u4eba\u7684\u7406\u89e3\uff0c\u4ee5\u53f3\u65cb\u4e3a\u4f8b\uff0c\u5bf9\u67d0\u4e2a\u8282\u70b9x\u8fdb\u884c\u53f3\u65cb\uff0c\u5176\u5b9e\u8d28\u662f\uff1a<\/p>\n