【数据结构】二叉搜索树的功能实现详解

二叉搜索树

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

其中序遍历是一颗有序的树

查找

二叉搜索树的查找效率非常高

• 因为二叉搜索树的左边都比我小，右边都比我大
• 要找比我小的树，就只需要在左树中找，直接最多可以去掉一半的数据
• 每次到达一个根节点都可以一次性排除掉最多一半的数据

时间复杂度：

• 最好情况下：$O(logN)$
• 最坏情况下：$O(N)$，单分支，将整棵树遍历完

因为这颗二叉搜索树是由一个一个节点构成的，所以先定义出节点

• 左孩子
• 右孩子
• 节点的值
  并定义出头结点

public class BinarySearchTree {  static class TreeNode {  public int val;  public TreeNode left;  public TreeNode right;  public TreeNode(int val) {  this.val = val;  }   }  public TreeNode root = null;  
}

每次去看一下 cur 的 val 和我们要找的 key 的大小关系

1. 如果 cur.val < key，那么就往右边走
2. 如果 cur.val > key，那么就往左边走
3. 如果 cur.val = key，那么就找到了

public TreeNode search(int key) {  TreeNode 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;  
}

插入

所有的插入都是插入到了叶子节点

1. 原来的树为空，则直接插入

2. 当树不为空时
   若要找到需要插入到的叶子结点的位置，就需要定位到最后父亲节点的叶子结点为 null 的时候。但当 cur 走到叶子结点的时候，就找不到此叶子结点的父亲节点了，所以需要多一个 parent 节点，用来记录当前的父亲节点，好方便随时可以定位到目标叶子结点的父亲节点，后续通过父亲节点进行赋值操作

public void insert(int key) {  TreeNode node = new TreeNode(key);  TreeNode cur = root;  TreeNode parent = null;  while (cur != null) {  if (cur.val < key) {  parent = cur;  cur = cur.right;  } else if (cur.val > key) {  parent = cur;  cur = cur.left;  } else {  return;  }    }    //此循环走完，parent 指向的节点就是需要插入的节点位置的父亲节点  if (parent.val > key) {  parent.left = node;  } else (parent.val < key) {  parent.right = node;  }
}

• 值相同的时候，不能进行重复插入
• while 循环结束，cur 指向要插入的叶子结点，parent 指向需要插入的节点的父亲节点
• 之后对父亲节点和 key 进行比较，选择插入哪一边

删除

删除包含很多种情况

1. 需要删除的节点的左孩子为空
2. 需要删除的节点的右孩子为空
3. 需要删除的节点的左右孩子都不为空

找到要删除的节点

首先需要找到需要删除的节点

public void remove(int key) {  TreeNode cur = root;  TreeNode parent = null;  while (cur != null) {  if(cur.val < key) {  parent = cur;  cur = cur.right;  } else if (cur.val > key) {  parent = cur;  cur = cur.left;  }else {  //此时就是找到了要删除的节点  removeNode(parent,cur);  return;  }    }
}

• 当执行到 else 的时候，就是找到要删除的节点了
• 随后完善删除操作==> removeNode

---

删除节点

1. 要删除节点的左孩子为空

1. cur 是 root，则 root = cur.right

---

2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.right

---

3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.right

// 1.当要删除的节点 cur 的左孩子为空  
if (cur.left == null) {  if (cur == root) {  // 1.1 要删除的 cur 为根节点  root = cur.right;  } else if (cur == parent.left) {  // 1.2 要删除的 cur 是 parent 的左节点  parent.left = cur.right;  } else {  // 1.3 要删除的 cur 是 parent 的右节点  parent.right = cur.right;  }  
}

2. 要删除节点的右孩子为空

1. cur 是 root，则 root = cur.left

---

2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.left

---

3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.left

// 2. 要删除的节点 cur 的右孩子为空  
else if (cur.right == null) {  if (cur == root) {  // 2.1 要删除的 cur 是根节点  root = cur.left;  } else if (cur == parent.left) {  // 2.2 要删除的 cur 是 parent 的左节点  parent.left = cur.left;  } else {  // 2.3 要删除的 cur 是 parent 的右节点  parent.right = cur.left;  }  
}

3. 要删除的节点的左右孩子都不为空

需要使用 替换法 进行删除

1. 在它的右子树中寻找一个最小的节点，用它的值填补到被删除节点中，再来处理该结点的删除问题

   • 因为要删除的节点 cur 左边都比它小，右边都比它大，所以就在 cur 的右边找到一个最小的节点，然后让目标节点覆盖掉 cur
   • 目标节点不会出现左右孩子都存在的情况。要么两边都为空，要么还存在一个右节点。（既然此节点是最小的，就不可能还有左子树，因为左子树肯定比此节点小）

2. 在它的左子树中寻找一个最大的节点，用它的值填补到被删除节点中，再来处理该结点的删除问题

   • 此时这个最大值一定是在左树的最右边，意味着它肯定没有右子树

---

所以找到最小值的特征是：

• 此节点左子树为空，且一定在 cur 右树的最左边
• 此节点右子树为空，且一定在 cur 左树的最右边

---

寻找右子树的最小值

// 3.1 右数的最小值  
TreeNode t = cur.right;  
TreeNode tp = cur;  
while (t.left != null) {  tp = t;  t = tp.left;  
}  
cur.val = t.val;  
if(t == tp.right) {  
//t 和 tp 在起始步就找到了最小值tp.right = t.right;  
}else{  
//t 和 tp 在继续移动的过程中找到最小值tp.left = t.right;  
}

• t 是用来定位最小值的，当 t.left == null 的时候，t 就是最小值
• tp 是用来定位 t 的父节点的，方便后续对节点进行删除（因为节点的删除都要依靠删除节点的父节点进行“改变连接对象”）
• 在没找到最小节点之前，tp 和 t 一起进行移动
  1. 最开始 tp 在要删除的节点 cur 的位置，t 在 cur 的右节点（起始步）
  2. tp 走到 t 的位置
  3. t 再走向 tp 的左节点（一轮移动结束）
  4. t.left != null，tp 走到 t 的位置
  5. t 再走向 tp 的左节点（一轮移动结束）
  6. …
• 如果在起始步就满足 t.left == null 了，则直接进行

---

完整代码

public void remove(int key) {  TreeNode cur = root;  TreeNode parent = null;  while (cur != null) {  if (cur.val < key) {  parent = cur;  cur = cur.right;  } else if (cur.val > key) {  parent = cur;  cur = cur.left;  } else {  //此时就是找到了要删除的节点  removeNode(parent, cur);  return;  }  }  
}  private void removeNode(TreeNode parent, TreeNode cur) {  // 1.当要删除的节点 cur 的左孩子为空  if (cur.left == null) {  if (cur == root) {  // 1.1 要删除的 cur 为根节点  root = cur.right;  } else if (cur == parent.left) {  // 1.2 要删除的 cur 是 parent 的左节点  parent.left = cur.right;  } else {  // 1.3 要删除的 cur 是 parent 的右节点  parent.right = cur.right;  }  // 2. 要删除的节点 cur 的右孩子为空  } else if (cur.right == null) {  if (cur == root) {  // 2.1 要删除的 cur 是根节点  root = cur.left;  } else if (cur == parent.left) {  // 2.2 要删除的 cur 是 parent 的左节点  parent.left = cur.left;  } else {  // 2.3 要删除的 cur 是 parent 的右节点  parent.right = cur.left;  }  // 3. 要删除的节点的左右孩子都不为空  } else {  // 3.1 右数的最小值  TreeNode t = cur.right;  TreeNode tp = cur;  while (t.left != null) {  tp = t;  t = tp.left;  }  cur.val = t.val;  if(t == tp.right) {  //t 和 tp 在起始步就找到了最小值  tp.right = t.right;  }else{  //t 和 tp 在继续移动的过程中找到最小值  tp.left = t.right;  }  }  
}