【Java---数据结构】二叉搜索树
目录
一、认识二叉搜索树
二、实现二叉搜索树
🍓查找
🍓插入
🍓删除
四、性能分析
一、认识二叉搜索树
🍎二叉搜索树是一种特殊的二叉树，二叉搜索树又称二叉排序树。
🍎空树也是二叉搜索树。
⭐二叉搜索树的特点：
二、实现二叉搜索树
💦二叉搜索树的基本结构
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.valkey){ //如果待查找的结点比当前结点值小，就在该结点的左边查找 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.valparent.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)。
