从bst到lsm的进阶之路-编程思维

前言 相信大家之前都了解过很多种数据结构,我之前总是两两的,也就是从局部上去进行比较,没有从整体上进行这些树的发展脉络进行梳理,因此经常看完没多久就忘了。看来确实是需要从本源出发,不仅要知其然还要知其所以然,了解清楚前因后果,不仅可以方便我们记忆,更有利于增加我们的理解深度。实际上任何事物的出现都是有他出现的必要性,当某个事物达到瓶颈之后,必然会出现新的事务来弥补它的不足。好的,废话不多说了,今

leetcode 315 count of smaller numbers after self - 编程思维

题目细节描述参看leetcode。 今天的重头戏 LC315 Count of Smaller Numbers After Self.在讲这个题目之前,请思考这个问题。在BST找到所有比Node P小的节点个数。利用inorder tarvseral我们一直走BST并计数,找到p点就返回计数得到的值。时间复杂度worst case O(n).如果我们要找到的是好多节点的值,如果还用这种方法,时间

平衡二叉树——avl - 编程思维

AVL 之前写过的二叉排序树(BST)在插入、删除和查找等基本操作的平均时间为O(logN),但在最坏的情况下,这些基本运算的时间均会增至O(n)(因为退化成了链表)。为了避免这些情况发生,人们研究了许多种动态平衡的方法,使得在树中插入或删除元素时,通过调整树的形态来保持树的“平衡”,使之既保持BST的性质不变又保证树的高度在任何情况下均为O(logN),从而确保树上的基本运算在最坏情况下的时间

leetcode109. convert sorted list to binary search tree - 编程思维

题目要求 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 给一个按照递增顺序排列的链表。将该链表转化为平衡二叉树。 思路和代码 在这里需要注意的是,因为提供的数据结构为链表,所以我们必须顺序遍历才能知道该链表的长度以及该链表

二叉树 - 编程思维

本文引用至: 二叉树 树, 实际上是一个非常重要的数据结构, 比如,我们的进程树,文件树,HTML节点树等. 都是依赖这样的一个结构. 树,实际上是一种非线性的数据结构,但是他们是有序的. 如下图 每一个节点下面,都有本身的value,parent_node,child_node属性(除了根节点). 树的基本概念 每颗树都有根节点,叶子节点, 子节点,父节点的属性. 如果按 树组分的话, 还可

bst - 编程思维

江南无所谓 聊赠一枝春 前言 二叉搜索树插入 二叉搜索树遍历 二叉搜索树高度 二叉搜索树最大值 什么是二叉搜索树 满足条件: 左节点值 < 根节点值 < 右节点值 定义树节点 typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode