基于双键BST的数据结构
我需要在数据结构中存储具有正方形底座（由底座边和高度表示）的盒子，操作包括：插入、删除和搜索边和高度值都不小于给定盒子的最小体积盒子。数据结构应该基于二分搜索树，所以我可以简单地平衡它们（红黑/AVL）。我发现一棵树是不够的，所以我试着把盒子分成边值和高值。提前感谢您的任何建议，支持插入、删除的对数时间，以及类似于n*LG(m)的搜索（给定n，m是边和高度值的数量）。
共有1个答案
类似的问题请看我在这里的回答。
您需要的是一个同时保存属于两个树的信息的节点。每棵树按不同的键（宽度、体积等）排序。
这样，对于O(logn)的复杂性，您可以找到一个匹配所有需求的框。
-
二叉树 ： 闲话少说，直接上代码： <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>BST</title> </head> <body> <script> //结点 function Node(data,left,right){ this.data=data; t
-
基于锁的并发数据结构设计，需要确保访问线程持有锁的时间最短。对于只有一个互斥量的数据结构来说，这十分困难。需要保证数据不被锁之外的操作所访问到，并且还要保证不会在固有结构上产生条件竞争(如第3章所述)。当你使用多个互斥量来保护数据结构中不同的区域时，问题会暴露的更加明显，当操作需要获取多个互斥锁时，就有可能产生死锁。所以，在设计时，使用多个互斥量时需要格外小心。 在本节中，你将使用6.1.1节中的
-
问题内容： 我知道有三种不同的，流行的非SQL数据库类型。 键/值：Redis，Tokyo Cabinet，Memcached ColumnFamily：Cassandra，HBase 文件：MongoDB，CouchDB 我已经读了很长的博客，但对它的了解却很少。 我知道关系数据库，并且在MongoDB / CouchDB等基于文档的数据库中徘徊。 谁能告诉我这些和清单上的两个前者之间的主要区别
-
主要内容：一、基础数据结构,二、数据结构的初步分析,三、数据结构的使用,四、总结一、基础数据结构 在整体上把握了Redis的架构流程后，先分析一下基础的数据结构。这样，一个是对以后各个模块分别分析时，不会因为对数据结构的陌生而增加源码分析的难度，又可以通过分析基础的数据结构来初步掌握redis的设计风格。在redis中，共有五种基础数据结构： string:字符串，在KV结构中，Key都是字符串类型。其它的数据结构可以说是从这个基础上衍生出来的。它可以存储字符，复杂的字符串（
-
关键数据结构 为了表示一个设备，需要有对应的数据结构，ucore为此定义了struct device，其描述如下： struct device { size_t d_blocks; //设备占用的数据块个数 size_t d_blocksize; //数据块的大小 int (*d_open)(struct device *dev, uint3
-
主要内容：一、quicklist,二、源码分析,三、总结一、quicklist 再看一下quicklist，它是从Redis3.2才提供的一个数据结构。从字面意思上理解，这个应该比list快。但是同样是list，为什么它要快？就得找一下原因。在普通的list中，可以通过拥有的前向和后向指针进行前后的遍历和查找。但是，当数据量大时，这两个指针占用的空间就非常明显了。而在前面的ziplist中，可以看到，通过指示本Entry的长度配合相关标识，就可以去除这
-
主要内容：一、ziplist压缩列表,二、源码分析,三、总结一、ziplist压缩列表 压缩列表是HASH和跳表的小数据时的数据结构，这个在前面提到过。压缩列表的定义和使用其实在源码的头部说明中是很清楚的。看一下英文的注释： The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both st
-
主要内容：一、skiplist 跳表,二、源码分析,三、总结一、skiplist 跳表 跳表这个数据结构是新生的，在学习数据结构的时候儿是没有这个的。当然，也可以理解成是对数据结构的进一步的封装，这样理解的话，可能就会更准确一些。为什么叫跳表？想想生活中跳的动作，一般人走路是一步一步的走，而如果跳跃的话，一下子可以走好几步，但是付出的代价就是要多费些力气。 其实跳表也是如此，正常的链表list，访问的时候儿是从头到尾（或者反过来）一条条的遍历，而跳表由于多