二叉查找樹（Binary Search Tree）

支持動態(tài)數(shù)據(jù)集合的快速插入刪除查找

要求？節(jié)點(diǎn)值：左<父<右

【二叉排序樹】中序遍歷二叉查找樹可輸出有序的數(shù)據(jù)序列，時(shí)間復(fù)雜度O（n）

時(shí)間復(fù)雜度與樹的高度成正比O（height）

查找

從根節(jié)點(diǎn)開始依次比較要查找的數(shù)據(jù)和節(jié)點(diǎn)大小關(guā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;(根結(jié)點(diǎn)的值<查找數(shù)據(jù)則進(jìn)入左子樹遞歸查找)
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

插入

類似查找，插入數(shù)據(jù)一般在葉子節(jié)點(diǎn)上

刪除

• 刪除的節(jié)點(diǎn)無子節(jié)點(diǎn)（直接將指向該節(jié)點(diǎn)的指針置為null）
• 刪除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)（子承父位）
• 刪除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)（替換成右子樹中的最小節(jié)點(diǎn)）

or 將要?jiǎng)h除的節(jié)點(diǎn)特殊標(biāo)記

支持重復(fù)數(shù)據(jù)

存儲對象包含很多字段=鍵值（key）構(gòu)建+衛(wèi)星數(shù)據(jù)

• 把值相同的數(shù)據(jù)存儲在同一節(jié)點(diǎn)

• 插入數(shù)據(jù)與節(jié)點(diǎn)值相同，則當(dāng)作略大值處理放到節(jié)點(diǎn)的右子樹；遇到值相同的節(jié)點(diǎn)不停止查找，在右子樹中查找直到找到葉子節(jié)點(diǎn)