什么是二叉搜索树?
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
二叉搜索树的优缺点
- 二叉搜索树既有链表的好处，又有数组数组的好处，链表的好处是插入元素和删除元素相对方便，但是查找元素非常慢，而数组的好处的是查找元素非常快，但是插入元素和删除元素相对较慢，而二叉搜索树既有链表的优势，又有数组的优势，二叉搜索树的插入操作和查找操作的平均运行时间都是指数级别的。
但是二叉搜索树最大的缺点就是就是它会退化，什么是退化呢，举一个例子，当插入的数值一个有序数组时，假设依次插入这些值时{1，2，3，4，5，6，7，8}，二叉搜索树就会变成这个样子，
如果一个二叉搜索树退化成了如图的样子，那他不就是一个链表了吗，当要搜索8这个元素时，会一直在右子树 上进行搜索，时间复杂度为O(N),如果要插入一个大于8的元素，时间复杂度也是O(N),这就是二叉搜索树最为致 命的缺点，AVL书对二叉搜索树进行了优化。
二叉搜索树的Java实现
二叉搜索树的节点
<br />这个Node节点包含了五个字段，这个key是泛型，是指存入的关键字，二叉搜索树的排序就是根据这个字段进 行排序的，这个value字段也是泛型，是指关键字多对应的值，然后还有两个字段left和right，是指当前节点的<br />左指针和右指针，最后一个字段N是指当前节点对应的子树的节点数量，这个字段有没有不重要，最重要的还是 前四个字段。
二叉搜索树所对应的java类的结构
二叉搜索树的实现类有一个内部类，也就是之前咱们介绍的Node节点，还有一个字段，也就是根节点，其他的全是对应的方法，我们只介绍几个比较重要的方法，其中包括插入方法，删除方法，查询最值方法，以及删除最小值方法。
插入操作
假设我们有一个如上图的二叉树，现在要插入7这个元素，那我们需要怎么做呢，其实仔细想一下也不太难，我们想一下二叉搜索树有什么性质，当一个二叉搜索树不为空时，一个节点的左子树大于这个节点的值，这个节点的右子树大于这个节点的值，当我们需要插入一个节点的值时，我们不断跟当前节点的值进行比较，当插入的节点大于当前的值，当前节点指向右子树，当插入的节点小于当前节点的值，当前节点指向左子树，就这样重复下去，知道找到一个空的位置，然后进行填充，下面我们看一下图来直观感受一下插入值为7节点的操作过程。
最开始跟根节点进行比较，由于根节点的值为5，而插入的节点值为7，所以当前节点指向右子树，指向值为6的这个节点，继续进行比较，
由于插入的节点还是大于当前节点的值所以，当前节点继续指向右子树10，继续进行比较，
当当前节点指向9的时候，由于插入节点比9小，当前节点应该指向左子树，但是当前节点的左子树为null，所以插入节点的位置确定了，就是当前节点的左子树。
就就是插入节点的全过程，下面我们来看一下如何用代码是实现。
public void put(Key key, Value value) { root = put(root, key, value); }
private Node put(Node x, Key key, Value value) { if(x == null) return new Node(key, value, 1);
int cmp=key.compareTo(x.key);
if(cmp < 0) x.left = put(x.left, key, value);
else if(cmp > 0) x.right = put(x.right, key, value);
else
x.val = value;
x.N = size(x.left) + size(x.right) + 1;
return x; }
查找最值
由于查找最大值和查找最小值的思想很想，所以我们这里只介绍一下如何查询最大值，我们想一下，如何查找一个二叉搜索树的最大值呢，这时又会利用到我们二叉搜索树的性质，二叉树的右子树的值大于二叉树左子树的值，所以我们只需要一直遍历右子树的右节点为null，即意味着我们找到了我们的最大值。
下面来看一下代码如何实现。
public Key max() { return max(root).key; }
private Node max(Node node) {
if(node.right == null) return node;
return max(node.right); }
删除最小值
首先我们要明确一点，一棵树的最小值一定在树的最左端，我们来看一下一颗二叉搜索树
这颗二叉搜索树的最小值为1，我们会发现，一个二叉搜索树最小值对应的节点的左子树肯定为null，因为如果左子树不为null，说明还有比它更小的，所以我们得出一个结论，一个二叉搜索树最小值对应的节点的左子树一定为null，知道这个我们就好办了，我们只需让最小值所对应的节点的右子树指向最小值节点的父节点。
删除后应该这样子的，到时候1这个节点应该会自动回收。
那我们看一下代码
public void deleteMin() {
root = deleteMin(root); }
public Node deleteMin(Node x) {
if(x.left == null)
return x.right;
x.left = deleteMin(x.left);
x.N = size(x.left) + size(x.right) + 1;
return x; }
删除操作
删除操作应该是二叉搜索树里面一个最为复杂的操作了，别急，我们一步一步来，那我们要想先删除节点，那我们是不是得首先会找到那个节点，这个查找操作也不是特别难，就是跟当前节点进行比较，当我们找到我们要删除的那个节点时，如果我们直接把这个节点进行删除而不进行其他任何操作时，那原本的二叉搜索树就会变为好几颗树，我们不想这样，那需要如何进行操作呢，我们需要找到一个节点去替换我们要删除的这个节点，那这个节点肯定不是随便去找的，因为他需要满足二叉搜索树的性质，那我们如何去找这样一个节点呢，那我们想一下，当这个节点是删除节点的右子树的最小值所对应的节点，首先左子树所有的节点肯定比这个节点所对应的值要小，有二叉搜索树性质可知，右子树的值肯定要大于左子树的值，而这个节点又是右子树的最小值，所以当这个节点替换删除节点时，右子树肯定是大于他的，所以满足了二叉搜索树的性质，那我们举一个例子来看一下。
假设我们要删除6这个节点，首先我们找到6的右子树的最小值为7，当7这个节点去替换6这个节点时，我们会发现完全满足二叉搜索树的所有性质。最后的最后，由于我们把7这个节点替换到6这个节点上面了，我们需要把7这个节点删除了，要不就相当于多了一个节点。
下面我们来看一下代码
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);
else if(cmp > 0)
x.right = delete(x.right, key);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.N = size(x.left) + size(x.right) + 1;return x; }
若有收获，就点个赞吧
0 人点赞
