二叉搜索树
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
其中序遍历是一颗有序的树
查找
二叉搜索树的查找效率非常高
- 因为二叉搜索树的左边都比我小，右边都比我大
- 要找比我小的树，就只需要在左树中找，直接最多可以去掉一半的数据
- 每次到达一个根节点都可以一次性排除掉最多一半的数据
时间复杂度：
- 最好情况下： O ( l o g N )
- 最坏情况下： 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 的大小关系
- 如果
cur.val < key，那么就往右边走 - 如果
cur.val > key，那么就往左边走 - 如果
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; }
插入
所有的插入都是插入到了叶子节点
- 原来的树为空，则直接插入
- 当树不为空时
若要找到需要插入到的叶子结点的位置，就需要定位到最后父亲节点的叶子结点为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进行比较，选择插入哪一边
删除
删除包含很多种情况
- 需要删除的节点的左孩子为空
- 需要删除的节点的右孩子为空
- 需要删除的节点的左右孩子都不为空
找到要删除的节点
首先需要找到需要删除的节点
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. 要删除节点的左孩子为空
cur是root，则root = cur.right
cur不是root，cur是parent.left，则parent.left = cur.right
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. 要删除节点的右孩子为空
cur是root，则root = cur.left
cur不是root，cur是parent.left，则parent.left = cur.left
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. 要删除的节点的左右孩子都不为空
需要使用 替换法 进行删除
- 在它的右子树中寻找一个最小的节点，用它的值填补到被删除节点中，再来处理该结点的删除问题
- 因为要删除的节点
cur左边都比它小，右边都比它大，所以就在cur的右边找到一个最小的节点，然后让目标节点覆盖掉 cur - 目标节点不会出现左右孩子都存在的情况。要么两边都为空，要么还存在一个右节点。（既然此节点是最小的，就不可能还有左子树，因为左子树肯定比此节点小）
- 在它的左子树中寻找一个最大的节点，用它的值填补到被删除节点中，再来处理该结点的删除问题
- 此时这个最大值一定是在左树的最右边，意味着它肯定没有右子树
所以找到最小值的特征是：
- 此节点左子树为空，且一定在
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一起进行移动
- 最开始
tp在要删除的节点cur的位置，t在cur的右节点（起始步） tp走到t的位置t再走向tp的左节点（一轮移动结束）t.left != null，tp走到t的位置t再走向tp的左节点（一轮移动结束）- …
- 如果在起始步就满足
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; } } }
