二分搜索树的优势
-
高效
- 不仅可以查找数据;还可以高效地插入,删除数据-动态维护数据
-
可以方便的回答很多数据之间的关系问题
- min(最小值),max(最大值),floor(首次出现),ceil(最后一次出现),rank(排名),select(选择查询)
| 查找元素 | 插入元素 | 删除元素 | |
|---|---|---|---|
| 普通数组 | O(n) | O(n) | O(n) |
| 顺序数组 | O(logn) | O(n) | O(n) |
| 二分搜索树 | O(logn) | O(logn) | O(logn) |
特点
- 首先是一棵二叉树(不一定是完全二叉树)
- 每个节点的键值都大于左孩子(左子树的所有节点)
- 每个节点的键值都小于右孩子(右子树的所有节点)
- 以左右孩子为根的子树仍为二分搜索数
右孩子的值是不会超过 父节点的父节点的值的,如果超过的话,应该是作为父节点的父节点的右子树
二分搜索树Binary Search Tree
代码实现
二叉搜索树基本结构
内部维护了一个内部类,用于维护各个节点之间的关系
public class BST<K,E extends Comparable<E>> {
//二分搜索树内部的节点
private class Node{
E data;
Node left,right;
public Node(E data){
this.data = data;
this.left = null;
this.right = null;
}
}
//二分搜索树的大小
private int size;
//根元素
private Node root;
public BST() {
size = 0;
root = null;
}
}
基本方法
- 获取二叉搜索树的大小
- 判断是否为空
/**
* 获取二分搜索树的大小
* @return 二分搜索树的大小
*/
public int getSize(){
return size;
}
/**
* 判断树是否为空
* @return true:树为空 false:树不为空
*/
public boolean isEmpty(){
return size == 0;
}
增加元素
通过递归的方式寻找到正确的位置,再进行添加
/**
* 增加元素 调用的函数
* @param data 添加的数据
*/
public void add(E data) {
root = add(root, data);
}
/**
* 通过递归寻找到合适的位置
* @param root 节点
* @param data 数据
* @return 参数中的node
*/
private Node add(Node root, E data){
//根节点为空 直接在根节点进行添加
if (root == null){
size ++;
return new Node(data);
}
//与根节点进行比较 调用递归直至放到正确的位置
if (data.compareTo(root.data) < 0){
root.left = add(root.left,data);
}else {
root.right = add(root.right,data);
}
return root;
}
删除元素
根据二叉树的特点递归(也可以采用循环的方式)查找,删除.这里要注意移除节点之后,其他节点的变换
删除最大值
删除最小元素
/**
* 删除最小值
* @return 删除的最小值
*/
public E removeMin(){
E minData = getMin();
root = removeMin(root);
return minData;
}
/**
* 删除掉以node为根的二分搜索树中最小的节点
* @param node 传入节点
* @return 返回删除后新的二分搜索树的根
*/
private Node removeMin(Node node){
//递归的终止条件:找到了最小的节点
if (node.left == null){
//node.right为空也不影响
Node rightNode = node.right;
node.right = null;
size--;
//返回这一步,就将node.right的节点变成了父亲节点
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
/**
* 删除最大值
* @return 删除的最大值
*/
public E removeMax(){
E maxData = getMax();
root = removeMax(root);
return maxData;
}
/**
* 删除掉以node为根的二分搜索树中最大的节点
* @param node 传入节点
* @return 返回删除后新的二分搜索树的根
*/
private Node removeMax(Node node){
if (node.right == null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
查找元素
- 是否存在该元素
同样是通过递归的方式进行
- 获取最值
/**
* 查询二叉搜索树中是否存在该元素
* @param data 查询的数据
* @return false-不存在,true-存在
*/
public boolean contains(E data){
return contains(root,data);
}
private boolean contains(Node node,E data){
//如果根节点为空时,结束递归
if (node == null){
return false;
}
//找到相等的值
if (node.data.compareTo(data) == 0){
return true;
}
//如果寻找的节点值比当前根节点大 向右继续寻找
else if (node.data.compareTo(data) < 0){
return contains(node.right,data);
}
//如果寻找的节点值比当前根节点小 向左继续寻找
else {
return contains(node.left,data);
}
}
/**
* 获取最大值
* @return 二叉搜索树中的最大值
*/
public E getMax(){
if (isEmpty()){
throw new IllegalArgumentException("BinarySearchTree is empty");
}
return getMax(root).data;
}
/**
* 通过递归获取最右边的节点,也就是值最大的节点
* @param node 节点
* @return 最右边的节点
*/
private Node getMax(Node node){
if (node.right == null){
return node;
}
return getMax(node);
}
/**
* 获取最小值
* @return 最小值
*/
public E getMin(){
if (isEmpty()){
throw new IllegalArgumentException("BinarySearchTree is empty");
}
return getMin(root).data;
}
/**
* 通过递归获取最左边的节点,也就是值最小的节点
* @param node 节点
* @return 最左边的节点
*/
private Node getMin(Node node){
if (node.left == null){
return node;
}
return getMin(node);
}
二分搜索树的局限性
同样的数据,可以对应不同的二分搜索树,甚至可能退化成链表
退化成链表之后树的高度上升,所有的算法复杂度退化为On级别
解决方案:
平衡二叉树,其中最经典的莫过于红黑树
(2-3 树,AVL 树,伸展树(Splay tree))
网友评论