Closed sailei1 closed 5 years ago
数组 有序 有下标 栈 有序 后进先出 队列 有序 先进先出 链表 无序 记录周围的关系(比如前一个 后一个) 集合 无序且唯一 字典 map key value 无序
散列表 hashtable
数据中的键通过一个散列函数的计算后返回一个数据存放的地址，因此可以直接通过地址来访问它的值，这样的查找就非常快。避免冲突
二叉树 一般节点分为key 左节点 右节点 以当前节点 key 为基准值， 左节点是小于key值的 右节点是大于key值的 插入 1插入一个全新节点 左右节点关系null 2 验证这个树 有没有 根节点 如果没有 它就是根节点 3 如果有根节点，根据新节点插入值的大小 如果新节点值小于当前节点值 检查左侧 ，如果当前节点没有左节点关系，新节点放在当前节点左侧 如果新节点 大于当前节点值 检查右侧，如果当前节点没有右节点关系，新节点 放在当前当前节点右侧 4 重复第3步 直到找到合适的位置 插入 最大值 最小值 一般左边最深层 是最小值 右边最深层是最大值
查询 根据值的大小 去递归取区间 小于取左边 大于取右边 等于 返回，没找到 返回null
移除节点
走查询逻辑 找到目标节点 如果没找到 返回null。 如果找到了 1 左右节点关系为空 node=null 直接移除 2 左右节点只有一个的时候 跳过这个节点，直接将父节点指向它的子节点 3 左右节点关系都有的时候 (1) 当找到了需要移除的节点后，需要找到它右边子树中最小的节点(它的继承者。 (2) 然后，用它右侧子树中最小节点的键去更新这个节点的值。通过这一步，我 们改变了这个节点的键，也就是说它被移除了。 (3) 但是，这样在树中就有两个拥有相同键的节点了，这是不行的。要继续把右侧子树中的 最小节点移除，毕竟它已经被移至要移除的节点的位置了。 (4) 最后，向它的父节点返回更新后节点的引用。
思路 找右节点的最小值 （区间） 替换当前节点 同时 移除最小值新节点
数组 有序 有下标 栈 有序 后进先出 队列 有序 先进先出 链表 无序 记录周围的关系(比如前一个 后一个) 集合 无序且唯一 字典 map key value 无序
散列表 hashtable
数据中的键通过一个散列函数的计算后返回一个数据存放的地址，因此可以直接通过地址来访问它的值，这样的查找就非常快。避免冲突
二叉树 一般节点分为key 左节点 右节点 以当前节点 key 为基准值， 左节点是小于key值的 右节点是大于key值的 插入 1插入一个全新节点 左右节点关系null 2 验证这个树 有没有 根节点 如果没有 它就是根节点 3 如果有根节点，根据新节点插入值的大小
如果新节点值小于当前节点值 检查左侧 ，如果当前节点没有左节点关系，新节点放在当前节点左侧 如果新节点 大于当前节点值 检查右侧，如果当前节点没有右节点关系，新节点 放在当前当前节点右侧 4 重复第3步 直到找到合适的位置 插入 最大值 最小值 一般左边最深层 是最小值 右边最深层是最大值
查询 根据值的大小 去递归取区间 小于取左边 大于取右边 等于 返回，没找到 返回null
移除节点
走查询逻辑 找到目标节点 如果没找到 返回null。 如果找到了
1 左右节点关系为空 node=null 直接移除 2 左右节点只有一个的时候 跳过这个节点，直接将父节点指向它的子节点 3 左右节点关系都有的时候 (1) 当找到了需要移除的节点后，需要找到它右边子树中最小的节点(它的继承者。 (2) 然后，用它右侧子树中最小节点的键去更新这个节点的值。通过这一步，我 们改变了这个节点的键，也就是说它被移除了。 (3) 但是，这样在树中就有两个拥有相同键的节点了，这是不行的。要继续把右侧子树中的 最小节点移除，毕竟它已经被移至要移除的节点的位置了。 (4) 最后，向它的父节点返回更新后节点的引用。
思路 找右节点的最小值 （区间） 替换当前节点 同时 移除最小值新节点