赤黒木の本質 - Qiita
この記事はデータ構造とアルゴリズム Advent Calendar 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思いついたのか見当がつかずとても不思議に感じました。 しかし、その後赤黒木の成り立ちやその基になったデータ構造について知ると、トリッキーに見えた定義がとても自然であることを実感しました。 おそらく知っている人は当たり前に知っている内容だとは思いますが、知らない人
Designing far memory data structures: think outside the box | the morning paper
the morning paper a random walk through Computer Science research, by Adrian Colyer Made delightfully fast by strattic Designing far memory data structures: think outside the box Aguilera et al., HotOS’19 Last time out we looked at some of the trade-offs between RInKs and LInKs, and the advantages of local in-memory data structures. There’s another emerging option that we didn’t talk about there:
Elastic Binary Trees - ebtree
Brain dumps. Reports about experiments, ideas, and various stuff that's more useful on the net than written on paper stacked on my desk. Administrivia This article was initially posted on Wikipedia in 2008, which explains why it's written at the 3rd person and looks familiar to articles on binary trees. A few moderators decided that the article was only self-promotion and removed it without notifi
research!rsc: An Encoded Tree Traversal
Every basic data structures course identifies three ways to traverse a binary tree. It’s not entirely clear how to generalize them to k-ary trees, and I recently noticed an unexpected ordering that I’d like to know more about. If you know of references to this ordering, please leave a comment or email me (rsc@swtch.com). Binary Tree Orderings First a refresher about binary-tree orderings to set up
GitHub - mandliya/algorithms_and_data_structures: 180+ Algorithm & Data Structure Problems using C++
dbs-028.dvi
Foundations and Trends R � in Databases Vol. 3, No. 4 (2010) 203–402 c � 2011 G. Graefe DOI: 10.1561/1900000028 Modern B-Tree Techniques By Goetz Graefe Contents 1 Introduction 204 1.1 Perspectives on B-trees 204 1.2 Purpose and Scope 206 1.3 New Hardware 207 1.4 Overview 208 2 Basic Techniques 210 2.1 Data Structures 213 2.2 Sizes, Tree Height, etc. 215 2.3 Algorithms 216 2.4 B-trees in Databases
興味深いデータ構造：BK木 | POSTD
BK木とは、 距離空間 内のデータをインデックス化する目的に特化した、木構造を指します。距離空間は基本的に、要素の組 $ (a,b) $ 全てについて距離関数 $ d(a,b) $ を持つオブジェクトの集合です。この距離関数は正しく動作することを保証するために、一連の公理を満たしていなければなりません。これが必要になる理由は、後述の「検索」のセクションできちんと説明します。 BK木のデータ構造は、一連のキーを検索し、与えられた検索キーの値に最も近いキーを見つける問題の解決策として、 1973年にBurkhardとKellerが提案したもの です。この問題を解決する素朴な方法は、要素の組に含まれる各要素と検索キーの値を単純に比較することです。一定の時間内に比較が完了した場合、この検索の解は $ O(n) $ となります。一方、BK木を採用すると、この時実行する比較の回数を減らせる可能性が高く
Purely Functional Data Structures in Scala
Slides of my talk for Scala NSK Usergroup. Video in Russian: http://www.youtube.com/watch?v=fWnaW3CP7OI
What's new in purely functional data structures since Okasaki?
New purely functional data structures published since 1998: 2001: Ideal Hash Trees, and its 2000 predecessor, Fast And Space Efficient Trie Searches, by Phil Bagwell: Apparently used as a fundamental building block in Clojure's standard library. 2001: A Simple Implementation Technique for Priority Search Queues, by Ralf Hinze: a really simple and beautiful technique for implementing this important
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Lectures in Advanced Data Structures (6.851)
A Specialized B-Tree for Concurrent Datalog Evaluation | Soufflé • A Datalog Synthesis Tool for Static Analysis
Functional Data Structures
http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf
Maximize Cache Performance with this One Weird Trick: An Introduction to Cache-Oblivious Data Structures
On Disk IO, Part 3: LSM Trees
ダブル配列の実装方法
trillian/VerifiableDataStructures.pdf at master · google/trillian · GitHub
Split-ordered linked list: lock free hash table
Linked Lists are Still Hard - Stephen Brennan
GitHub - usethesource/capsule: The Capsule Hash Trie Collections Library
