【数据结构与算法】系列八 - 二叉搜索树

在 n 个动态的整数中搜索某个整数？（查看其是否存在）

假设使用动态数组存放元素，从第 0 个位置开始遍历搜索，平均时间复杂度：O(n)。

如果维护一个有序的动态数组，使用二分搜索，最坏时间复杂度：O(logn)。但是添加、删除的平均时间复杂度是 O(n)。

针对这个需求，有没有更好的方案？

使用二叉搜索树，添加、删除、搜索的最坏时间复杂度均可优化至：O(logn)。

一、二叉搜索树

二叉搜索树（Binary Search Tree，简称：BST）是二叉树的一种，是应用非常广泛的一种二叉树。又被称为：二叉查找树、二叉排序树。

特点：

任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一棵二叉搜索树

二叉搜索树存储的元素必须具备可比较性，比如int、double等。如果是自定义类型，需要指定比较方式（比如比较Person的age），但是元素不允许为null。

二叉搜索树可以大大提高搜索数据的效率。

二、接口设计

int size() // 元素的数量
boolean isEmpty() // 是否为空
void clear() // 清空所有元素
void add(E element) // 添加元素
void remove(E element) // 删除元素
boolean contains(E element) // 是否包含某元素

需要注意的是二叉搜索树的元素没有索引的概念，因为索引是无效且无意义的。

2.1. 添加节点

比如添加12、1

添加步骤：

找到父节点parent
创建新节点node
parent.left = node 或者 parent.right = node

代码：

// 添加节点
public void add(E element) {
  // 如果元素为null则抛出异常
  elementNotNullCheck(element);
  
  // 添加第一个节点（根节点）
  if (root == null) {
    root = new Node<>(element, null);
    size++;
    return;
  }
  
  // 添加的不是第一个节点
  // 找到父节点
  Node<E> parent = root;
  Node<E> node = root;
  int cmp = 0;
  do {
    cmp = compare(element, node.element);
    parent = node;
    if (cmp > 0) {
      node = node.right;
    } else if (cmp < 0) {
      node = node.left;
    } else { // 相等
      node.element = element;
      return;
    }
  } while (node != null);

  // 看看插入到父节点的哪个位置
  Node<E> newNode = new Node<>(element, parent);
  if (cmp > 0) {
    parent.right = newNode;
  } else {
    parent.left = newNode;
  }
  size++;
}

// 非空检查
private void elementNotNullCheck(E element) {
  if (element == null) {
    throw new IllegalArgumentException("element must not be null");
  }
}

// 构造节点
private static class Node<E> {
  E element;
  Node<E> left;
  Node<E> right;
  Node<E> parent;
  public Node(E element, Node<E> parent) {
    this.element = element;
    this.parent = parent;
  }
}

遇到值相等的元素该如何处理？建议覆盖旧的值，因为比较自定义对象有可能仅仅是参与比较的元素值是相等的，其他属性都不一样。

2.2. 元素的比较方案设计

允许外界传入一个Comparator自定义比较方案。
如果没有传入Comparator，强制认定元素实现了Comparable接口。

public BinarySearchTree() {
  this(null);
}

public BinarySearchTree(Comparator<E> comparator) {
  this.comparator = comparator;
}

/**
 * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于0，代表e1小于e2
 */
private int compare(E e1, E e2) {
  if (comparator != null) {
    return comparator.compare(e1, e2);
  }
  return ((Comparable<E>)e1).compareTo(e2);
}

2.3. 打印二叉树

推荐工具类：https://github.com/CoderMJLee/BinaryTrees

使用步骤：

实现BinaryTreeInfo接口
调用打印API：BinaryTrees.println(bst);

推荐网站：