树表查找(持续更新，暂时有项目，过几天再补，求谅解！！)

树表查找(持续更新，暂时有项目，过几天再补，求谅解！！)

树表查找

• 前言
• 二叉查找树(Binary Search Tree)
• • 定义
  • 性质
  • 操作
  • 实现
  • • 基本方法实现，无容器
  • 拓展

前言

• 先附上前面的查找算法和理解
• 哈希查找：哈希相关知识
• 常见的五种查找算法：常见查找算法
• 树表查找的知识在数据结构中有讲的很多了，它主要用于动态查找。
• 因为有项目，对二叉查找树进行优化的树过几天再写，也是写到这篇文章里，反正我这也没人看。。。持续更新！！

二叉查找树(Binary Search Tree)

定义

• 也叫二叉排序树和二叉搜索树。
• 左子树永远小于它的根结点，右子树永远的大于它的根结点，同时左子树和右子树也满足二叉查找树的定义。
• 没有相等的键值。

性质

• 中序遍历时产生有序数组。
• 时间复杂度：在插入和查找时时间复杂度均为O(logn)，二叉查找树目的是在最坏的情况下也有较好的时间复杂度。

操作

• 查找：对树遍历呗，一般用BFS广度优先查找，对二叉查找树来说，每次比较都等于剪掉一般的树，从根节点开始，如果目标大于根结点就进右子树，目标小于根结点就进左子树，所以类似二分查找，在查找时达到O(logn)的时间复杂度。
• 插入：和查找操作一样的，也是把目标和根结点比较，大了就进右子树，小了就进左子树，找到位置对应插入就行了。
• 删除：分三种情况：
  • 删除叶子结点：删了就删了，直接找到它删掉就完事了。
  • 删除有一个子结点的结点：把它和它的子节点的位置换一下，删掉就行了。
  • 删除有两个子节点的结点(可能有子树)：用中序遍历找到目标的后继节点，也就是在中序遍历产生的顺序表中目标的下一个元素，把它和目标换个位置，然后删掉就行了。

实现

基本方法实现，无容器

/*** @Author: 胡奇夫* @QQ: 1579328766* @CreateTime: 2020-07-05-22-31* @Descirption: 二叉搜索树普通方法*/
public class BinarySearchTree {private class Node{int val;Node left;Node right;}private Node root;public void insert(int key){Node n = new Node();n.val = key;if(root == null)root = n;else{Node parent = new Node();Node current = root;while(true){parent = current;if(key > current.val){current = current.right;if(current == null)parent.right = n;}else{current = current.left;if(current == null)parent.left = n;}}}}
}

拓展

• 二叉查找树是基础，对它进行优化产生了AVL树，红黑树和平衡二叉树，还有什么2-3查找树啥的，再拓展就是数据库的B树和B+树。
• 过几天就更新树！！！