二叉搜索树
一、定义
二叉搜索树是二叉树的一种，是应用非常广泛的一种有序二叉树，英文名:Binary Search Tree,简称BST。二叉搜索树又称二叉查找树、二叉排序树。
二叉搜索树其中每个节点都包含一个键值，并且对于任意节点，其左子树中的所有键值小于该节点的键值，而右子树中的所有键值大于该节点的键值。
二、性质
二叉搜索树可以大大提高搜索树的效率，二叉搜索树所存储的元素必须具备可比较性，元素不能为null
- 左小右大性质：对于BST中的任意节点，其左子树中的所有键值小于该节点的键值，而右子树中的所有键值大于该节点的键值。
- 任意一个节点的值都大于其左子树的所有节点的值。
- 任意一个节点的值都小于其右子树的所有节点的值。
- 它的左右子树也是二叉搜索树
- 唯一性：BST中不存在两个相同键值的节点。
- 中序遍历有序性：对BST进行中序遍历得到的序列是按键值递增排列的。
- 高效的查找、插入和删除操作：由于BST的特定结构，对于有序数据的存储和检索非常高效，查找、插入和删除操作的时间复杂度为 O(log n)（平均情况下）。
三、特点
- 动态插入和删除：BST支持动态的插入和删除操作，可以根据需要动态地调整树的结构。
- 高效的查找：通过利用树的有序性质，查找操作非常高效。
- 不适合于特定数据集：虽然对于大部分数据集合BST非常高效，但是在极端情况下（比如数据完全有序的情况下），BST可能会退化为链表，导致性能下降。
- 可用于实现有序集合和映射：由于BST的有序性质，可以用于实现有序集合（例如集合、映射等）的数据结构。
四、应用场景
- 数据库索引：BST常用于数据库中的索引结构，加速数据的检索操作。
- 动态集合和映射：BST可以用于实现动态的集合和映射，提供高效的增删改查操作。
- 有序数据的存储和检索：由于BST的中序遍历结果是有序的，适合用于存储和检索有序数据。
五、实现
5.1 接口定义
/**
* @Description 二叉搜索树接口
* @Author lcy
* @Date 2020/9/22 16:18
*/
public interface BinaryTreeInfo {
/**
* 返回根节点信息，who is the root node
* @param
* @return java.lang.Object
* @author lcy
* @date 2020/9/23 9:32
**/
Object root();
/**
* 返回当前节点的左子节点
* @param node 当前节点
* @return java.lang.Object
* @author lcy
* @date 2020/9/23 9:33
**/
Object left(Object node);
/**
* 返回当前节点的右子节点
* @param node 当前节点
* @return java.lang.Object
* @author lcy
* @date 2020/9/23 9:33
**/
Object right(Object node);
/**
* 需要打印当前节点的什么值
* @param node 当前节点
* @return java.lang.Object
* @author lcy
* @date 2020/9/23 9:33
**/
Object string(Object node);
}5.2 二叉搜索树
/**
* @Description 二叉搜索树
* @Author lcy
* @Date 2020/9/22 16:18
*/
public class BinarySearchTree<E> implements BinaryTreeInfo {
/**
* 长度
*/
protected int size = 0;
/**
* 根节点
*/
protected Node<E> rootNode;
/**
* 排序接口实现
*/
protected Comparator<E> comparator;
public BinarySearchTree(Comparator<E> comparator){
this.comparator = comparator;
}
public BinarySearchTree(){
}
/**
* 提供创建节点的接口
* @param element 节点值
* @param parent 父节点
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.Node<E>
* @author lcy
* @date 2020/11/18 8:54
**/
protected Node<E> createNode(E element,Node<E> parent){
return new Node<>(element,parent);
}
/**
* 返回长度
*/
public int size(){
return size;
}
/**
* 判断是否为空
* @return boolean
* @author lcy
* @date 2020/9/3 20:58
**/
public boolean isEmpty(){
return size == 0;
}
/**
* 添加对象
* @param element 对象
* @author lcy
* @date 2020/9/3 20:55
**/
void add(E element){
checkElementNull(element);
Node<E> node;
//如果根节点为空，插入根节点
if (rootNode == null) {
node = createNode(element,null);
rootNode = node;
} else {
//获取需要插入元素的父节点
Node<E> parent = getParent(element);
node = createNode(element,parent);
int compare = compare(element,parent.element);
if (compare == 1) {
parent.right = node;
} else if (compare == -1) {
parent.left = node;
} else {
node.element = element;
}
}
size++;
//添加以后的操作
afterAdd(node);
}
/**
* 添加节点以后的操作
* @author lcy
* @date 2020/11/17 17:24
**/
protected void afterAdd(Node<E> node){}
/**
* 获取对象
* @param element 元素，根据传入元素compare属性比较，得出完整的属性
* @return E
* @author lcy
* @date 2020/9/3 20:56
**/
public E get(E element){
return node(element).element;
}
/**
* 清除数二叉树
* @author lcy
* @date 2020/9/3 20:56
**/
public void clear(){
rootNode = null;
size = 0;
}
/**
* 删除指定对象
* @param element 需要删除的对象
* @author lcy
* @date 2020/9/3 21:01
**/
boolean remove(E element){
//获取当前对象的节点
Node<E> deleteNode = node(element);
if (deleteNode == null) {
return false;
}
size--;
if (deleteNode.hasTwoChildren()) {
//获取后继节点
Node<E> successor = successor(deleteNode);
//替换节点值为后继节点值
deleteNode.element = successor.element;
//删除节点
deleteNode = successor;
}
Node<E> replaceNode = deleteNode.left != null ? deleteNode.left : deleteNode.right;
if (replaceNode != null) {
replaceNode.parent = deleteNode.parent;
if (deleteNode.parent == null) {
rootNode = replaceNode;
} else if (deleteNode.isLeftChild()) {
deleteNode.parent.left = replaceNode;
} else {
deleteNode.parent.right = replaceNode;
}
////删除节点后的操作
//afterRemove(deleteNode,replaceNode);
//删除节点后的操作
afterRemove(replaceNode);
} else if (deleteNode.parent == null) {
rootNode = null;
////删除节点后的操作
//afterRemove(deleteNode,null);
//删除节点后的操作
afterRemove(deleteNode);
} else {
if (deleteNode.isLeftChild()) {
deleteNode.parent.left = null;
} else {
deleteNode.parent.right = null;
}
////删除节点后的操作
//afterRemove(deleteNode,null);
//删除节点后的操作
afterRemove(deleteNode);
}
//if (deleteNode.hasTwoChildren()) {
// //获取前驱节点、后继节点
// Node<E> successor = successor(deleteNode);
// //替换节点值为后继节点值
// deleteNode.element = successor.element;
// //替换节点值为后继节点值
// deleteNode.element = successor.element;
// //替换值
// parent = successor.parent;
// deleteNode = successor;
//}
////删除结点
//changeNode(parent,deleteNode);
//afterRemove(deleteNode);
return true;
}
/**
* 根据删除节点的父节点（可能失衡是节点）
* @param node 删除节点
* @param replaceNode 替换的节点
* @author lcy
* @date 2020/11/20 9:03
**/
protected void afterRemove(Node<E> node,Node<E> replaceNode){
}
/**
* 根据删除节点的父节点（可能失衡是节点）
* @param node 被删除的节点或者删除以后被取代的节点（只有当被删除的节点是拥有子节点并且是度为1的时候）
* @author lcy
* @date 2020/11/20 9:03
**/
protected void afterRemove(Node<E> node){
}
/**
* 删除节点
* @param parent 父节点
* @param deleteNode 需要删除的节点
* @author lcy
* @date 2020/11/13 10:24
**/
void changeNode(Node<E> parent,Node<E> deleteNode){
if (parent == null) {
if (deleteNode.right != null) {
rootNode = deleteNode.right;
} else if (deleteNode.left != null) {
rootNode = deleteNode.left;
} else {
rootNode = null;
}
} else {
if (parent.left == deleteNode) {
parent.left = deleteNode.left;
} else if (parent.right == deleteNode) {
parent.right = deleteNode.right;
}
}
}
/**
* 根据对象获取节点值
* @param element 需要查找的对象
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.RedBlackNode<E>
* @author lcy
* @date 2020/11/12 16:18
**/
public Node<E> node(E element){
if (element == null) {
return null;
}
Node<E> node = rootNode;
while (node != null) {
//通过compare方法对比
int compare = compare(element,node.element);
if (compare == 1) {
node = node.right;
} else if (compare == -1) {
node = node.left;
} else {
return node;
}
}
return null;
}
/**
* 获取父节点的值,如果传入的元素值等于某个节点，则返回当前节点值
* @param element 元素
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.RedBlackNode<E>
* @author lcy
* @date 2020/9/22 17:20
**/
private Node<E> getParent(E element){
Node<E> node = rootNode;
Node<E> parent = null;
while (node != null) {
int compare = compare(element,node.element);
parent = node;
if (compare == 1) {
node = node.right;
} else if (compare == -1) {
node = node.left;
} else {
return node;
}
}
return parent;
}
/**
* 比较值 返回值为0，代表e1 == e2，返回值大于0，代表e1大于e2，返回值小于0，代表e1小于e2
* @param e1 原对象
* @param e2 需要对比的对象
* @return int
* @author lcy
* @date 2020/9/22 17:45
**/
private int compare(E e1,E e2){
//E泛型对象一定是实现了官方的comparable接口
if (comparator == null) {
return ((Comparable<E>)e1).compareTo(e2);
}
return comparator.compare(e1,e2);
}
/**
* 判断元素是否为空，如果为空抛出异常
* @param element 泛型元素
* @author lcy
* @date 2020/9/22 17:52
**/
private void checkElementNull(E element){
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
/**
* 前序遍历--递归
*/
public void preorderTraverse(Node<E> rootNode){
if (rootNode == null) {
return;
}
System.out.println(rootNode.element);
preorderTraverse(rootNode.left);
preorderTraverse(rootNode.right);
}
/**
* 中序遍历--递归
*/
public void inorderTraverse(Node<E> rootNode){
if (rootNode == null) {
return;
}
inorderTraverse(rootNode.left);
System.out.println(rootNode.element);
inorderTraverse(rootNode.right);
}
/**
* 后序遍历--递归
*/
public void postorderTraverse(Node<E> rootNode){
if (rootNode == null) {
return;
}
postorderTraverse(rootNode.left);
postorderTraverse(rootNode.right);
System.out.println(rootNode.element);
}
/**
* 前序遍历
*/
public void preorderTraverse(ViewTree<E> viewTree){
if (rootNode == null || viewTree == null) {
return;
}
Node<E> node = rootNode;
Stack<Node<E>> stack = new Stack<>();
while (node != null) {
//遍历根节点
viewTree.view(node.element);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
node = node.left;
} else {
if (stack.isEmpty()) {
break;
} else {
node = stack.pop();
}
}
}
}
/**
* 中序遍历
*/
public void inorderTraverse(ViewTree<E> viewTree,OperateTree<E> operateTree){
if (rootNode == null || viewTree == null) {
return;
}
//当前节点
Node<E> node = rootNode;
Stack<Node<E>> stack = new Stack<>();
//当节点不为空时
while (node != null || !stack.isEmpty()) {
//左子树入栈
while (node != null) {
stack.push(node);
node = node.left;
}
//出栈
node = stack.pop();
//操作节点
viewTree.view(node.element);
//尾部操作
if (operateTree != null) {
operateTree.operate(stack,node.element);
}
if (node.right != null) {
node = node.right;
} else {
node = null;
}
}
}
/**
* 后序遍历
*/
public void postorderTraverse(ViewTree<E> viewTree,OperateTree<E> operateTree){
if (rootNode == null || viewTree == null) {
return;
}
//当前节点
Node<E> node = rootNode;
//上一节点
Node<E> prev = null;
Stack<Node<E>> stack = new Stack<>();
//当节点不为空时
while (node != null || !stack.isEmpty()) {
//把根节点和左节点全部放到栈中
while (node != null) {
stack.push(node);
node = node.left;
}
//出栈
node = stack.pop();
if (node.right == null || node.right == prev) {
//操作节点
viewTree.view(node.element);
//尾部操作
if (operateTree != null) {
operateTree.operate(stack,node.element);
}
//上个节点为当前节点，往下遍历
prev = node;
//当前节点设为null，循环时赋予队列值
node = null;
} else {
//入栈
stack.push(node);
//当前节点等于右节点
node = node.right;
}
}
//后序遍历用两个栈实现
/* Stack<RedBlackNode<E>> stack = new Stack<>();
stack.push(rootNode);
Stack<E> elementStack = new Stack<>();
//后序遍历节点到elementStack栈里
while (!stack.isEmpty()) {
node = stack.pop();
elementStack.push(node.element);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
while (!elementStack.isEmpty()) {
E pop = elementStack.pop();
System.out.println(pop);
}*/
}
/**
* 层序遍历
* @param viewTree 遍历的对象的操作接口实现
* @author lcy
* @date 2020/10/12 14:33
**/
public void levelOrderTraverse(ViewTree<E> viewTree){
levelOrderTraverse(viewTree,null);
}
/**
* 层序遍历
* @param viewTree 遍历的对象的操作接口实现
* @param operateTree 在入栈或者入队以后的尾部操作
* @author lcy
* @date 2020/10/12 14:33
**/
public void levelOrderTraverse(ViewTree<E> viewTree,OperateTree<E> operateTree){
if (rootNode == null || viewTree == null) {
return;
}
Queue<Node<E>> queue = new LinkedBlockingQueue<>();
queue.offer(rootNode);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
//操作树
viewTree.view(node.element);
//左节点入队
if (node.left != null) {
queue.offer(node.left);
}
//右节点入队
if (node.right != null) {
queue.offer(node.right);
}
//尾部操作
if (operateTree != null) {
operateTree.operate(queue,node.element);
}
}
}
/**
* 获取当前树的高度
* @return int
* @author lcy
* @date 2020/10/12 15:02
**/
public int height(){
return height(rootNode);
}
/**
* 获取当前节点高度
* @param node 节点对象
* @return int
* @author lcy
* @date 2020/10/12 15:01
**/
public int height(Node<E> node){
if (node == null) {
return 0;
}
//当前节点的高度，默认根节点，所以是1
AtomicInteger height = new AtomicInteger(1);
//当前节点在栈或队列的子节点数，默认根节点，所以是1
AtomicInteger levelSize = new AtomicInteger(1);
//层序遍历
levelOrderTraverse(
//操作遍历值，入队之前
element -> levelSize.addAndGet(-1)
//入队以后的操作
,(collection,element) -> {
//如果子节点数为0，说明已经到下一个节点
if (levelSize.get() == 0 && collection.size() > 0) {
height.addAndGet(1);
levelSize.set(collection.size());
}
}
);
return height.get();
}
/**
* 判断是否为完全二叉树
* @return boolean
* @author lcy
* @date 2020/10/12 16:23
**/
public boolean isCompleteTree(){
return isCompleteTree(rootNode);
}
/**
* 判断节点的子树是否为完全二叉树
* @param node 节点值
* @return boolean
* @author lcy
* @date 2020/10/12 16:23
**/
private boolean isCompleteTree(Node<E> node){
if (node == null) {
return false;
}
Queue<Node<E>> queue = new LinkedBlockingQueue<>();
queue.offer(node);
//判断是否已经到叶子节点
boolean isLeaf = false;
while (!queue.isEmpty()) {
Node<E> tmpNode = queue.poll();
//如果叶子节点标记为true，但是实际不是叶子节点，返回false
if (isLeaf && !tmpNode.isLeaf()) {
return false;
}
//左节点入队
if (tmpNode.left != null) {
queue.offer(tmpNode.left);
//如果左节点为空，右节点不为空直接返回
} else if (tmpNode.right != null) {
return false;
}
//右节点入队
if (tmpNode.right != null) {
queue.offer(tmpNode.right);
//如果右节点为空。不管左边为不为空，后面的遍历的都要是叶子节点。标记修改
} else {
isLeaf = true;
}
}
return true;
}
/**
* 查找当前节点的前驱节点（中序遍历的前一个节点）
* @param node 传入节点值
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.RedBlackNode<E>
* @author lcy
* @date 2020/10/19 17:43
**/
public Node<E> predecessor(Node<E> node){
return getInorderNode(node).get("predecessor");
}
/**
* 查找当前节点的后继节点（中序遍历的后一个节点）
* @param node 传入节点值
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.RedBlackNode<E>
* @author lcy
* @date 2020/10/19 17:43
**/
public Node<E> successor(Node<E> node){
return getInorderNode(node).get("successor");
}
/**
* 根据flag标志判断获取传入节点的前驱节点还是后继节点
* @param node 节点
* @return BaseMap<String,RedBlackNode < E>> 值：predecessor为前驱节点，successor为后继节点
* @author lcy
* @date 2020/11/13 10:54
**/
public Map<String,Node<E>> getInorderNode(Node<E> node){
Map<String,Node<E>> map = new HashMap<>(3);
if (rootNode == null) {
return null;
}
//当前节点
Node<E> tmpNode = rootNode;
Node<E> prev = null;
Stack<Node<E>> stack = new Stack<>();
//当节点不为空时
while (tmpNode != null || !stack.isEmpty()) {
//左子树入栈
while (tmpNode != null) {
stack.push(tmpNode);
tmpNode = tmpNode.left;
}
//出栈
tmpNode = stack.pop();
map.put("predecessor",prev);
if (prev == node) {
map.put("successor",tmpNode);
return map;
}
prev = tmpNode;
if (tmpNode.right != null) {
tmpNode = tmpNode.right;
} else {
tmpNode = null;
}
}
return null;
}
@Override public Object root(){
return rootNode;
}
@Override public Object left(Object node){
return ((Node)node).left;
}
@Override public Object right(Object node){
return ((Node)node).right;
}
@Override public Object string(Object node){
return node;
}
/**
* 遍历二叉树做的操作
* @author lcy
* @date 2020/9/28 9:17
**/
public static interface ViewTree<E> {
/**
* 二叉树遍历操作
* @param element element
* @author lcy
* @date 2020/10/12 14:30
**/
void view(E element);
}
/**
* 遍历二叉树,在尾部做操作
* @author lcy
* @date 2020/9/28 9:17
**/
public static interface OperateTree<E> {
/**
* 操作方法
* @param collection 栈或者队列对象
* @param element element
* @author lcy
* @date 2020/10/12 14:49
**/
void operate(Collection<Node<E>> collection,E element);
}
/**
* 树节点内部类
* @author lcy
* @date 2020/9/7 10:22
**/
protected static class Node<E> {
/**
* 当前节点值
*/
E element;
/**
* 左节点值
*/
Node<E> left;
/**
* 右节点值
*/
Node<E> right;
/**
* 父节点值
*/
Node<E> parent;
public Node(E element,Node<E> parent){
this.element = element;
this.parent = parent;
}
/**
* 判断是否叶子节点
* @return boolean
* @author lcy
* @date 2020/10/16 15:46
**/
public boolean isLeaf(){
return left == null && right == null;
}
/**
* 判断是否有左右子树
* @return boolean
* @author lcy
* @date 2020/10/16 15:46
**/
public boolean hasTwoChildren(){
return left != null && right != null;
}
/**
* 判断是否有子节点
* @return boolean
* @author lcy
* @date 2020/10/16 15:46
**/
public boolean hasChild(){
return left != null || right != null;
}
/**
* 判断是否左子树
* @return boolean
* @author lcy
* @date 2020/11/18 15:23
**/
public boolean isLeftChild(){
return parent != null && parent.left == this;
}
/**
* 判断是否右子树
* @return boolean
* @author lcy
* @date 2020/11/18 15:23
**/
public boolean isRightChild(){
return parent != null && parent.right == this;
}
/**
* 返回兄弟节点
* @return Node<E>
* @author lcy
* @date 2020/11/18 15:23
**/
public Node<E> sibling(){
//如果是左子节点，返回父节点的右子节点
if (isLeftChild()) {
return parent.right;
}
//如果是右子节点，返回父节点的左子节点
if (isRightChild()) {
return parent.left;
}
//如果是根节点，返回null
return null;
}
@Override public String toString(){
return element.toString();
}
}
public static void main(String[] args){
int[] ageArray = {44,31,3,2,6,88,34,13,32,77,74,35,89,1,-1,-3,-5};
int[] weightArray = {144,131,103,102,106,188,134,113,132,177,174,135,189,1,-1,-3,-5};
BinarySearchTree<Person> binarySearchTree = new BinarySearchTree<>(Comparator.comparingInt(Person :: getAge));
for (int i = 0; i < ageArray.length; i++) {
binarySearchTree.add(new Person(ageArray[i],weightArray[i],String.valueOf(i)));
}
System.out.println("-------------print-------------");
BinaryTrees.print(binarySearchTree);
System.out.println();
System.out.println("---------------------------------");
binarySearchTree.remove(new Person(6,113,"7"));
BinaryTrees.print(binarySearchTree);
System.out.println();
binarySearchTree.remove(new Person(2,132,"7"));
BinaryTrees.print(binarySearchTree);
System.out.println();
binarySearchTree.remove(new Person(32,132,"7"));
BinaryTrees.print(binarySearchTree);
System.out.println();
binarySearchTree.add(new Person(33,133,"0"));
BinaryTrees.print(binarySearchTree);
System.out.println();
binarySearchTree.remove(new Person(31,133,"0"));
BinaryTrees.print(binarySearchTree);
System.out.println();
System.out.println("-------------print-------------");
List<Person> elementList = new ArrayList<>();
System.out.println("-------------前序遍历-------------");
binarySearchTree.preorderTraverse(binarySearchTree.rootNode);
System.out.println("---------------------------------");
binarySearchTree.preorderTraverse(System.out :: println);
System.out.println("-------------前序遍历-------------");
System.out.println("-------------中序遍历-------------");
binarySearchTree.inorderTraverse(binarySearchTree.rootNode);
System.out.println("---------------------------------");
binarySearchTree.inorderTraverse(System.out :: println,null);
System.out.println("-------------中序遍历-------------");
System.out.println("-------------后序遍历-------------");
binarySearchTree.postorderTraverse(binarySearchTree.rootNode);
System.out.println("---------------------------------");
binarySearchTree.postorderTraverse(System.out :: println,null);
System.out.println("-------------后序遍历-------------");
System.out.println("-------------层序遍历-------------");
binarySearchTree.levelOrderTraverse(elementList :: add);
binarySearchTree.levelOrderTraverse(System.out :: println);
System.out.println("-------------层序遍历-------------");
System.out.println(Arrays.toString(elementList.toArray()));
System.out.println(binarySearchTree.height());
System.out.println(binarySearchTree.isCompleteTree());
}
}