BST
Binary Search Tree也被成为 ordered binary tree(有序二叉树)或 sorted binary tree(排序二叉树),
interface
package _11_Tree._01_trie;
import java.util.List;
import java.util.function.Consumer;
//二叉树
public interface IBinarySearchTree<K, V> {
/**
* 新增节点
*
* @param k 关键字
* @param v 值
* @return
*/
BSTNode<K, V> insert(K k, V v);
/**
* 中序遍历 处理中序遍历中的每个元素的函数
*
* @param con
*/
void inOrder(Consumer<K> con);
/**
* 查找元素
*
* @param key
* @return
*/
V lookupValue(K key);
/**
* 获取最小关键字
*
* @return
*/
K min();
/**
* 获取最大关键字
*
* @return
*/
K max();
/**
* 移除关键字对应的节点
*
* @param key
*/
void remove(K key);
/**
* x的后继-比x大的第一个元素
* 1、其右边子树的最小值
* 2、没有子树,则向上追溯,直到每个祖先节点是左孩子,返回这个祖先节点的父亲节点 它就是x的后继
*
* @param x
* @return
*/
K successor(K x);
/**
* 前驱 返回第一个比它小的元素
*
* @param x
* @return
*/
K predecessor(K x);
Boolean isBalance();
/**
* 返回节点数
*
* @return
*/
int getSize();
/**
* 高度
*
* @return
*/
int getHeight();
/**
* 层次遍历
* @return
*/
List<List<BSTNode<K, V>>> levelOrder();
}
BSTNode
节点
package _11_Tree._01_trie;
public class BSTNode<K, V> {
public K key;
public V value;
public BSTNode<K, V> left;
public BSTNode<K, V> right;
public BSTNode<K, V> parent;
public Boolean isLeftChild;
public int height;//以这个节点的根的高度
public int num;//编号
public BSTNode() {
}
public BSTNode(K key, V value, BSTNode<K, V> left, BSTNode<K, V> right, BSTNode<K, V> parent) {
super();
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.parent = parent;
}
public boolean isLeft() {
return isLeftChild;
}
public boolean isRight() {
return !isLeftChild;
}
}
实现
package _11_Tree._01_trie;
import java.util.*;
import java.util.function.Consumer;
public class BinarySearchTree<K, V> implements IBinarySearchTree<K, V> {
/**
* 根节点
*/
protected BSTNode root;
/**
* 元素个数
*/
protected int size;
BinarySearchTree() {
}
/**
* 更新节点高度
*
* @param curr
*/
private void updateHeight(BSTNode<K, V> curr) {
if (curr.parent == null) return;//util root
BSTNode<K, V> p = curr.parent;//update this node be father
if (p.height == curr.height) {
p.height++;
updateHeight(p);//递归
}
}
/**
* 插入节点
* 用到 Comparable 接口
*
* @param key
* @param value
* @return
*/
@Override
public BSTNode<K, V> insert(K key, V value) {
if (!(key instanceof Comparable)) {//判断是否可比较 不能比较就不能创建
throw new ClassCastException();
}
BSTNode<K, V> parent = null;
BSTNode<K, V> curr = root;//current 和parent 是父子关系
//找到要插入的位置
while (curr != null) {
parent = curr;//记录插入位置的父节点
if (compare(key, curr.key) < 0)
curr = curr.left;//小的在左边
else if (compare(key, curr.key) > 0) {
curr = curr.right;
} else { //相同 无法插入
curr.value = value;
return curr;
}
}
//Link new Node with key,value,parent.
curr = new BSTNode(key, value, null, null, parent);
if (parent == null) {//父节点没有 说明是插入第一个元素 就是根节点
root = curr;
} else if (compare(key, parent.key) < 0) {
parent.left = curr;
curr.isLeftChild = true;
} else {
parent.right = curr;
curr.isLeftChild = false;
}
size++;//节点数目
updateHeight(curr);//更新树的高度
return curr;
}
/**
* 中序遍历
* Consumer义定一个参数,对其进行(消费)处理,处理的方式可以是任意操作.
*
* @param con
*/
@Override
public void inOrder(Consumer<K> con) {
if (root != null)
inOrder(root, con);
}
private void inOrder(BSTNode<K, V> p, Consumer<K> con) {
if (p != null) {
inOrder(p.left, con);
con.accept(p.key);
inOrder(p.right, con);
}
}
/**
* 通过 key查 value
* O(n)~O([LogN+1])
*
* @param key
* @return
*/
@Override
public V lookupValue(K key) {
//查找值 创建值的节点
BSTNode<K, V> lookupNode = lookupNode(key);
return lookupNode == null ? null : lookupNode.value;
}
private BSTNode<K, V> lookupNode(K key) {
BSTNode<K, V> p = root;
//不为空和 没找到
while (p != null && compare(key, p.key) != 0) {
if (compare(key, p.key) < 0) {//小了 在左边
p = p.left;
} else {
p = p.right;
}
}
return p;
}
@Override
public K min() {
return minNode(root).key;
}
private BSTNode<K, V> minNode(BSTNode p) {
while (p.left != null) {
p = p.left;
}
return p;
}
@Override
public K max() {
return maxNode(root).key;
}
private BSTNode<K, V> maxNode(BSTNode p) {
while (p.right != null)
p = p.right;
return p;
}
/**
* 找到对应的key节点
*
* @param key 通过k删除节点
*/
@Override
public void remove(K key) {
removeNode(lookupNode(key));//查找删除的节点
size--;
}
/**
* 11.10BST中移除节点
* 有三种情况:
* 1.叶子 Leaf Node :最边界的节点 无子节点 :断相互连接就好
* 2.单支(左/右): 顶替即可
* 3.双支 :找 右子树的最小节点min ,并把数据替换进去。删除min(右侧最小min替代x 删min)
*
* @param x
*/
private void removeNode(BSTNode<K, V> x) {
if (x != null) {//节点存在
if (x.left == null && x.right == null) {//为leaf node 就是无子节点 最边界
if (x.parent == null) {//根节点
root = null;
return;
}
if (x.isLeftChild) {//父亲指向子节点 断开
x.parent.left = null;
} else {
x.parent.right = null;
}
x.parent = null;//子节点指向父亲 断开
// x = null;
} else if (x.left == null) {//x只有右节点
if (x.isLeftChild) {//x是左孩子
BSTNode<K, V> c = x.right;//x的右孩子替代他
BSTNode<K, V> parent = x.parent;
parent.left = c;
c.isLeftChild = true;
c.parent = parent;
} else {//x是右孩子
if (x.parent != null) {//x有父亲 所以不是根节点 三点一线
x.parent.right = x.right; //直接把x换成 他的右子节点 //父亲指向x的右子节点
x.right.parent = x.parent;//
} else {//x是根节点
root = x.right;
}
}
x = null;//自己位空
} else if (x.right == null) {//x只有 左节点
if (x.isLeftChild) { // x是左孩子 三点一线
x.parent.left = x.left;
x.left.parent = x.parent;
} else {//x为右边孩子 有左节点
if (x.parent != null) {//218 //存在父亲
x.parent.right = x.left;
x.left.isLeftChild = false;//替换了x 并成为了右节点
x.left.parent = x.parent;
} else {//无父亲 为根节点
root = x.left;
}
}
x = null;
} else {//双分支 都存在 不为空
BSTNode<K, V> minOfRight = minNode(x.right);//找出右边分支最大的来替换
x.key = minOfRight.key;//替换key 和value 原指向不变。
x.value = minOfRight.value;
removeNode(minOfRight);//删除该节点即可(右子树最小元素)
}
}
}
/**
* x的后继-比x大的第一个元素
* 1、其右边子树的最小值
* 2、没有子树,则向上追溯,直到每个祖先节点是左孩子,返回这个祖先节点的父亲节点 它就是x的后继
*
* @param x
* @return
*/
@Override
public K successor(K x) {
BSTNode<K, V> xNode = lookupNode(x);//找到节点
if (xNode == null) return null;
if (xNode.right != null) return minNode(xNode.right).key;
BSTNode<K, V> yNode = xNode.parent;
while (yNode != null && xNode != yNode.left) {//找到该节点是 父亲节点的 做孩子。则其父亲
xNode = yNode;//不满足就上推
yNode = yNode.parent;
}
return yNode == null ? null : yNode.key;
}
/**
* 前驱 返回第一个比它小的元素
*
* @param x
* @return
*/
@Override
public K predecessor(K x) {
BSTNode<K, V> xNode = lookupNode(x);
if (xNode == null) return null;
if (xNode.left != null) return maxNode(xNode.left).key;//有左子树 返回左子树的最小值
BSTNode<K, V> yNode = xNode.parent;
while (yNode != null && xNode.isLeftChild) {//找到是右孩子的 父亲节点 就是比它小的 第一个元素
xNode = yNode;
yNode = yNode.parent;
}
return yNode==null?null:yNode.key;
}
@Override
public Boolean isBalance() {
return null;
}
@Override
public int getSize() {
return size;
}
@Override
public int getHeight() {
return getHeight(root);
}
protected int getHeight(BSTNode node) {
if (node == null) return 0;
int l = getHeight(node.left);
int r = getHeight(node.right);
return 1 + Math.max(l, r);
// return node.height;
}
@Override
public List<List<BSTNode<K, V>>> levelOrder() {
root.num = 1;//节点按实际位置编号 有虚节点的位置
return levelOrder(root);
}
private List<List<BSTNode<K, V>>> levelOrder(BSTNode x) {
//int num=x.num;// 累进的编号
List<List<BSTNode<K, V>>> res = new ArrayList<>();
Queue<BSTNode<K, V>> q = new LinkedList<>();
q.add(x);
BSTNode<K, V> last = x;
BSTNode<K, V> nLast = null;
List<BSTNode<K, V>> l = new ArrayList<>();
res.add(l);
while (!q.isEmpty()) {
BSTNode<K, V> peek = q.peek();
//把即将弹出的节点的子节点加入队列
if (peek.left != null) {
peek.left.num = peek.num * 2;
q.add(peek.left);
nLast = peek.left;
}
if (peek.right != null) {
peek.right.num = peek.num * 2 + 1;
q.add(peek.right);
nLast = peek.right;
}
l.add(q.poll());//弹出,加入当前层列
if (peek == last && !q.isEmpty()) {///如果现在弹出的节点是之前标记的最后节点,就要换列表
l = new ArrayList<>();
res.add(l);
last = nLast;
}
}
return res;
}
//Comparator接口 独立的类中实现比较 不强制进行自然排序,可以指定排序顺序。
private Comparator comparator;
public BinarySearchTree(Comparator comparator) {
this.comparator = comparator;
}
private int compare(K key, K key1) {
if (null == comparator)
return ((Comparable) key).compareTo((Comparable) key1);
else
return comparator.compare(key, key1);
}
}
本文作者:Author: 寒光博客
文章标题:[java]BinarySearchTree(BST)接口及其实现
本文地址:https://dxoca.cn/dataStructure/375.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/dataStructure/375.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。