集册 Java实例教程 以对称顺序实现二进制搜索树。

以对称顺序实现二进制搜索树。

欢马劈雪     最近更新时间:2020-01-02 10:19:05

438
以对称顺序实现二进制搜索树。
import java.util.LinkedList;

import java.util.Queue;/**from 时 代 J a v a 公 众 号 - N o w J a v  a . c o m**/


class BinarySearchTree<Key extends Comparable<Key>, Value> {

  private Node root;


  class Node {

    private Key key;

    private Value val;


    private Node left, right;// left & right subtrees

    private int count = 1;


    public Node(Key k, Value v) {

      this.key = k;/**from nowjava.com - 时  代  Java**/

      this.val = v;

    }


    @Override

    public String toString() {

      return "" + key;

    }

  }


  public boolean isEmpty() {

    return size() == 0;

  }


  public int size() {

    return size(root);

  }


  private int size(Node x) {

    if (x == null)

      return 0;

    return x.count;

  }


  public boolean contains(Key k) {

    return get(k) != null;

  }


  public Value get(Key key) {

    Node x = root;


    while (x != null) {

      int cmp = key.compareTo(x.key);


      if (cmp < 0)

        x = x.left;

      else if (cmp > 0)

        x = x.right;

      else

        return x.val;

    }


    return null;

  }


  public void put(Key key, Value val) {

    root = put(root, key, val);

  }


  private Node put(Node x, Key key, Value val) {

    if (x == null)

      return new Node(key, val);


    int cmp = key.compareTo(x.key);


    if (cmp < 0)

      x.left = put(x.left, key, val);

    else if (cmp > 0)

      x.right = put(x.right, key, val);

    else

      x.val = val; // found node


    x.count = 1 + size(x.left) + size(x.right);

    return x;

  }


  public int height() {

    return height(root);

  }


  private int height(Node x) {

    if (x == null)

      return -1;

    return 1 + Math.max(height(x.left), height(x.right));

  }


  public Key min() {

    if (isEmpty())

      return null;

    return min(root).key;

  }


  private Node min(Node x) {

    if (x.left == null)

      return x;

    return min(x.left);

  }


  public Key max() {

    if (isEmpty())

      return null;

    return max(root).key;

  }


  private Node max(Node x) {

    if (x.right == null)

      return x;


    return max(x.right);

  }


  public Key select(int k) {

    if (k < 0 || k >= size())

      return null;


    Node x = select(root, k);

    return x.key;

  }


  private Node select(Node x, int k) {

    if (x == null)

      return null;


    int t = size(x.left);

    if (t > k)

      return select(x.left, k);

    else if (t < k)

      return select(x.right, k - t - 1);

    else

      return x;

  }


  public int rank(Key key) {

    return rank(key, root);

  }


  private int rank(Key key, Node x) {

    if (x == null)

      return 0;


    int cmp = key.compareTo(x.key);

    if (cmp < 0)

      return rank(key, x.left);

    else if (cmp > 0)

      return 1 + size(x.left) + rank(key, x.right);

    else

      return size(x.left);

  }


  public void deleteMin() {

    if (isEmpty())

      return;

    root = deleteMin(root);

  }


  private Node deleteMin(Node x) {

    if (x.left == null)

      return x.right;


    x.left = deleteMin(x.left);

    x.count = size(x.left) + size(x.right) + 1;

    return x;

  }


  public void deleteMax() {

    if (isEmpty())

      return;

    root = deleteMax(root);

  }


  private Node deleteMax(Node x) {

    if (x.right == null)

      return x.left;


    x.right = deleteMax(x.right);

    x.count = size(x.left) + size(x.right) + 1;

    return x;

  }


  public void delete(Key key) {

    root = delete(root, key);

  }


  private Node delete(Node x, Key key) {

    if (x == null)

      return null;


    int cmp = key.compareTo(x.key);

    if (cmp < 0)

      x.left = delete(x.left, key); // delete left

    else if (cmp > 0)

      x.right = delete(x.right, key); // delete right

    else {

      if (x.right == null)

        return x.left;


      if (x.left == null)

        return x.right;


      Node t = x;

      x = min(t.right);

      x.right = deleteMin(t.right);

      x.left = t.left;

    }

    x.count = size(x.left) + size(x.right) + 1;

    return x;

  }


  public Iterable<Key> keys() {

    Queue<Key> q = new LinkedList<Key>();

    inorder(root, q);

    return q;

  }


  private void inorder(Node x, Queue<Key> q) {

    
展开阅读全文