wordpress 七牛,北京seo公司优化网络可见性,海口自助建站系统,食品网站设计文章目录 前言参考目录学习笔记1#xff1a;二叉树与二叉搜索树定义1.1#xff1a;二叉树定义1.2#xff1a;二叉搜索树定义1.3#xff1a;Java定义1.4#xff1a;BST基本实现1.5#xff1a;BST demo 演示1.5.1#xff1a;节点搜索成功命中演示1.5.2#xff1a;节点搜索… 文章目录 前言参考目录学习笔记1二叉树与二叉搜索树定义1.1二叉树定义1.2二叉搜索树定义1.3Java定义1.4BST基本实现1.5BST demo 演示1.5.1节点搜索成功命中演示1.5.2节点搜索未命中演示1.5.3节点插入演示1.6BST 查找Java 实现1.7BST 插入Java 实现1.8树的形状1.9BSTs 与快速排序分区的一致性1.10小结2排序操作2.1向上取整与向下取整2.1.1向下取整过程演示2.1.2向下取整代码实现2.2小结3删除操作3.1删除最大键和删除最小键3.1.1删除最小项过程演示3.1.2删除最小项代码实现3.2删除操作3.2.1Hibbard 删除3.2.2Hibbard 删除代码实现3.3删除操作分析3.4小结 前言
本文的主要内容是 二叉搜索树 binary search trees以下简称 BST以及其相关的 API 操作介绍。
参考目录
B站 普林斯顿大学《Algorithms》视频课 请自行搜索。主要以该视频课顺序来进行笔记整理课程讲述的教授本人是该书原版作者之一 Robert Sedgewick。微信读书《算法第4版》 本文主要内容来自《3.2 二叉查找树》官方网站 有书本配套的内容以及代码
学习笔记
注1下面引用内容如无注明出处均是书中摘录。 注2所有 demo 演示均为视频 PPT demo 截图。
1二叉树与二叉搜索树定义
定义BST是对称顺序的二叉树。
1.1二叉树定义 二叉树要么为空 要么由两个不相交的二叉树组成即左子树和右子树。 进一步理解有点绕
一个二叉树可以是一个空树null。否则它是一个包含一个根节点的树该节点连接到两个独立的二叉树上分别称为其左子树和右子树且左子树和右子树也是二叉树结构。 二叉树是一种显式数据结构显式树结构与之相对应的堆是一种隐式数据结构用数组隐式表示树。
1.2二叉搜索树定义 对称顺序。每个节点都有一个键key并且每个节点的键都满足以下条件 大于其左子树中所有节点的键。小于其右子树中所有节点的键。 进一步理解
对于二叉树中的任意节点其键值严格大于其左子树中所有节点的键值。同时该节点的键值严格小于其右子树中所有节点的键值。 1.3Java定义
一个二叉搜索树BST是一个指向根节点的引用。
一个节点由四个部分组成
一个键Key和一个对应的值Value。分别指向其左子树更小的 key和右子树更大的 key的引用。 1.4BST基本实现
edu.princeton.cs.algs4.BST 1.5BST demo 演示
查找如果更小向左移动如果更大向右移动如果相等搜索命中。
1.5.1节点搜索成功命中演示
搜索 H
初始状态 与根节点 S 比较更小左移 与节点 S 左子树节点 E 比较更大右移 与节点 E 右子树节点 R 比较更小左移 与节点 R 左子树节点 H 比较相等搜索命中 1.5.2节点搜索未命中演示
搜索 G
初始状态 与根节点 S 比较更小左移 与节点 S 左子树节点 E 比较更大右移 与节点 E 右子树节点 R 比较更小左移 与节点 R 左子树节点 H 比较更小左移 H 左移为空链接查找未命中并返回 null 1.5.3节点插入演示
插入如果更小向左移动如果更大向右移动如果为 null插入。
插入 G
初始状态 移动路径与 #1.5.2 查找类似直到节点 H 左子树为 null插入节点 G G 完整移动路线图 1.6BST 查找Java 实现
edu.princeton.cs.algs4.BST#get 开销 一次结束于给定结点的命中查找所需的比较次数为查找路径的深度加1。 1.7BST 插入Java 实现
edu.princeton.cs.algs4.BST#put 1.8树的形状
许多 BSTs 对应同一组keys一次查找 / 插入所需的比较次数为查找路径的深度加1。 注树的形状取决于键被插入的先后顺序。
1.9BSTs 与快速排序分区的一致性 命题C。在由N个随机键构造的二叉查找树中查找命中平均所需的比较次数为2lnN约1.39lgN。 命题D。在由N个随机键构造的二叉查找树中插入操作和查找未命中平均所需的比较次数为2lnN约1.39lgN。 参考 快速排序1.4.3平均案例分析。
1.10小结 书里面在章节末尾也有给出相关的表格 表3.2.2 简单的符号表实现的成本总结 2排序操作 Now,we’re going to take a look at ordered symbol table operations using the binary search tree data structure as the underlying implementation. 现在我们将要探讨如何利用二叉搜索树这一数据结构作为底层实现来进行有序符号表操作。 相关的所有章节
3.2.3.1 最大键和最小键 Minimum and maximum.3.2.3.2 向上取整和向下取整 Floor and ceiling.3.2.3.3 选择操作 Selection.3.2.3.4 排名 Rank.
2.1向上取整与向下取整
2.1.1向下取整过程演示 图3.2.10 计算floor()函数 2.1.2向下取整代码实现
edu.princeton.cs.algs4.BST#floor 2.2小结 3删除操作
相关的所有章节
3.2.3.5 删除最大键和删除最小键 Delete the minimum and maximum.3.2.3.6 删除操作 Delete.3.2.3.7 范围查找 Range search.3.2.3.8 性能分析
3.1删除最大键和删除最小键
3.1.1删除最小项过程演示
向左移动直到找到左链接为空的节点。将该节点替换为其右侧链接。更新子树计数。 图3.2.12 删除二叉查找树中的最小结点 3.1.2删除最小项代码实现
edu.princeton.cs.algs4.BST#deleteMin 3.2删除操作
3.2.1Hibbard 删除
情况一没有子节点 情况二一个子节点 情况三两个子节点 书中关于删除过程操作的描述 图3.2.13 二叉查找树中的删除操作 3.2.2Hibbard 删除代码实现
edu.princeton.cs.algs4.BST#delete 3.3删除操作分析 简单汉化一下
不能令人满意的结果不对称。 令人惊讶的事实树不再随机 平方操作 长期存在的开放问题简单高效的 BST 删除。 That’s another one like merging in place, that you’d think there ought to be an easy way to do it, but in 50 years, no one’s really discovered one. 这是另一种类似原地归并的方法你会认为应该有一种简单的方法可以做到这一点但 50 年来没有人真正找到解决方法。 3.4小结 下一节红黑二叉搜索树Red-black BST保证所有操作的对数性能。 But the delete operation for Binary Search Trees shows us the kind of complexity that we can encounter with working with these kinds of data structures. BST 删除操作向我们展示了当遇到类似数据结构时我们可能遇到的复杂情况。 完
