二分搜索树， Binary Search Tree
特点
每个树节点的值：
- 必须大于左子树的所有节点的值，
- 必须小于右子树的所有节点的值。
- 树的叶子节点的左右子节点都为null（为了便于理解我这里这样假设。有些文章将这个null作为叶子节点。）
储存的数据：
- 必须具有可比较性（具体表现在K需要实现Comparable接口， 当然如果我们用hashcode方法，这个条件可以不要）
实现代码
public class BST<K extends Comparable<E>, V> {
private class Node {
// 定义私有类，对用户屏蔽
public K key;
public V value;
// 左右两个节点
public Node left;
public Node right;
// 定义我们的构造方法
public Node(K key, V value, Node left, Node right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
public Node(K key, V value) {
// 默认构造左右子节点都为空
this(key, value, null, null)
}
}
// 树根节点
private Node root;
// size 树的大小
private int size;
// 树的构造方法
public BST() {
root = null;
size = 0;
}
// 一些基本的方法
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
// 添加元素
public void add(K key, V value) {
// 树结构有着天然的递归性质， 我们使用递归去添加元素
root = add(root, key, value);
}
private Node add(Node node, K key, V value) {
if (node == null) {
// 递归结束条件， 已经遍历到了叶子节点的子节点了。在叶子节点的后面添加我们的新增节点。不要忘了维护size
size++;
return new Node(key, value);
}
if (key.compareTo(node.key) > 0) {
// 我们添加的key比我们当前找到的node的key 要大（注意这里的可比较性 -- > key > node.key） ， 说明我们要添加在当前找到的node的右边, 递归继续查找
node.right = add(node.right, key, value)
}else if (key.compareTo(node.key) < 0) {
node.left = add(node.left, key, value)
}else {
// 相等的情况，修改值。 当然其他处理方式也可以，比如放左放右或者
node.value = value;
}
// 最后不要忘记把我们的node return出去
return node;
}
// 删除节点
public V remove(K key) {
// 先查找出来，在删除
Node retNode = getNode(key);
if (retNode != null) {
root = remove(root, K key);
// 返回查找到的 node 的值
return retNode.value;
}
// 没找到返回null
return null;
}
private Node remove(Node node, K key) {
if (node == null) {
// 递归结束还没找到这个key的话，说明没有这个node
return null;
}
if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key)
}else if (key.compareTo(node.key) < 0) {
node.left = remove(node.left, key)
}else {
// 如果找到了这个key
// 分两种情况：
// 1、 找到的这个node不是是叶子节点，但是是左子节点或者有子节点有一个是null， 直接删除就好了，然后把不是null的子节点返回个出去就好了
// 2、 找到的这个node不是叶子节点，而且左子和右子节点都不为空， 这个时候， 我们可以找到待删除的node节点的后继（或者前驱）节点替代当前节点位置，在返回出去
这里有必要说一下后继和前驱节点的意思， 后继节点就是当前节点右子树所有节点当中的最小的节点
前驱节点就是当前节点左子树所有节点当中的最大的节点
// 实现代码
if (node.left == null) {
Node ret = node.right;
// 释放空间
node.right = null;
size--;
return ret;
}else if (node.right == null) {
Node ret = node.left;
// 释放空间
node.left = null;
size--;
return ret;
}else {
// 找到当前节点的后继节点
Node succeedNode = minimum(node.right);
succeedNode.left = node.left;
// 我们把删除node的后继节点之后的node.right作为这个后继节点的右子节点
succeedNode.right = remove(node.right, succeedNode.key)
node.left = node.right = null;
return succeedNode;
}
}
}
// 查找某个node， 整体和add很相似
private Node getNode(K key) {
if (key.compareTo(node.key) > 0) {
return getNode(node.right, key)
}else if (key.compareTo(node.key) < 0) {
return getNode(node.left, key)
}else {
return node;
}
}
// 找到节点的后继节点
private Node minimum(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
// 查看是否包含某个key
public boolean contains(K key) {
return contains(root, key)
}
private boolean contains(Node node, K key) {
if (node == null) {
return false;
}
if (key.compareTo(node.key) > 0) {
return contains(node.right, key)
}else if (key.compareTo(node.key) < 0) {
return contains(node.left, key)
}else {
return true;
}
}
}
- 可以看到， 我们上面的代码已经实现了二分搜索树的添加和删除，为了不使代码变得很沉长难读， 我把接下来的遍历方法写在了下面
- 对于树的遍历， 通常分为两种：
- 广度优先遍历： 广度优先遍历也称为层序遍历，是从树根节点逐层向下遍历，是对树的一个横向遍历操作
- 深度优先遍历：深度优先遍历分为 前序遍历， 中序遍历， 后序遍历
代码实现：
public class BST<K extends Comparable<E>, V> {
// 广度优先遍历， 我们直接使用java的队列实现, 就非常的简单
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty) {
Node node = queue.remove()
System.out.printLn(node.value)
if (node.left != null) {
queue.add(node.left)
}
if (node.right != null) {
queue.add(node.right)
}
}
// 深度优先遍历，无论是前序还是中序后序，其实都是同一种遍历方式， 只是在我们操作元素的时间段不同
// 当我们使用递归去遍历的时候， 任意一个节点都会经过三个过程，
// 1、刚开始遍历到当前节点（这个时候操作当前节点-->前序遍历）
// 2、遍历完当前节点的左子节点后回到当前节点 （这个时候操作当前节点-->中序遍历）
// 3、遍历完当前节点的右子节点后回到当前节点， 结束遍历。（这个时候操作当前节点-->后序遍历）
// 大家会发现中序遍历， 就是一个对key的排序过程
// 前序遍历
public void preOrder() {
preOrder(root);
}
private void preOrder(Node node) {
if (node == null) {
return;
}
Sysout.out.printLn(node.key);
preOrder(node.left);
preOrder(node.right);
}
}
// 中序遍历
public void inOrder() {
inOrder(root);
}
private void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left);
Sysout.out.printLn(node.key);
inOrder(node.right);
}
}
// 后序遍历
public void postOrder() {
postOrder(root);
}
private void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
Sysout.out.printLn(node.key);
}
}
- 这样我们就实现了一个简单的二分搜索树， 增删改查操作，均摊复杂度为O(log n) 级别。 log底为2。
- 但是我们的树在一些极端得情况下，比如我们故意插入的是一组有序的数据时 我们的树就会退化成一个链表，复杂度会变为O(n) 级别
- 在下一篇， 我们将会给它添加自平衡的能力， 使他成为一颗简单的AVL树
