片片日本久久97,伊人九九九精品一本色,亚洲日韩精品网无

上節(jié)課學(xué)習(xí)了二分搜索樹這樣一種有序數(shù)據(jù)結(jié)構(gòu) ，本節(jié)課將借助二分搜索樹來實現(xiàn)更高級的數(shù)據(jù)結(jié)構(gòu)--集合與映射。

1. 集合

1.1 基于二分搜索樹的集合實現(xiàn)

集合的主要特點是不能盛放重復(fù)元素，在實際生活中，應(yīng)用也很廣泛：

公司客戶統(tǒng)計
書籍詞匯量統(tǒng)計

上一節(jié)實現(xiàn)的二分搜索樹不能添加相同的元素，是非常好的實現(xiàn)集合的底層數(shù)據(jù)結(jié)構(gòu)。要實現(xiàn)集合，首先需要定義如下通用型集合接口：

    public interface Set<E> {
        // 1. 添加元素
        public void add(E e);
        
        // 2. 刪除元素
        public void remove(E e);
        
        // 3. 判斷是否為空
        public boolean isEmpty();
        
        // 4. 查看集合內(nèi)元素個數(shù)
        public int getSize();
        
        // 5. 判斷是否包含某元素
        public boolean contains(E e);
    }

然后使用上一節(jié)創(chuàng)建的二分搜索樹來實現(xiàn)該接口：

    import java.util.Comparator;

    public class BSTSet<E extends Comparable<E>> implements Set<E> {
        private BST<E> data;

        public BSTSet() {
            data = new BST<>();
        }

        @Override
        public int getSize() {
            return data.getSize();
        }
        
        @Override
        public boolean isEmpty() {
            return data.isEmpty();
        }
        
        @Override
        public boolean contains(E e) {
            return data.contains(e);
        }
        
        @Override
        public void add(E e) {
            data.addElement(e);
        }
        
        @Override
        public void remove(E e) {
            data.removeElement(e);
        }
    }

下面測試上述實現(xiàn)，編寫測試函數(shù)，計算《傲慢與偏見》的詞匯量，這里需要借助文件讀取，首先實現(xiàn)文字的切割：

    import java.io.FileInputStream;
    import java.util.ArrayList;
    import java.util.Scanner;
    import java.util.Locale;
    import java.io.File;
    import java.io.BufferedInputStream;
    import java.io.IOException;

    // 文件相關(guān)操作
    public class FileOperation {

        // 讀取文件名稱為filename中的內(nèi)容，并將其中包含的所有詞語放進words中
        public static boolean readFile(String filename, ArrayList<String> words){

            if (filename == null || words == null){
                System.out.println("filename is null or words is null");
                return false;
            }

            // 文件讀取
            Scanner scanner;

            try {
                File file = new File(filename);
                if(file.exists()){
                    FileInputStream fis = new FileInputStream(file);
                    scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
                    scanner.useLocale(Locale.ENGLISH);
                }
                else
                    return false;
            }
            catch(IOException ioe){
                System.out.println("Cannot open " + filename);
                return false;
            }

            // 簡單分詞
            // 這個分詞方式相對簡陋, 沒有考慮很多文本處理中的特殊問題
            // 在這里只做demo展示用
            if (scanner.hasNextLine()) {

                String contents = scanner.useDelimiter("\\A").next();

                int start = firstCharacterIndex(contents, 0);
                for (int i = start + 1; i <= contents.length(); )
                    if (i == contents.length() || !Character.isLetter(contents.charAt(i))) {
                        String word = contents.substring(start, i).toLowerCase();
                        words.add(word);
                        start = firstCharacterIndex(contents, i);
                        i = start + 1;
                    } else
                        i++;
            }

            return true;
        }

        // 尋找字符串s中，從start的位置開始的第一個字母字符的位置
        private static int firstCharacterIndex(String s, int start){

            for( int i = start ; i < s.length() ; i ++ )
                if( Character.isLetter(s.charAt(i)) )
                    return i;
            return s.length();
        }
    }

測試函數(shù)：

    public static void main(String[] args) {
        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
            
            System.out.println("Total words:"+words.size()); // 125901
            
            BSTSet<String> bst =  new BSTSet<>();
            for(String word:words) {
                bst.add(word);
            }
            
            System.out.println("Total different words: "+bst.getSize()); // 6530
        }
        else {
            throw new IllegalArgumentException("Read failed");
        }
    }

可以看到，完成二分搜索樹的增刪邏輯之后，借助二分搜索樹實現(xiàn)集合是非常簡單的，下面考慮用鏈表實現(xiàn)集合。

1.2 基于鏈表的集合實現(xiàn)

基于之前構(gòu)造的鏈表結(jié)構(gòu)，也可以實現(xiàn)集合功能，只不過在添加元素時，需要先判斷鏈表中是否已包含該元素，另外，鏈表集合中的泛型無需實現(xiàn)比較器：

    import java.util.ArrayList;

    public class LinkedListSet<E> implements Set<E> {
        private LinkedList<E> list;
        
        public LinkedListSet() {
            list = new LinkedList<>();
        }
        
        @Override
        public int getSize() {
            return list.getSize();
        }
        
        @Override
        public boolean isEmpty() {
            return list.isEmpty();
        }
        
        @Override
        public boolean contains(E e) {
            return list.contains(e);
        }
        
        @Override
        public void add(E e) {
            // 加一句判斷，若列表中已包含元素，則不添加元素
            if(!list.contains(e))
                list.addFirst(e);
        }
        
        @Override
        public void remove(E e) {
            list.removeElement(e);
        }
    }

可以采用相同的測試函數(shù)來驗證上述實現(xiàn)的有效性：

    public static void main(String[] args) {
        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
            
            System.out.println("Total words:"+words.size()); // 125901
            
            LinkedListSet<String> list =  new LinkedListSet<>();
            for(String word:words) {
                list.add(word);
            }
            
            System.out.println("Total different words: "+list.getSize()); // 6530
        }
        else {
            throw new IllegalArgumentException("Read failed");
        }
    }

運行時可以很明顯感覺到將鏈表作為底層結(jié)構(gòu)，耗時要比二分搜索樹長很多。

1.3 時間復(fù)雜度分析

對于底層結(jié)構(gòu)是鏈表的集合，其時間復(fù)雜度與鏈表的時間復(fù)雜度相關(guān)：

增(add)：鏈表本身添加操作的時間復(fù)雜度為O(1)，然而為實現(xiàn)集合元素不能重復(fù)的特性，添加元素時需要先遍歷一遍鏈表，判斷是否包含待添加元素，因此時間復(fù)雜度為O(n)
刪(remove)：鏈表的刪除操作需要找到待刪除元素的前一節(jié)點，因此時間復(fù)雜度為O(n)
查(contains)：需要遍歷鏈表所有元素，復(fù)雜度為O(n)

下面分析二分搜索樹的時間復(fù)雜度，二分搜索樹本質(zhì)上是一種順序結(jié)構(gòu)，增刪查操作與二分搜索樹的深度h有關(guān)：

image.png

考慮二分搜索樹中節(jié)點個數(shù)n與深度h的關(guān)系：

對于一個滿二叉樹，除了葉子節(jié)點，每個節(jié)點都有兩個孩子

image.png

可以看到，第 $0$ 層有 $1$ 個節(jié)點，第 $1$ 層有 $2$ 個節(jié)點，第 $2$ 層有 $4$ 個節(jié)點，...，第 $i$ 層有 $2^i$ 個節(jié)點，因此對于滿二叉樹， $n = 2^0+2^1+...+2^{h-1}=2^h-1$ 增刪查的時間復(fù)雜度為 $O(h)=O(logn)$
上面滿二叉樹是一種平均情況，對于極端的情況，二分搜索樹有可能退化成鏈表，此時時間復(fù)雜度為 $O(n)$

image.png

下面的測試函數(shù)用來簡單測試鏈表集合類與二分搜索樹集合類的效率：

public static double  testSet(Set<String> set,String filename) {
    long startTime = System.nanoTime();
    ArrayList<String> words = new ArrayList<>();
    if(FileOperation.readFile(filename, words)) {
        
        System.out.println("Total words:"+words.size());
        
        for(String word:words) {
            set.add(word);
        }
        
        System.out.println("Total different words: "+set.getSize()); 
    }
    
    long endTime = System.nanoTime();
    
    return (endTime - startTime)/ 1000000000.0;
}

public static void main(String[] args) {
      String filename = "pride-and-prejudice.txt";
      BSTSet<String> bst = new BSTSet<String>();
      double time1 = testSet(bst,filename);
      System.out.println("BST set:"+time1+"s"); // 0.3
      
      System.out.println();
      
      LinkedListSet<String> linkedListSet = new LinkedListSet<>();
      double time2 = testSet(linkedListSet, filename);
      System.out.println("LinkedList set:"+time2+"s"); // 4.0355  
}

2. leetcode中與集合有關(guān)的問題

804

國際摩爾斯密碼定義一種標準編碼方式，將每個字母對應(yīng)于一個由一系列點和短線組成的字符串，比如: "a" 對應(yīng) ".-", "b" 對應(yīng) "-...", "c" 對應(yīng) "-.-.", 等等。
所有26個英文字母對應(yīng)的摩爾斯密碼表如下：
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
給定一個單詞列表，每個單詞可以寫成每個字母對應(yīng)摩爾斯密碼的組合。例如，"cab" 可以寫成 "-.-..--..."，(即 "-.-." + "-..." + ".-"字符串的結(jié)合)。我們將這樣一個連接過程稱作單詞翻譯。不同的單詞有可能被翻譯為相同的摩爾斯密碼，要求返回單詞列表中不同摩爾斯密碼的數(shù)量。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-morse-code-words
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

使用集合很容易解答該題，遍歷單詞列表，將每個單詞的翻譯結(jié)果放入一個集合中，由于集合不能存放相同的元素，因此，遍歷完單詞列表后，集合中元素的數(shù)量即為不同摩爾斯密碼的數(shù)量。

應(yīng)用Java集成的TreeSet類

 import java.util.TreeSet;

 // leetcode 804
 public class Solution {
      public int uniqueMorseRepresentations(String[] words) {
          String[] codes = {".-","-...","-.-.","-..",".","..-.",
                  "--.","....","..",".---","-.-",".-..","--","-.",
                  "---",".--.","--.-",".-.","...","-","..-","...-",
                  ".--","-..-","-.--","--.."};
          TreeSet<String> treeSet = new TreeSet<>();
          for(String word:words) {
              StringBuilder res = new StringBuilder();
              for(int i=0;i<word.length();i++) {
                  // 將單詞索引為i位置的字母翻譯成摩爾斯密碼，追加到翻譯結(jié)果中
                  res.append(codes[word.charAt(i)-'a']);
              }
              treeSet.add(res.toString());
          }
          return treeSet.size();
      }
 }

使用上一節(jié)中自己創(chuàng)建的Set類

  import java.util.Comparator;
  import java.util.LinkedList;
  import java.util.Queue;
  import java.util.Stack;

  public class Solution {
          public int uniqueMorseRepresentations(String[] words) {
           String[] codes = {".-","-...","-.-.","-..",".","..-.",
                   "--.","....","..",".---","-.-",".-..","--","-.",
                   "---",".--.","--.-",".-.","...","-","..-","...-",
                   ".--","-..-","-.--","--.."};
           BSTSet<String> set = new BSTSet<>();
           for(String word:words) {
               StringBuilder res = new StringBuilder();
               for(int i=0;i<word.length();i++) {
                   // 將單詞索引為i位置的字母翻譯成摩爾斯密碼，追加到翻譯結(jié)果中
                   res.append(codes[word.charAt(i)-'a']);
               }
               set.add(res.toString());
           }
           return set.getSize();
       }
  }

349

給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2]
示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [9,4]
說明:

輸出結(jié)果中的每個元素一定是唯一的。
我們可以不考慮輸出結(jié)果的順序。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/intersection-of-two-arrays
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

使用基于二分搜索樹構(gòu)造的集合類解決該問題：

  class Solution {

      public int[] intersection(int[] nums1, int[] nums2) {
          BSTSet<Integer> bstSet = new BSTSet<>();
          // 先將第一個數(shù)組中的元素添加到集合中
          for(int num:nums1) {
              bstSet.add(num);
          }
          ArrayList<Integer> arr = new ArrayList<>();
          for(int num:nums2) {
              // 遍歷第二個數(shù)組中的所有元素，如果存在于集合中，則將該元素添加到數(shù)組列表中
              // 同時從集合中移除該元素
              if(bstSet.contains(num)) {
                  arr.add(num);
                  bstSet.remove(num);
              }
          }
          int[] res = new int[arr.size()];
          for(int i = 0;i<arr.size();i++) {
              res[i] = arr.get(i);
          }
          return res;
      }
  }

3. 映射

映射（Map）是一種存儲（鍵，值）數(shù)據(jù)對的數(shù)據(jù)結(jié)構(gòu)（key,value），鍵在映射中是不可重復(fù)的，通過鍵（key）來尋找值（value）。映射在實際生活中同樣具有廣泛的應(yīng)用：

字典中一個單詞對應(yīng)一個釋義
名冊中一個身份證號對應(yīng)一個人
車輛管理中一個車牌對應(yīng)一輛車

回顧之前介紹的鏈表和二分搜索樹的結(jié)構(gòu)：

    // 鏈表中的節(jié)點結(jié)構(gòu)            // 二分搜索樹中的節(jié)點結(jié)構(gòu)
    class Node{                  class Node{
        E e;                         E e;
        Node next;                   Node left;
    }                                Node right;
                                 }

很容易用這樣的結(jié)構(gòu)來實現(xiàn)映射機制，只需在節(jié)點中存儲一對數(shù)據(jù)即可：

    // 存儲鍵值對的鏈表                  // 存儲鍵值對的二分搜索樹
    class Node{                        class Node{
        K key;                            K key;
        V value;                          V value;
        Node next;                        Node left;
    }                                     Node right;
                                        }

一個Map應(yīng)該包含如下基本接口：

    public interface Map<K,V> {
        // 1. 獲取map中鍵值對個數(shù)
        public int getSize();
        // 2. 判斷map是否為空
        public boolean isEmpty();
        // 3. 添加鍵值對
        public void add(K key,V value);
        // 4. 刪除key對應(yīng)的鍵值對，返回value
        public V remove(K key);
        // 5. 更新key對應(yīng)的value
        public void set(K key,V value);
        // 6. 查詢key對應(yīng)的值
        public V get(K key);
        // 7. 判斷是否包含指定的key
        public boolean contains(K key);
    }

3.1 使用鏈表實現(xiàn)Map

首先使用鏈表來實現(xiàn)Map，對鏈表節(jié)點結(jié)構(gòu)進行修改，注意增加泛型支持：

  public class LinkedListMap<K,V> implements Map<K,V> {
      // 私有結(jié)點類，存儲鍵值對
      private class Node{
          private K key;
          private V value;
          private Node next;
          
          public Node(K key, V value, Node next) {
              this.key = key;
              this.value = value;
              this.next = next;
          }
          
          public Node(K key,V value){
              this(key,value,null);
          }
          
          public Node() {
              this(null,null,null);
          }
          
          @Override
          public String toString() {
              return "Key: "+key.toString()+"Value:"+value.toString();
          }
      }
      
      private Node dummyHead;
      private int size;
  }

簡單函數(shù)的實現(xiàn)

      // 1. 獲取map中鍵值對個數(shù)
      public int getSize(){
          return size;
      }
      
      // 2. 判斷map是否為空
      public boolean isEmpty() {
          return size == 0;
      }
      // 私有成員函數(shù)，根據(jù)key找到所在節(jié)點
      private Node getNode(K key) {
          Node cur = dummyHead.next;
          while(cur!=null) {
              if(cur.key.equals(key)) {
                  return cur;
              }
              cur = cur.next;
          }
          return null;
      }

根據(jù)鍵查詢

// 6. 判斷是否包含指定的key
@Override
public boolean contains(K key) {
    Node node = getNode(key);
    return node != null;
}

// 7. 查詢key對應(yīng)的值
@Override
public V get(K key) {
    Node node = getNode(key);
    return node.value;
}

更新/修改

  // 5. 更新key對應(yīng)的value
  @Override
  public void set(K key, V value) {
      Node node = getNode(key);
      
      if(node!=null) {
          node.value = value;
          Node preNode = dummyHead.next;
          while(preNode.next!=null) {
              // 找到待更新結(jié)點的前一結(jié)點
              if(preNode.next.key.equals(key)) {
                  node.next = preNode.next.next;
                  preNode.next = node;
                  return;
              }
              preNode = preNode.next;
          }
      }
      // node.value = value; // 需事先判斷Map中是否存在該鍵
  }

添加元素

  // 3. 添加新的鍵值對
  @Override
  public void add(K key, V value) {
      
      if(contains(key)) { // 如果已包含該鍵，更新該鍵對應(yīng)的值
          set(key,value);
      }
      else { // 如果不包含該鍵，添加到鏈表頭
          Node node = new Node(key,value);
          node.next = dummyHead.next;
          dummyHead.next = node;
          size++;
      }
  }

刪除元素

  // 4. 刪除key對應(yīng)的鍵值對，返回value
  @Override
  public V remove(K key) {
      Node pre = dummyHead;
      Node delNode = new Node();
      // 從虛擬頭節(jié)點出發(fā)，找到待刪除元素的前一節(jié)點
      while(pre.next!=null) {
          if(pre.next.key.equals(key))
              break;
          pre = pre.next;
      }
      // 如果找到的前一節(jié)點不是最后一個元素，則執(zhí)行刪除操作
      if(pre.next!=null) {
          delNode = pre.next;
          pre.next = delNode.next;
          delNode.next = null;
          size --;
      }
      return delNode.value;
  }

3.2 leetcode中與Map相關(guān)的問題

給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
說明：

輸出結(jié)果中每個元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個數(shù)組中出現(xiàn)的次數(shù)一致。
我們可以不考慮輸出結(jié)果的順序。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

利用基于鏈表構(gòu)造的映射類來解決問題

    public class Solution {
      public static int[] intersect(int[] nums1, int[] nums2) {
          LinkedListMap<Integer,Integer> linkedListMap = new LinkedListMap<Integer,Integer>();
          // 遍歷第一個數(shù)組中的元素，將元素及其對應(yīng)出現(xiàn)的次數(shù)存入映射中
          for(int num:nums1) {
              // 如果是之前添加過的元素，將元素出現(xiàn)的次數(shù)+1
              if(linkedListMap.contains(num)) {
                  linkedListMap.set(num, linkedListMap.get(num)+1);
              }
              // 如果之前沒有添加過，以出現(xiàn)次數(shù)為1添加進映射中
              else
                  linkedListMap.add(num, 1);
          }
          
          ArrayList<Integer> arr = new ArrayList<>();
          for(int num:nums2) {
              // 遍歷第二個數(shù)組中的元素，如果包含在映射中，加入數(shù)組 列表中
              if(linkedListMap.contains(num)) {
                  // 如果該元素的次數(shù)大于1，加入數(shù)組列表，同時將出現(xiàn)次數(shù)減1
                  if(linkedListMap.get(num)>=1) {
                      arr.add(num);
                      linkedListMap.set(num, linkedListMap.get(num)-1);
                  }
                  // 如果該元素次數(shù)是0，則將其從映射中移除
                  else
                      linkedListMap.remove(num);
              }
          }
          int[] res = new int[arr.size()];
          for(int i = 0;i<arr.size();i++) {
              res[i] = arr.get(i);
          }
          return res;
      }
  }

3.3 使用二分搜索樹實現(xiàn)Map

支持泛型的二分搜索樹基本結(jié)構(gòu)，注意鍵的可比較性

  public class BSTMap<K extends Comparable<K>,V> implements Map<K,V> {
      // 私有結(jié)點類
      private class Node{
          private K key;
          private V value;
          private Node left,right;
          public Node(K key, V value) {
              this.key = key;
              this.value = value;
              left = null;
              right = null;
          }
          
          @Override
          public String toString() {
              return "Key: "+key.toString()+"Value:"+value.toString();
          }
      }
      private Node root;
      private int size;
      
      public BSTMap() {
          root = null;
          size = 0;
      }
      
      @Override
      public int getSize() {
          return size;
      }
      
      @Override
      public boolean isEmpty() {
          return size == 0;
      }
  }

添加元素

  // 向二分搜索樹中添加新的元素（key,value）
  @Override
  public void add(K key, V value) {
      root = add(root,key,value);
  }
  
  // 私有添加方法，遞歸向以node為根結(jié)點的二分搜索樹中添加鍵值對
  // 返回插入新結(jié)點后二分搜索樹的根
  private Node add(Node node,K key,V value) {
      if(node==null) {
          node = new Node(key,value);
          size++;
          return node;
      }
      if(node.key.compareTo(key)>0) {
          node.left = add(node.left,key,value);
      }
      else if(node.key.compareTo(key)<0) {
          node.right = add(node.right,key,value);
      }
      else { // node.key.compareTo(key)==0
          // 如果已存在該元素，做更新操作
          node.value = value;
      }
      return node;
  }

查詢操作

  // 返回以node為根節(jié)點的二分搜索樹中，key所在的節(jié)點
  private Node getNode(Node node,K key) {
      if(node==null) {
          return null;
      }
      if(node.key.compareTo(key)>0) {
          return getNode(node.left,key);
      }
      else if(node.key.compareTo(key)<0) {
          return getNode(node.right,key);
      }
      else { // node.key.compareTo(key)==0
          return node;
      }
  }
  
  @Override
  public boolean contains(K key) {
      return getNode(root,key)!=null;
  }
  
  @Override
  public V get(K key) {
      Node node = getNode(root,key);
      return (node == null)?null:node.value;
  }
  // 返回以node為根的二分搜索樹的最小值所在的節(jié)點
  private Node minimize(Node node) {
      if(node.left==null) {
          return node;
      }
      return minimize(node.left);
  }

修改/更新

  @Override
  public void set(K key, V newValue) {
      Node node = getNode(root,key);
      if(node==null)
          throw new IllegalArgumentException(key+" doesn't exist!");
      node.value = newValue;
  }

刪除

  // 刪除掉以node為根的二分搜索樹中的最小節(jié)點
  // 返回刪除節(jié)點后新的二分搜索樹的根
  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;
  }
  // 從二分搜索樹中刪除鍵為key的節(jié)點
  @Override
  public V remove(K key) {
      Node node = getNode(root,key);
      if(node!=null) {
          root = remove(root,key);
      }
      return node.value;
  }

  // 刪除掉以node為根的二分搜索樹中鍵為key的結(jié)點
  // 返回刪除節(jié)點后新的二分搜索樹的根
  private Node remove(Node node,K key) {
      if(node==null) {
          return null;
      }
      if(node.key.compareTo(key)>0) {
          node.left = remove(node.left,key);
          return node;
      }
      else if(node.key.compareTo(key)<0) {
          node.right = remove(node.right,key);
          return node;
      }
      else { // node.key.compareTo(key)==0
          // 待刪除結(jié)點右子樹為空的情況
          if(node.right==null) {
              Node leftNode = node.left;
              node.left = null;
              size--;
              return leftNode;
          }
          // 待刪除結(jié)點左子樹為空的情況
          if(node.left==null) {
              Node rightNode = node.right;
              node.right = null;
              size--;
              return rightNode;
          }
          // 待刪除節(jié)點左右子樹均不為空的情況

          // 找到比待刪除節(jié)點大的最小節(jié)點, 即待刪除節(jié)點右子樹的最小節(jié)點
          // 用這個節(jié)點頂替待刪除節(jié)點的位置
          Node successor = minimize(node.right);
          successor.right = removeMin(node.right);
          successor.left = node.left;
          
          node.left = node.right = null;
          return successor;
      }
  }

3.4 兩種底層實現(xiàn)的比較

    import java.util.ArrayList;

    public class Main {

        private static double testMap(Map<String, Integer> map, String filename){

            long startTime = System.nanoTime();

            System.out.println(filename);
            ArrayList<String> words = new ArrayList<>();
            if(FileOperation.readFile(filename, words)) {
                System.out.println("Total words: " + words.size());

                for (String word : words){
                    if(map.contains(word))
                        map.set(word, map.get(word) + 1);
                    else
                        map.add(word, 1);
                }

                System.out.println("Total different words: " + map.getSize());
                System.out.println("Frequency of PRIDE: " + map.get("pride"));
                System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
            }

            long endTime = System.nanoTime();

            return (endTime - startTime) / 1000000000.0;
        }

        public static void main(String[] args) {

            String filename = "pride-and-prejudice.txt";

            BSTMap<String, Integer> bstMap = new BSTMap<>();
            double time1 = testMap(bstMap, filename);
            System.out.println("BST Map: " + time1 + " s"); // 0.1520 s

            System.out.println();

            LinkedListMap<String, Integer> linkedListMap = new LinkedListMap<>();
            double time2 = testMap(linkedListMap, filename);
            System.out.println("Linked List Map: " + time2 + " s"); // 9.7194 s

        }
    }

4. 總結(jié)

本節(jié)課主要學(xué)習(xí)了集合與映射兩種高級數(shù)據(jù)結(jié)構(gòu)，分別以鏈表和二分搜索樹為底層結(jié)構(gòu)實現(xiàn)了這兩種數(shù)據(jù)結(jié)構(gòu)，并對存取效率進行了比較，存取效率與底層實現(xiàn)結(jié)構(gòu)相關(guān)，以二分搜索樹為底層結(jié)構(gòu)的數(shù)據(jù)存取效率更高，這是因為二分搜索樹的存取時間復(fù)雜度為 $O(logn)$ ，遠小于鏈表的時間復(fù)雜度 $O(n)$ 。集合與映射在實際生活中的應(yīng)用非常廣泛，可以用來實現(xiàn)很多復(fù)雜任務(wù)。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)6-集合與映射

玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)6-集合與映射

1. 集合

1.1 基于二分搜索樹的集合實現(xiàn)

1.2 基于鏈表的集合實現(xiàn)

1.3 時間復(fù)雜度分析

2. leetcode中與集合有關(guān)的問題

804

349

3. 映射

3.1 使用鏈表實現(xiàn)Map

3.2 leetcode中與Map相關(guān)的問題

3.3 使用二分搜索樹實現(xiàn)Map

3.4 兩種底層實現(xiàn)的比較

4. 總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)6-集合與映射

1. 集合

1.1 基于二分搜索樹的集合實現(xiàn)

1.2 基于鏈表的集合實現(xiàn)

1.3 時間復(fù)雜度分析

2. leetcode中與集合有關(guān)的問題

804

349

3. 映射

3.1 使用鏈表實現(xiàn)Map

3.2 leetcode中與Map相關(guān)的問題

3.3 使用二分搜索樹實現(xiàn)Map

3.4 兩種底層實現(xiàn)的比較

4. 總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av