文章目录 ⭐前言⭐ 🍓一，二分搜索树的特性 1，中序遍历的序列是递增的序列 2，中序遍历的下一个节点，称后继节点，即比当前节点大的最小节点 3，中序遍历的前一个节点，称前驱节点，即比当前节点小的最大节点 🍒二，添加节点 1，思路 2，代码实现 🍌三，删除任意节点 1，思路 2，示例分析 3，代码实现 🍎四，查找节点 1，思路 2，代码实现 🍇五，总结 1，二分搜索树的优缺点 2，时间-空间复杂度 ⭐前言⭐ 二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
二叉排序树或者是一棵空树，或者是具有下列特点的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； （3）左、右子树也分别为二叉排序树； 🍓一，二分搜索树的特性 1，中序遍历的序列是递增的序列 public LinkedList inorder(TreeNode root, LinkedList arr) { if (root == null) return arr; inorder(root.left, arr); arr.add(root.val); inorder(root.right, arr); return arr; }
2，中序遍历的下一个节点，称后继节点，即比当前节点大的最小节点 public int successor(TreeNode root) { root = root.right; while (root.left != null) root = root.left; return root; } 3，中序遍历的前一个节点，称前驱节点，即比当前节点小的最大节点 public int predecessor(TreeNode root) { root = root.left; while (root.right != null) root = root.right; return root; }
🍒二，添加节点 1，思路 🌸（1）比较根节点和value的值 🌸（2）把value添加在叶子节点
2，代码实现
/**
* 添加值为value的节点
*/
public Node add(Node root, int value) {
if(root == null){
//走到叶子节点添加
root = new Node(value);
size++;
return root;
}
//比较value和根节点的大小
if(value < root.val){
root.left = add(root.left,value);
}else{
root.right = add(root.right,value);
}
return root;
}
🍌三，删除任意节点 1，思路 （1）若value < root.val，则在左子树进行删除 （2）若value >root.val，则在右子树进行删除 （3）若value == root.val，此节点就是要删除的 ① 该节点是叶子，直接删除 ②该节点只有左子树，将前驱节点代替根节点，删除前驱节点 ③该节点只有右子树，将后继节点代替根节点，删除后继节点 （4）返回根节点root
2，示例分析 （1）要删除的节点为叶子节点，可以直接删除
（2）删除的节点不是叶子节点，只有右节点，则该节点可以由该节点的后继节点替代，然后可以从后继节点的位置递归向下操作以删除后继节点。
（3）删除的节点不是叶子节点，只有左节点。
这意味着它的后继节点在它的上面，但是我们并不想返回。
我们可以使用它的前驱节点进行替代，然后再递归的向下删除前驱节点。
3，代码实现
/**
* 二叉搜索树的根节点 root,值 key，删除key 对应的节点
*/
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null) {
return null;
}
if(key < root.val){
//在左子树删除
root.left = deleteNode(root.left,key);
}else if(key > root.val){
//在右子树删除
root.right = deleteNode(root.right,key);
}else{
//node是叶子
if(root.left ==null && root.right == null){
root = null;
//只有右子树
}else if(root.right != null){
root.val = sucessor(root);
root.right = deleteNode(root.right,root.val);
}else{
//只有左子树
root.val = predecessor(root);
root.left = deleteNode(root.left,root.val);
}
}
return root;
}
//找到后继节点，返回根结点的值
public int sucessor(TreeNode root) {
root = root.right;
while(root.left != null){
root = root.left;
}
return root.val;
}
//找到前驱节点，返回根结点的值
public int predecessor(TreeNode root) {
root = root.left;
while(root.right != null){
root = root.right;
}
return root.val;
}
🍎四，查找节点 1，思路 🍎 (1)查找二分搜索树是否包含指定值-二分查找 🍎 (2)返回二分搜索树的最小值 🍎 (3)返回二分搜索树的最大值
2，代码实现
/**
* 判断以root为根节点的二分搜索树中是否包含指定元素val
*/
public boolean contains(Node root,int val){
if(root == null){
return false;
}
//根节点就是val
if(root.val == val){
return true;
}else if(val < root.val){
//在左树中寻找
contains(root.left,val);
}
return contains(root.right,val);
}
🍇五，总结 1，二分搜索树的优缺点 （1）⭐优势⭐ 查找元素、插入元素、删除元素的时间复杂度都是O(logn)。
还可以方便的回答很多数据之间关系的问题:min，max，floor，ceil，rank，select （2）⭐局限性⭐ 当将一组数据以近乎有序的顺序插入空二分搜索树中时，几乎每一个节点都是父节点的右孩子，二分搜索树近乎退化成了一个链表，相关算法时间复杂度都退化成了O(N)。
因此有了平衡二叉树，不会退化成链表，如：红黑树等。
2，时间-空间复杂度 🍓二叉排序树是平衡的，则n个节点的二叉排序树的高度为,其查找效率为，近似于折半查找。
如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。
一般的，二叉排序树的查找性能在到O(n)之间。
因此，为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。
🍓二叉树的空间复杂度：因为需要建立排序二叉树，所以空间复杂度为O（n）