二叉查找樹

它不僅僅支持快速查找一個(gè)數(shù)據(jù)神凑，還支持快速插入、刪除一個(gè)數(shù)據(jù)何吝。這些都依賴于二叉查找樹的特殊結(jié)構(gòu)溉委。二叉查找樹要求，在樹中的任意一個(gè)節(jié)點(diǎn)岔霸，其左子樹中的每個(gè)節(jié)點(diǎn)的值薛躬，都要小于這個(gè)節(jié)點(diǎn)的值，而右子樹節(jié)點(diǎn)的值都大于這個(gè)節(jié)點(diǎn)的值呆细。

1.二叉查找樹的查找操作

我們先取根節(jié)點(diǎn)，如果它等于我們要查找的數(shù)據(jù)八匠，那就返回絮爷。如果要查找的數(shù)據(jù)比根節(jié)點(diǎn)的值小，那就在左子樹中遞歸查找梨树；如果要查找的數(shù)據(jù)比根節(jié)點(diǎn)的值大坑夯，那就在右子樹中遞歸查找。

public class BinarySearchTree {
  private Node tree;

  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

2.二叉查找樹的插入操作

如果要插入的數(shù)據(jù)比節(jié)點(diǎn)的數(shù)據(jù)大抡四，并且節(jié)點(diǎn)的右子樹為空柜蜈，就將新數(shù)據(jù)直接插到右子節(jié)點(diǎn)的位置；如果不為空指巡，就再遞歸遍歷右子樹淑履，查找插入位置。同理藻雪，如果要插入的數(shù)據(jù)比節(jié)點(diǎn)數(shù)值小秘噪，并且節(jié)點(diǎn)的左子樹為空，就將新數(shù)據(jù)插入到左子節(jié)點(diǎn)的位置勉耀；如果不為空指煎，就再遞歸遍歷左子樹，查找插入位置便斥。

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }

  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

3. 二叉查找樹的刪除操作

二叉查找樹的查找至壤、插入操作都比較簡單易懂，但是它的刪除操作就比較復(fù)雜了枢纠。針對(duì)要?jiǎng)h除節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)的不同像街，我們需要分三種情況來處理。

1.如果要?jiǎng)h除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，我們只需要直接將父節(jié)點(diǎn)中宅广，指向要?jiǎng)h除節(jié)點(diǎn)的指針置為 null葫掉。
2.如果要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)（只有左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)），我們只需要更新父節(jié)點(diǎn)中跟狱，指向要?jiǎng)h除節(jié)點(diǎn)的指針俭厚，讓它指向要?jiǎng)h除節(jié)點(diǎn)的子節(jié)點(diǎn)就可以了。
3.如果要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)驶臊，這就比較復(fù)雜了挪挤。我們需要找到這個(gè)節(jié)點(diǎn)的右子樹中的最小節(jié)點(diǎn)，把它替換到要?jiǎng)h除的節(jié)點(diǎn)上关翎。然后再刪除掉這個(gè)最小節(jié)點(diǎn)扛门，因?yàn)樽钚」?jié)點(diǎn)肯定沒有左子節(jié)點(diǎn)（如果有左子結(jié)點(diǎn)，那就不是最小節(jié)點(diǎn)了）纵寝，所以论寨，我們可以應(yīng)用上面兩條規(guī)則來刪除這個(gè)最小節(jié)點(diǎn)。

public void delete(int data) {
  Node p = tree; // p 指向要?jiǎng)h除的節(jié)點(diǎn)爽茴，初始化指向根節(jié)點(diǎn)
  Node pp = null; // pp 記錄的是 p 的父節(jié)點(diǎn)
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 沒有找到

  // 要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
  if (p.left != null && p.right != null) { // 查找右子樹中最小節(jié)點(diǎn)
    Node minP = p.right;
    Node minPP = p; // minPP 表示 minP 的父節(jié)點(diǎn)
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 將 minP 的數(shù)據(jù)替換到 p 中
    p = minP; // 下面就變成了刪除 minP 了
    pp = minPP;
  }

  // 刪除節(jié)點(diǎn)是葉子節(jié)點(diǎn)或者僅有一個(gè)子節(jié)點(diǎn)
  Node child; // p 的子節(jié)點(diǎn)
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  if (pp == null) tree = child; // 刪除的是根節(jié)點(diǎn)
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

4. 二叉查找樹的其他操作

快速地查找最大節(jié)點(diǎn)和最小節(jié)點(diǎn)葬凳、前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。
中序遍歷二叉查找樹室奏，可以輸出有序的數(shù)據(jù)序列火焰，時(shí)間復(fù)雜度是 O(n)，非常高效

支持重復(fù)數(shù)據(jù)的二叉查找樹

在實(shí)際的軟件開發(fā)中胧沫，我們在二叉查找樹中存儲(chǔ)的昌简，是一個(gè)包含很多字段的對(duì)象。我們利用對(duì)象的某個(gè)字段作為鍵值（key）來構(gòu)建二叉查找樹绒怨。我們把對(duì)象中的其他字段叫作衛(wèi)星數(shù)據(jù)纯赎。

那如果存儲(chǔ)的兩個(gè)對(duì)象鍵值相同，這種情況該怎么處理呢窖逗？我這里有兩種解決方法址否。

第一種方法比較容易。

二叉查找樹中每一個(gè)節(jié)點(diǎn)不僅會(huì)存儲(chǔ)一個(gè)數(shù)據(jù)碎紊，因此我們通過鏈表和支持動(dòng)態(tài)擴(kuò)容的數(shù)組等數(shù)據(jù)結(jié)構(gòu)佑附，把值相同的數(shù)據(jù)都存儲(chǔ)在同一個(gè)節(jié)點(diǎn)上。

第二種方法比較不好理解仗考，不過更加優(yōu)雅音同。

每個(gè)節(jié)點(diǎn)仍然只存儲(chǔ)一個(gè)數(shù)據(jù)。在查找插入位置的過程中秃嗜，如果碰到一個(gè)節(jié)點(diǎn)的值权均，與要插入數(shù)據(jù)的值相同顿膨，我們就將這個(gè)要插入的數(shù)據(jù)放到這個(gè)節(jié)點(diǎn)的右子樹，也就是說叽赊，把這個(gè)新插入的數(shù)據(jù)當(dāng)作大于這個(gè)節(jié)點(diǎn)的值來處理恋沃。

當(dāng)要查找數(shù)據(jù)的時(shí)候，遇到值相同的節(jié)點(diǎn)必指，我們并不停止查找操作囊咏，而是繼續(xù)在右子樹中查找，直到遇到葉子節(jié)點(diǎn)塔橡，才停止梅割。這樣就可以把鍵值等于要查找值的所有節(jié)點(diǎn)都找出來。

對(duì)于刪除操作葛家，我們也需要先查找到每個(gè)要?jiǎng)h除的節(jié)點(diǎn)户辞，然后再按前面講的刪除操作的方法，依次刪除癞谒。

二叉查找樹的時(shí)間復(fù)雜度分析

如果根節(jié)點(diǎn)的左右子樹極度不平衡底燎，退化成了鏈表，那么查找的時(shí)間復(fù)雜度就變成了 O(n)弹砚。
如果二叉查找樹是一棵完全二叉樹（或滿二叉樹）书蚪，插入、刪除迅栅、查找操作的時(shí)間復(fù)雜度也比較穩(wěn)定，是 O(logn)晴玖。
一般情況下時(shí)間復(fù)雜度跟樹的高度成正比读存，也就是 O(height)

二叉樹比散列表的優(yōu)勢

第一，散列表中的數(shù)據(jù)是無序存儲(chǔ)的呕屎，如果要輸出有序的數(shù)據(jù)让簿，需要先進(jìn)行排序。而對(duì)于二叉查找樹來說秀睛，我們只需要中序遍歷尔当，就可以在 O(n) 的時(shí)間復(fù)雜度內(nèi)，輸出有序的數(shù)據(jù)序列蹂安。
第二椭迎，散列表擴(kuò)容耗時(shí)很多，而且當(dāng)遇到散列沖突時(shí)田盈，性能不穩(wěn)定畜号，盡管二叉查找樹的性能不穩(wěn)定，但是在工程中允瞧，我們最常用的平衡二叉查找樹的性能非常穩(wěn)定简软，時(shí)間復(fù)雜度穩(wěn)定在 O(logn)蛮拔。
第三，籠統(tǒng)地來說痹升，盡管散列表的查找等操作的時(shí)間復(fù)雜度是常量級(jí)建炫，但因?yàn)楣_突的存在，這個(gè)常量不一定比 logn 小疼蛾，所以實(shí)際的查找速度可能不一定比 O(logn) 快肛跌。加上哈希函數(shù)的耗時(shí)，也不一定就比平衡二叉查找樹的效率高据过。
第四惋砂，散列表的構(gòu)造比二叉查找樹要復(fù)雜，需要考慮的東西很多绳锅。比如散列函數(shù)的設(shè)計(jì)西饵、沖突解決辦法、擴(kuò)容鳞芙、縮容等眷柔。平衡二叉查找樹只需要考慮平衡性這一個(gè)問題，而且這個(gè)問題的解決方案比較成熟原朝、固定驯嘱。
最后，為了避免過多的散列沖突喳坠，散列表裝載因子不能太大鞠评，特別是基于開放尋址法解決沖突的散列表，不然會(huì)浪費(fèi)一定的存儲(chǔ)空間壕鹉。

二叉樹基礎(chǔ)下