文章目录
- 一、基本概念
- 二、二叉树查询性能分析
- 三、插入
- 四、删除
- 五、代码实现
提示：以下是本篇文章正文内容，Java系列学习将会持续更新 一、基本概念
二叉查找树 (Binary Search Tree)
①它属于二叉树的一种。
②左子树的所有节点值 < 根节点的值 < 右子树的所有节点值
③它的左右子树也是二分搜索树。
④一般不考虑值相等的情况，元素不重复。
特点：
对二分搜索树进行中序遍历，得到的集合就是一个升序的集合。
二叉搜索树查找长度与结点在二叉搜索树的深度有关，即结点越深，则比较次数越多。
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N
回到目录…
三、插入①BST树不能插入重复的元素。
②往BST树中插入元素，一定是插入到叶子节点的位置，不会影响原本树的结构。
每次都是和父节点作比较，小于的话往左子树中插，大于的话往右子树中插，再和子树的父节点比较，以此往下。。。
public void add(int val) {
root = add(root, val);
}
//向以root为根节点的树添加元素
private TreeNode add(TreeNode root, int val){
//边界条件
if(root == null){
size ++;
return new TreeNode(val);
}
if(val < root.val){
//在左树中插入val
root.left = add(root.left, val);
}else if(val > root.val){
//在右树中插入val
root.right = add(root.right, val);
}
return root;
}
回到目录…
四、删除-
当待删节点没有左子树时，就类似于删除最小值，直接将右子树拼接到原本的位置。
-
当待删节点没有右子树时，就类似于删除最大值，直接将左子树拼接到原本的位置。
-
当待删节点左右子树都存在时，找到当前节点的前驱或后继节点来代替它。所谓前驱 / 后继，并不是它的左孩子 / 右孩子，而是大小关系上最接近它且比它小 / 大的节点。
-
那具体如何找前驱 / 后继呢？ 前驱 = 左子树中的最大值； 后继 = 右子树中的最小值。
public void remove(int val) {
root = remove(root, val);
}
private TreeNode remove(TreeNode root, int val) {
if(root == null){
throw new NoSuchElementException("BST中没有值为" + val + "的节点");
}else if(root.val < val){
root.right = remove(root.right, val);
return root;
}else if(root.val > val){
root.left = remove(root.left, val);
return root;
}else { //此时root就是待删节点
if(root.left == null){
// 先存右子树
TreeNode right = root.right;
// 将待删节点的指向剪断至空
root.right = root = null;
// 右子树就是结果树，直接返回
return right;
}
if(root.right == null){
TreeNode left = root.left;
root.left = root = null;
return left;
}
//此时，左右子树都不为空
//先找到右子树中的最小值节点
TreeNode rightMin = minNode(root.right);
// 结果树的右子树就是原节点删除最小值后的右子树
rightMin.right = removeMin(root.right);
// 结果树的左子树就是原节点的左子树
rightMin.left = root.left;
// 断开连接
root.left = root = null;
root.right = root = null;
return rightMin;
}
}
回到目录…
五、代码实现
public class BST {
private class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
private int size;
private TreeNode root;
public void add(int val) {
root = add(root, val);
}
//向以root为根节点的树添加元素
private TreeNode add(TreeNode root, int val){
//边界条件
if(root == null){
size ++;
return new TreeNode(val);
}
if(val < root.val){
//在左树中插入val
root.left = add(root.left, val);
}else if(val > root.val){
//在右树中插入val
root.right = add(root.right, val);
}
return root;
}
public boolean contains(int val) {
return contains(root, val);
}
//判断根节点为root的二叉树中有无val
private boolean contains(TreeNode root, int val) {
//边界条件
if(root == null){
return false;
}
if(root.val == val){
return true;
}else if(root.val > val){
return contains(root.left, val);
}else{
return contains(root.right, val);
}
}
public int findMin() {
//判空
if(size == 0){
throw new NoSuchElementException("BST is empty! Cannot find!");
}
return findMin(root);
}
//返回以root为根节点的二叉树的最小值
private int findMin(TreeNode root) {
if(root.left == null){
return root.val;
}
return findMin(root.left);
}
public int findMax() {
//判空
if(size == 0){
throw new NoSuchElementException("BST is empty! Cannot find!");
}
TreeNode node = root;
while (node.right != null){
node = node.right;
}
return node.val;
}
public int removeMin() {
//判空
if(size == 0){
throw new NoSuchElementException("BST is empty! Cannot remove!");
}
int min = findMin();
root = removeMin(root);
return min;
}
//删除以root为根节点的二叉树的最小值
private TreeNode removeMin(TreeNode root) {
//当左子树不存在时
if(root.left == null){
//当前的root就是待删节点，则先暂存右子树的地址
TreeNode right = root.right;
//断开连接，并置为空
root.right = root = null;
size --;
return right;
}
//左子树存在时，则递归去删左子树的最小值
root.left = removeMin(root.left);
return root;
}
public int removeMax() {
//日常判空
if(size == 0){
throw new NoSuchElementException("BST is empty! Cannot remove!");
}
int max = findMax();
root = removeMax(root);
return max;
}
//删除以root为根节点的二叉树的最大值
private TreeNode removeMax(TreeNode root) {
//当不存在右子树时
if(root.right == null){
//root就是最大值，待删节点
TreeNode left = root.left;
root.left = root = null;
size --;
return left;
}
//存在右子树时
root.right = removeMax(root.right);
return root;
}
public void remove(int val) {
root = remove(root, val);
}
private TreeNode remove(TreeNode root, int val) {
if(root == null){
throw new NoSuchElementException("BST中没有值为" + val + "的节点");
}else if(root.val < val){
root.right = remove(root.right, val);
return root;
}else if(root.val > val){
root.left = remove(root.left, val);
return root;
}else { //此时root就是待删节点
if(root.left == null){
return removeMin(root);
}
if(root.right == null){
return removeMax(root);
}
//此时，左右子树都不为空
//先找到右子树中的最小值节点
TreeNode rightMin = minNode(root.right);
//
rightMin.right = removeMin(root.right);
rightMin.left = root.left;
root.left = root = null;
root.right = root = null;
return rightMin;
}
}
//查找以root为根节点的树中最小值的节点
private TreeNode minNode(TreeNode root) {
if(root == null){
throw new NoSuchElementException("BST is empty! Not have minNode!");
}
TreeNode node = root;
while(node.left != null){
node = node.left;
}
return node;
}
@Override
public String toString() {
List list = new ArrayList<>();
inOrder(list, root);
return list.toString();
}
// 中序遍历
private void inOrder(List list, TreeNode root) {
if(root == null){
return;
}
inOrder(list, root.left);
list.add(root.val);
inOrder(list, root.right);
}
}
回到目录…
总结:
提示：这里对文章进行总结：
以上就是今天的学习内容，本文是Java数据结构的学习，认识了BST树，BST树的插入和删除操作，以及BST树的不平衡性。之后的学习内容将持续更新！！！
