二叉查找树
二叉查找树的平均查找速度与树高成正比
优点: 作为一种有序符号表实现,支持高效的查找丶插入丶删除操作, 平均情况下1.39lgN
缺点: 在最坏况下(有序数据构建),二叉查找树会退化成链表,此时的变为o(n)级别,(为解决此问题出现平衡树)
/**
* 二叉查找树
* 性质:
* 1.若它的左子树不为空,则左子树上的所有节点的值均小于根节点的值
* 2.若它的右子树不为空,则右子树上的所有结点的值均大于根节点的值
* 3.二叉查找树的左右子树也都是二叉查找树
*/
public class BinarySearchTree<Key,Value> {
private Comparator comparator;
private Node root;
public BinarySearchTree(Comparator comparator) {
this.comparator = comparator;
}
private class Node{
private Key key;
private Value val;
private Node left; //左子节点
private Node right; //右子节点
private int n; //以当前节点为根节点的二叉查找树总节点数(x.n = x.left.n + x.right.n + 1)
public Node(Key key, Value val, int n) {
this.key = key;
this.val = val;
this.n = n;
}
}
//*************************************1.递归实现部分***************************************
/**
*插入: 递归方式
*概述: 1.从根节点查找是否有与待插入节点相同key的节点,如果有则更新其值val
* 如果一直到树的底部还没有找到则直接在底部正确位置插入新节点即可
* 2. 查找过程中如果待插入节点比当前节点x大,则只需要在x节点右子树中查找
* 如果比当前节点x小则只需要在x节点左子树中查找
*/
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,1); //查找树底还没找到,则插入新节点
int cmp = comparator.compare(key,x.key);
if(cmp > 0) x.right = put(x.right,key,val);
else if(cmp < 0) x.left = put(x.left,key,val);
else x.val = val;
x.n = size(x.left) + size(x.right) + 1; //更新节点数
return x;
}
/**
*获取键key对应的值(与put方式查找思路相同)
*/
public Value get(Key key){ return get(root,key); }
private Value get(Node x,Key key){
if(x == null) return null;
int cmp = comparator.compare(key,x.key);
if(cmp > 0) return get(x.right,key);
else if(cmp < 0) return get(x.left,key);
else return x.val;
}
/**
*删除节点: 递归
* 概述: 1.从根节点往下进行查找(与get方法思路相同)
* 2.找到时节点为x,此时只需要用x右子树中最小的节点把x节点替换掉即可
* (或用x左子树中最大的节点替换掉x节点)
*/
public void delete(Key key){ root = delete(root,key); }
private Node delete(Node x,Key key){
if(x == null) return null;
int cmp = comparator.compare(key,x.key);
if(cmp > 0) x.right = delete(x.right,key);
else if(cmp < 0) x.left = delete(x.left,key);
else { //找到,使用x节点右子树中最小的节点替换掉x节点
if(x.left == null) return x.right;
if(x.right == null) return x.left;
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;
}
/**
* 删除最小节点
* 概述: 找到最小节点x(与min方法思路相似),用x.right节点替换掉x节点即可
*/
public void deleteMin(){ root = deleteMin(root); }
private Node deleteMin(Node x){
if(x.left == null) return x.right; //找到最小节点x,此时返回x.right,替换掉x节点
x.left = deleteMin(x.left); //在左子树查找删除最小节点
x.n = size(x.left) + size(x.right) + 1;
return x;
}
public void deleteMax(){ root = deleteMax(root); }
private Node deleteMax(Node x){
if(x.right == null) return x.left;
x.right = deleteMax(x.right);
x.n = size(x.left) + size(x.right) + 1;
return x;
}
/**
* 查找最小节点
* 概述: 从根节点开始一直向底部查找每次都查找左节点即可
* 当当前节点x没有左节点时,即为最小值
*/
public Key min(){ return min(root).key; }
private Node min(Node x){
if(x.left == null) return x;
return min(x.left);
}
public Key max(){ return max(root).key; }
private Node max(Node x){
if(x.right == null) return x;
return max(x.right);
}
/**
* 小于等于key的最大节点
* 概述: 如果key小于当前节点,则一定在左子树
* 如果key大于当前节点,则在右子树找,如果右子树没有找到,则当前节点即为所需结果
* 如果相等,则当前节点为所需结果
*/
public Key floor(Key key){
Node x = floor(root,key);
if(x == null) return null;
return x.key;
}
private Node floor(Node x,Key key){
if(x == null) return null; //结束条件,在子树中没有找到时返回null
int cmp = comparator.compare(key,x.key);
if(cmp < 0) return floor(x.left,key);
else if(cmp >0){
Node t = floor(x.right,key);
if(t != null) return t; //右子树找到,返回找到的结果
//没有找到时返回x
}
return x; //cmp = 0; 或者 cmp >0且右子树没有找到时x为所需结果
}
//大于等于key的最小节点
public Key ceiling(Key key){
Node x = ceiling(root,key);
if(x == null) return null;
return x.key;
}
private Node ceiling(Node x,Key key){
if(x == null) return null;
int cmp = comparator.compare(key,x.key);
if(cmp > 0) return ceiling(x.right,key);
else if(cmp < 0){
Node t = ceiling(x.left,key);
if(t != null) return t;
}
return x;
}
/**
* 小于键key的数量
* 概述: 如果key小于当前节点,则在当前节点左子树查找小于key的数量即可
* 如果key大于当前节点,则在右子树中查找小于key的数量然后加上左子树节点数和一个根节点
* 如果相等,则左子树节点数即为所需结果
*/
public int rank(Key key){ return rank(root,key); }
private int rank(Node x,Key key){
if(x == null) return 0;
int cmp = comparator.compare(key,x.key);
if(cmp < 0) return rank(x.left,key);
else if(cmp > 0) return rank(x.right,key) + size(x.left) + 1;
else return size(x.left);
}
/**
* 排名为k的键(树中有k个小于它的键)
* 概述: 先统计当前节点左子树节点数t
* 如果t > k ,则在当前节点左子树中递归查找结果即可
* 如果t < k ,则在右子树查找即可,此时在右子树排名为 k-t-1
* (k-t-1值为0时,会递归到右子树最小节点,此时size(x.left)=0,
* 返回右子树最小节点)
* 如果t = k , 则返回当前节点即可
*/
public Key select(int k){
Node x = select(root,k);
if(x == null) return null;
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;
}
//二叉树中是否存在键key的节点
public boolean contains(Key key){ return get(key) != null; }
//是否为空
public boolean isEmpty(){ return size() == 0; }
//返回二叉树的节点总数
public int size(){ return size(root); }
private int size(Node x){
if(x == null) return 0;
return x.n;
}
public Iterable<Key> keys(){ return keys(min(),max()); }
public Iterable<Key> keys(Key lo,Key hi){
ArrayDeque<Key> deque = new ArrayDeque<>();
keys(deque,root,lo,hi);
return deque;
}
/**
* 范围查找:
* 中序遍历(递归): left -> root -> right
* 中序遍历节点key值在lo ~ hi之间的节点
* 概述: 将中序遍历稍作修改即可,(增加判断条件只遍历符合的子树)
* 即: 如果需要遍历当前节点x的左子树x.left, 则 lo < x
* 如果需要遍历当前节点x的右子树x.right, 则 hi > x
*/
private void keys(Deque deque, Node x, Key lo, Key hi){
if(x == null) return;
int cmplo = comparator.compare(x.key,lo);
int cmphi = comparator.compare(x.key,hi);
if(cmplo > 0) keys(deque,x.left,lo,hi);
if(cmplo >=0 && cmphi <= 0) deque.offerLast(x.key);
if(cmphi < 0) keys(deque,x.right,lo,hi);
}
public Iterable<Key> keysLoop(Key lo,Key hi){
ArrayDeque<Key> deque = new ArrayDeque<>();
keysLoop(deque,root,lo,hi);
return deque;
}
//***********************************2. 非递归实现部分*************************************
// 没有维护n的值
/**
* 范围查找: 非递归
* 概述: 在非递归中序遍历基础上增加判断条件,不遍历不符合的子树
*/
private void keysLoop(Deque deque,Node x,Key lo,Key hi){
ArrayDeque<Node> stack = new ArrayDeque<>();
while(x != null || !stack.isEmpty()) {
while (x != null) {
stack.push(x);
int cmplo = comparator.compare(x.key,lo);
if( cmplo >= 0) x = x.left;
else x = null;
}
if(stack.isEmpty()) continue;
x = stack.pop();
int cmplo = comparator.compare(x.key,lo);
int cmphi = comparator.compare(x.key,hi);
if(cmplo >=0 && cmphi <= 0) deque.offerLast(x.key);
if (x.right != null && cmphi <= 0) x = x.right;
else x = null;
}
}
/**
* 前序遍历: 非递归
* root -> left -> right
*/
public Iterable<Key> preOrder(){
ArrayDeque<Key> deque = new ArrayDeque<>();
ArrayDeque<Node> stack = new ArrayDeque<>();
Node x = root;
while(x != null || !stack.isEmpty()) {
while (x != null) {
deque.offerLast(x.key);
stack.push(x);
x = x.left;
}
if(stack.isEmpty()) continue;
x = stack.pop();
x = x.right;
}
return deque;
}
/**
* 中序遍历: 非递归
* left -> root -> right
*/
public Iterable<Key> inOrder(){
ArrayDeque<Key> deque = new ArrayDeque<>();
ArrayDeque<Node> stack = new ArrayDeque<>();
Node x = root;
while(x != null || !stack.isEmpty()) {
while (x != null) {
stack.push(x);
x = x.left;
}
if(stack.isEmpty()) continue;
x = stack.pop();
deque.offerLast(x.key);
x = x.right;
}
return deque;
}
/**
* 后序遍历: 非递归
* left -> right -> root
* 概述: 在中序遍历基础上做出修改即可
* 在中序遍历中经过root时,如何存在right没有遍历则root不出栈;
* 即如果上一个遍历节点pre不是当前root节点的right节点则需要先遍历right节点
*/
public Iterable<Key> postOrder(){
ArrayDeque<Key> deque = new ArrayDeque<>();
ArrayDeque<Node> stack = new ArrayDeque<>();
Node x = root;
Node pre = null; //保存最新出栈节点
do {
while (x != null) {
if(pre == x) break; //已经遍历根节点,无需遍历子树
stack.push(x);
x = x.left;
}
x = stack.peek();
//当存在右节点且右节点没有遍历时(前一个遍历节点不是右节点),先遍历右节点(压栈)
if (x.right != null && x.right != pre) {
x = x.right;
continue;
}
x = stack.pop();
deque.offerLast(x.key);
pre = x; //保存最新出栈节点
} while(!stack.isEmpty());
return deque;
}
/**
* 层序遍历: 非递归
* 概述: 利用队列先进先出的特点
* 先将首层节点依次入队,然后出队时,如果有子节点则将子节点再依次入队
*/
public Iterable<Key> levelOrder(){
ArrayDeque<Node> queue = new ArrayDeque<>();
ArrayDeque<Key> deque = new ArrayDeque<>();
Node x = root;
queue.offerLast(x);
while(!queue.isEmpty()){
Node t = queue.pollFirst();
if(t != null) deque.offerLast(t.key);
if(t.left != null) queue.offerLast(t.left);
if(t.right != null) queue.offerLast(t.right);
}
return deque;
}
//插入: 非递归
public void putLoop(Key key,Value val){
if(root == null) {
root = new Node(key,val,1);
return;
}
Node x = root,parent = null;
while(x != null){
parent = x;
int cmp = comparator.compare(key,x.key);
if(cmp > 0) x = x.right;
else if(cmp < 0) x = x.left;
else {
x.val = val;
return;
}
}
//如果是新元素插入则更新n(或者直接更新,非新元素再撤回)
x = root;
while(x != null){
int cmp = comparator.compare(key,x.key);
if(cmp > 0) {
x = x.right;
if(x != null) x.n ++;
}
else if(cmp < 0) {
x = x.left;
if(x != null) x.n++;
}
}
int cmp = comparator.compare(key,parent.key);
if(cmp > 0) parent.right = new Node(key,val,1);
else parent.left = new Node(key,val,1);
}
//获取: 非递归
public Value getLoop(Key key){
Node x = root;
while(x != null){
int cmp = comparator.compare(key,x.key);
if(cmp > 0) x = x.right;
else if(cmp < 0) x = x.left;
else return x.val;
}
return null;
}
//删除: 非递归
public void deleteLoop(Key key){ root = deleteLoop(root,key); }
private Node deleteLoop(Node x,Key key){
Node r = x;
Node pre = null;
while(x != null){
int cmp = comparator.compare(key,x.key);
if(cmp > 0)
{
pre = x;
x = x.right;
}
else if(cmp < 0)
{
pre = x;
x = x.left;
}
else{
Node t = x;
if(x.left == null) x = x.right;
else if(x.right == null) x = x.left;
else{
x = minLoop(t.right);
x.right = deleteMinLoop(t.right);
x.left = t.left;
}
if(pre == null) r = x;
else if(pre.left == t) pre.left = x;
else pre.right = x;
break;
}
}
return r;
}
//最小值: 非递归
private Node minLoop(Node x){
if(x == null) return null;
while(x.left != null){
x = x.left;
}
return x;
}
//删除最小: 非递归
public void deleteMinLoop(){ root = deleteMinLoop(root); }
private Node deleteMinLoop(Node x){
Node r = x;
Node pre = x;
if(x == null) return null;
while (x.left != null) {
pre = x;
x = x.left;
}
if(pre == x) return pre.right;
pre.left = x.right;
return r;
}
/**
* 树高
* 概述: 当前节点左子树和右子树中最大高度+1即为当前节点树高
*/
public int height(){ return height(root); }
private int height(Node x){
if(x == null) return 0; //假设叶子节点高度为1,若叶子节点高度为0则返回-1;
return Math.max(height(x.left),height(x.right)) + 1;
}
//是否二叉查找树(根据二叉查找树性质判断)(也可以通过中序遍历判断)
public boolean isBST(){ return isBST(root,null,null); }
public boolean isBST(Node x,Key min,Key max){
if(x == null) return true;
if(min != null && comparator.compare(x.key,min) <= 0) return false;
if(max != null && comparator.compare(x.key,max) >= 0) return false;
//左子树上的所有节点的值均小于根节点的值,右子树上的所有结点的值均大于根节点的值
return isBST(x.left,min,x.key) && isBST(x.right,x.key,max);
}
}