目录
一、认识二叉搜索树
🍎二叉搜索树是一种特殊的二叉树，二叉搜索树又称二叉排序树。
🍎空树也是二叉搜索树。
?二叉搜索树的特点：
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
- 二叉搜索树中的结点不可以重复
- 中序遍历二叉搜索树，得到是依次递增的序列。
二、实现二叉搜索树
💦二叉搜索树的基本结构
class Node{
public int val;
public Node left;
public Node right;
public Node(int val){
this.val = val;
}
}
//实现二叉搜索树的基本操作
public class BinarySearchTree {
public Node root = null;
}🍓查找
🍎根据二叉搜索树的定义，左子树的元素比根小，右子树的元素比根大。即只需要根据根结点的值与待查找的结点的值进行比较，就能实现查找功能。
- 根结点的值与待插入结点的值相等，表示找到了。
- 根结点的值比待插入结点的值大，去左子树找。
- 根结点的值比待插入结点的值小，去右子树找。
- 左右子树找不到，就表示没有要查找的结点。
🌊代码实现
/**
* 查找某一结点的值是否在二叉搜索树中
* @param key 待查找的值
* @return 如果在就返回该结点，不在就返回
*/
public Node sertchKey(int key){
if(root==null){
return null;
}
Node cur = root;
//遍历二叉搜索树
while (cur!=null){ //如果待查找的结点比当前结点的值大，就在该结点的右边查找
if(cur.val<key){
cur = cur.right;
}else if(cur.val>key){ //如果待查找的结点比当前结点值小，就在该结点的左边查找
cur = cur.left;
}else { //找到了就返回该结点
return cur;
}
}
return null; //找不到就返回null
}🍓插入
🍎在二叉搜索树中插入一个元素，首先要找到一个合适的插入位置。利用搜索树查找的方式，找到一待插入结点的父结点。
- 根结点的值与待插入结点的值相等，接返回false。（待插入结点的直不能与搜索树中结点的值相等）
- 根结点的值比待插入结点的值大，去左子树找。
- 根结点的值比待插入结点的值小，去右子树找。
- 找到待插入结点的父结点后，创建新的结点进行插入。
🌊代码实现
/**
* 插入结点
* @param val 待插入结点的值
* @return 插入成功返回 true，否则返回 false
*/
public boolean insert(int val){
//如果是空树，就创建一个新的结点，直接插入
if(root==null){
root = new Node(val);
return true;
}
Node cur = root;
Node parent = null; //用于指向待插入结点的父结点
//遍历二叉搜索树，找到插入结点的父结点位置
while(cur!=null){
if(cur.val<val){ //如果待插入结点的值比当前结点的值大，就在当前结点的右边查找
parent = cur; //指向当前结点
cur = cur.right; //遍历当前结点的右边
}else if(cur.val==val){ //如果待插入结点的值等于当前结点的值，就直接返回
return false; //不能有相同的数据
}else{ //待插入结点的值比当前结点的值小，就在当前结点的左边查找
parent = cur;
cur = cur.left;
}
}
//找到待插入结点的父结点后进行插入
if(val>parent.val){ //如果待插入结点的值比父结点的值大，就在父结点的右边创建一个新的结点进行插入
parent.right = new Node(val);
}else { //如果待插入结点的值比父结点的值小，就在父结点的左边创建一个新的结点进行插入
parent.left = new Node(val);
}
return true;
}🍓删除
💦二叉搜索树的删除操作需要考虑多种情况。
🍎设待删除结点为 cur, 待删除结点的双亲结点为 parent。需要删除结点，首先要找到待删除的结点，思路与查找的思路是一样的。
?情况1：cur.left == null
- cur == root，让root = cur.right;
- cur != root，parent.left == cur，让parent.left = cur.right;
- cur != root，parent.right == cur，让parent.right = cur.right。
?情况2：cur.right == null
- cur == null，让root = cur.left;
- cur != root，parent.left == cur，让parent.left = cur.left;
- cur != root，parent.right == cur，让parent.right = cur.left。
?情况3：cur.left != null && cur.right != null
- 找到 cur 右子树中结点值最小的结点，或 cur 左子树中结点值最大的结点，使用 target 指向该结点。
- 将 target 指向的结点的值与 cur 指向的结点的值进行替换。
- 删除 target 指向的结点。（使用 targetParent 指向该结点的父结点）。
- 在删除结点时要判断，target 指向的是 targetParent 的左子树还是右子树。
?🌊代码实现
/**
* 查找待删除的结点
* @param key
*/
public void remove(int key){
Node cur = root;
Node parent = null;
while (cur!=null){
if(cur.val>key){
parent = cur;
cur = cur.left;
}else if(cur.val<key){
parent = cur;
cur = cur.right;
}else {
//当cur指向的结点的值与待删除结点的值相同，就进行删除结点的操作
removeNode(cur,parent);
break;
}
}
}?找 cur 右子树中结点值最小的结点
/**
* 找到了待删除结点后，进行删除（情况三：找到右子树中最小的结点）
* @param cur
* @param parent
*/
public void removeNode(Node cur,Node parent){
if(cur.left==null){ //情况一：cur.left == null
if(cur==root){
root = cur.right;
}else if(cur==parent.left){
parent.left = cur.right;
}else { //cur==parent.right
parent.right = cur.right;
}
}else if(cur.right==null){ //情况二：cur.right == null
if(cur==root){
root = cur.left;
}else if(cur==parent.left){
parent.left = cur.left;
}else { //cur==parent.right
parent.right = cur.left;
}
}else{ //情况三：cur.left != null && cur.right != null
Node targetParent = cur;
Node target = cur.right;
while (target.left!=null){
targetParent = target;
target = target.left;
}
target.val = targetParent.val;
if(target==targetParent.left){
targetParent.left = target.right;
}else {
targetParent.right = target.right;
}
}
}?找 cur 左子树中结点值最大的结点?
/**
*找到了待删除结点后，进行删除（情况三：找到左子树中最大的结点）
* @param cur
* @param parent
*/
public void removeNode(Node cur,Node parent){
if(cur.left==null){ //情况一：cur.left == null
if(cur==root){
root = cur.right;
}else if(cur==parent.left){
parent.left = cur.right;
}else { //cur==parent.right
parent.right = cur.right;
}
}else if(cur.right==null){ //情况二：cur.right == null
if(cur==root){
root = cur.left;
}else if(cur==parent.left){
parent.left = cur.left;
}else { //cur==parent.right
parent.right = cur.left;
}
}else{ //情况三：cur.left != null && cur.right != null
Node targetParent = cur;
Node target = cur.left;
while (target.right!=null){
targetParent = target;
target = target.right;
}
target.val = targetParent.val;
if(target==targetParent.left){
targetParent.left = target.left;
}else {
targetParent.right = target.left;
}
}
}四、性能分析
- 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
- 对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
- 最优情况下，二叉搜索树为完全二叉树，其时间复杂度为二叉树的高度：O(
)。
- 最差情况下，二叉搜索树退化为单分支树，其时间复杂度为：O(n)。
