二叉搜索树的基本操作 || TreeMap和TreeSet介绍
目录
前言：
二叉搜索树的插入
代码实现
二叉搜索树的查找
代码实现
二叉搜索树的删除
代码实现
TreeMap介绍
源码展现
TreeSet介绍
源码展现
小结：
前言：
😄现在很多地方都需要去查找某个数据，那么查找的效率就显得尤为重要了。二叉搜索树是一颗左孩子比父亲小，右孩子比父亲大的一棵树。那么在这个基础上查找某个数据，一次比较就可以排除一半数据，效率是相当高的。
二叉搜索树的插入
😯拿到一个数据，首先判断根节点是否为空，如果为空就往根节点处插入。否则依次向下比较，比它大就往右走，比它小都往左走。直到走到叶子节点，就可以插入了。这个时候需记录这个叶子节点，然后去判断往右边还是左边插入数据。
代码实现
public boolean insert(int val) {
if(root == null) {
TreeNode newNode = new TreeNode(val);
root = newNode;
return true;
}
TreeNode cur = root;
TreeNode prev = null;
while(cur != null) {
if(val > cur.val) {
prev = cur;
cur = cur.right;
}else if(val < cur.val) {
prev = cur;
cur = cur.left;
}else {
return false;
}
}
//最终可能在左面和右面插入
TreeNode newNode = new TreeNode(val);
if(val < prev.val) {
prev.left = newNode;
}else {
prev.right = newNode;
}
return true;
}二叉搜索树的查找
😃定义cur去遍历二叉树。首先判断cur处位置的val值是否和需查找值一致，如果一致则直接返回这个节点，否则就去判断cur该往左还是右走。如果cur为空，则说明二叉树遍历完成，也没有找到目标值，返回null。
代码实现
public TreeNode Search(int val) {
TreeNode cur = root;
while(cur != null) {
if(val > cur.val) {
cur = cur.right;
}else if(val < cur.val) {
cur = cur.left;
}else {
return cur;
}
}
return null;
}
二叉搜索树的删除
🎈我们可以想到要删除树中的某一个节点，需连将这个节点的上一个节点和下一个节点连接起来。所以定义前后指针prev，cur去遍历树。当cur找到后去删除这个节点。
🎈删除树中的某一个节点，如果这个节点的左右都不为空，或者这个节点的左树为空，又或者这个节点的右树为空。它们的删除方法都不相同。因此我们将这些可能都枚举出来，逐个去判断。
🎈左树为空的情况，如果要删除的节点为根节点，直接调整根节点为它的右子树。如果要删除的节点在上一个节点的右边，直接连接上一个节点的right到这个节点的right。如果要删除的节点在上一个节点的左边，连接上一个节点left到这个节点的right。
🎈右树为空的情况，如果要删除的节点为根节点，直接调整根节点为它的左子树。如果要删除的节点在上一个节点的右边，直接连接上一个节点的right到这个节点的left。如果要删除的节点在上一个节点的左边，连接上一个节点left到这个节点的left。
🎈如果要删除节点的左右都不为空，不论怎样去连接都会打破树的结构，因此提出替罪羊式删除法。在这个节点左树中找到最大值，或者右树中找到最小值，就可以替换这个节点的值，保证这颗树依然维持二叉搜索树的结构特点。那么就只需要删除左树中的最大值或者右树中的最小值（替罪羊）。当在右树中找到最小的值，替换完成后。删除这个节点时，这个节点可能在上一个节点的左边，也可能在右边（右树只有一个节点）。在左边就直接连接上一个节点的left到这个节点right。在右边就直接连接上一个节点right到这个节点的right。
代码实现
public boolean remove(int val) {
TreeNode cur = root;
TreeNode prev = null;
while(cur != null) {
if(val > cur.val) {
prev = cur;
cur = cur.right;
}else if(val < cur.val) {
prev = cur;
cur = cur.left;
}else {
removeNode(prev, cur);
return true;
}
}
return false;
}
private void removeNode(TreeNode prev, TreeNode cur) {
//删除分为三种情况
//左树为空 右树为空 左右树都不为空
if(cur.left == null) {
//可能删除根节点 可能删除prev的右节点 可能删除prev的左节点
if(cur == root) {
root = root.right;
}else if(cur == prev.right) {
prev.right = cur.right;
}else {
prev.left = cur.right;
}
}else if(cur.right == null) {
if(cur == root) {
root = root.left;
}else if(cur == prev.right) {
prev.right = cur.left;
}else {
prev.left = cur.left;
}
}else {
//替罪羊式删除法
//左树中找最大的/右树中找最小的
//就可以替换要被删除的元素，接下来只需删除左面最大或者右面最小的节点
TreeNode target = cur.right;
TreeNode targetParent = cur;
while(target.left != null) {
targetParent = target;
target = target.left;
}
cur.val = target.val;
//最终要删除的节点可能在targetParent左和右
if(target == targetParent.left) {
targetParent.left = target.right;
}else {
targetParent.right = target.right;
}
}
}TreeMap介绍
🪖TreeMap的底层是一颗红黑树，红黑树是建立在二叉搜索树结构上的。由于搜索树在极端情况下它的单分支会很长，这样就会增加查找的效率。在这个基础上提出的AVL树，将它的单分支进行旋转。由于可能旋转的次数会很多，又在这个基础上提出了红黑树。
🪖TreeMap中数据存储，是按照键值对的方式去存储（key - val）。由于搜索树中不会存在相同的数据，即TreeMap中的key是唯一的。如果插入相同的key会更新其原来key的val值，那么相应的key是不可以修改的，但是val值可以修改。
🪖TreeMap是实现map接口的，相对于Iterable接口这个接口是独立的。可以调用entrySet方法将TreeMap中的（key - val）取出来为Entry类型，存储到set集合当中去组织。也可以调用keySet或者values方法可以单独将key或者val取出来，分别存储到set集合或者collection集合当中去组织。
🪖由于TreeMap底层是红黑树，那么它的key是必须具有比较性。如果提供比较器优先调用比较器，否则实现Comparable接口重写compareTo方法。key不能为null，因为null无法比较，否则会抛NullPointerException异常。
源码展现
TreeSet介绍
🤞TreeSet只存储key。它底层是用TreeMap实现的，只是所有的val值都是Object对象。TreeSet是实现set接口的，它是在Iterable接口下。
🤞那么相应的TreeSet底层也是红黑树，key值也就是唯一的，不可以添加相同的key。它的key也需具有可比较性。TreeSet具有天然去重的功能。
源码展现
小结：
🐵在学习一些集合时，我们在理解的基础上可以去看一些源码，这样也会加深对其的理解性。