数据结构|【数据结构】二叉搜索树数据结构|大数据

目录

概念
二叉搜索树的查找
二叉搜索树的插入
二叉搜索树的删除
二叉搜索树的性能分析

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

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

文章图片

int a [ ] = {5,3,4,1,7,8,2,6,0,9};

二叉搜索树的查找

文章图片

二叉搜索树的插入

文章图片

二叉搜索树的删除第一大种情况、cur.left == null
我们以这一大种情况为例，画图解析，后面其它情况类推即可

文章图片

【数据结构|【数据结构】二叉搜索树】第二大种情况、cur.right == null

文章图片

第三大种情况、cur.left != null && cur.right != null （也是最难的一种情况）

文章图片

我们的思路：
要么在待删除结点的左树找最大值，要么在待删除结点的右树找最小值，然后把待删除结点的值更新成找到的左树的最大值或者是找到的右树的最小值，最后把这个替罪羊结点（找到的左树的最大值或者找到的右树的最小值原来对应的结点）给删除

我们以找右树的最小值为例，画图帮助理解

文章图片

关于二叉搜索树的插入、查找、删除有关代码

public class BinarySearchTree { static class TreeNode{ public int key; public TreeNode left; public TreeNode right; TreeNode (int key){ this.key = key; } } public TreeNode root; /** * 插入 * @param key * @return true 表示插入成功, false 表示插入失败 */ public boolean insert(int key){ if(root==null){ root = new TreeNode(key); return true; } TreeNode cur = root; TreeNode parent = null; while(cur != null){ if(cur.key < key){ parent = cur; cur = cur.right; }else if(cur.key > key){ parent = cur; cur = cur.left; }else { return false; } } TreeNode node = new TreeNode(key); //当执行到这里之后，cur==null if(parent.key < key){ parent.right = node; }else { parent.left = node; } return true; }/** * 在搜索树中查找 key，如果找到，返回 key 所在的结点，否则返回 nul * @param key * @return */ publicTreeNode search(int key){ TreeNode cur = root; while(cur != null){ if(cur.key == key){ return cur; }else if(cur.key < key){ cur = cur.right; }else { cur = cur.left; } } return null; }/** *删除成功返回 true，失败返回 false * @param key * @return */ public boolean remove(int key){ TreeNode cur = root; TreeNode parent = null; while(cur != null){ if(cur.key < key){ parent = cur; cur = cur.right; }else if(cur.key == key){ //这里开始删除 removeNode(parent,cur); return true; }else { parent = cur; cur = cur.left; } } return false; } public void removeNode(TreeNode parent,TreeNode cur){ if(cur.left == null){ if(cur == root){ root = cur.right; }else if(cur == parent.left){ parent.left = cur.right; }else { parent.right = cur.right; } }else if (cur.right == null){ if (cur == root){ root = cur.left; }else if(cur == parent.left){ parent.left = cur.left; }else { parent.right = cur.left; } }else { TreeNode targetParent = cur; TreeNode target = cur.right; //找右树的最小值 while (target.left != null){ targetParent = target; target = target.left; } cur.key = target.key; if(target == targetParent.left){ targetParent.left = target.right; }else{ targetParent.right = target.right; } } } }

二叉搜索树的性能分析