Java 数据结构与算法之树（BST）

Binary Search Tree历史。,二叉搜索树算法是由包括 PF Windley、Andrew Donald Booth、Andrew Colin、Thomas N. Hibbard 在内的几位研究人员独立发现的。该算法归功于 Conway Berners-Lee 和 David Wheeler ，他们在 1960 年使用它在磁带中存储标记数据。最早和流行的二叉搜索树算法之一是 Hibbard 算法。,二叉搜索树（Binary Search Tree），也称二叉查找树。如果你看见有序二叉树（Ordered Binary tree）、排序二叉树（Sorted Binary Tree）那么说的都是一个东西。,,二叉搜索树在日常开发中使用的场景还是比较多的，例如基于组合模式实现的规则引擎，它就是一颗二叉搜索树。但类似这样的开发中用到的二叉树场景，都是基于配置生成，所以组合出来的节点也更加方便控制树高和平衡性。这与 Java API HashMap 中的红黑树这样为了解决插入节点后仍保持树的平衡性是有所不同的。,所以二叉搜索树也是一颗没有经过调衡的基础性数据结构，在一定概率上它完成有可能退化成链表，也就是从近似O(logn)的时间复杂度退化到O(n)。关于二叉搜索树的平衡解决方案，包括；AVL树、2-3树、红黑树等，小傅哥会在后续的章节继续实现。,二叉搜索树是整个树结构中最基本的树，同时也是树这个体系中实现起来最容易的数据结构。但之所以要使用基于二叉搜索树之上的其他树结构，主要是因为使用数据结构就是对数据的存放和读取。那么为了提高吞吐效率，则需要尽可能的平衡元素的排序，体现在树上则需要进行一些列操作，所以会有不同的结构树实现。,而实现二叉搜索树是最好的基础学习，了解基本的数据结构后才更容易扩展学习其他树结构。,用于组成一颗树的节点，则需要包括；值和与之关联的三角结构，一个父节点、两个孩子节点。如果是AVL树还需要树高，红黑树还需要染色标记。,首先判断插入元素时候是否有树根，没有则会把当前节点创建出一颗树根来。,如果当前树是有树根的，则对插入元素与当前树进行一个节点遍历操作，找到元素可以插入的索引位置 parent（挂到这个父节点下）。也就是 search 搜索过程。,最后就是插入元素，通过给插入值创建一个 Node 节点，并绑定它的父元素，以及把新元素挂到索引到的 parent 节点下。,值查找的过程，就是对二叉搜索树的遍历，不断的循环节点，按照节点值的左右匹配，找出最终相当的值节点。,,待删除节点14，判断此节点的父节点的孩子节点，哪个等于14，找出左右,把待删节点的右孩子节点，挂到删除节点的右节点,给待删节点的右孩子节点，设置上父节点,,为了方便观察树结构的变化，这里小傅哥找了一些资料资料，一种是我们可以通过程序来打印（类似大家之前打印99乘法表，另外是使用线上的可视化图：https://visualgo.net/zh/bst?slide=1）,因为你测试时的随机数不同，可能会出现很多不同结构的二叉搜索树，也可能是一个类似链表结构的退化树。,这个案例就是 4.2 删除双节点 的案例，删除了节点64以后，节点72被提取上来使用。读者伙伴也可以尝试删除其他节点测试验证。,二叉搜索树结构简述&变T的可能也让手写。,二叉搜索树的插入、删除、索引的时间复杂度。,二叉搜索树删除含有双子节点的元素过程叙述。,二叉搜索树的节点都包括了哪些信息。,为什么Java HashMap 中说过红黑树而不使用二叉搜索树。,