Meta tags:

Headings (most frequently used words):

books, who, nil, is, not, null, saturday, july, 28, 2012, blogs, here, complete, works, somewhat, popular, bits, and, bytes, cares, peter, read, book, montage, reuse, recycle, reanimate, avl, trees, turn, 50,

Text of the page (most frequently used words):
and (20), trees (15), the (8), october (7), april (7), july (7), avl (7), november (6), are (5), peter (5), books (5), february (5), may (5), december (5), that (5), not (4), share (4), september (4), june (4), 2012 (4), january (4), were (4), this (3), book (3), favorite (3), have (3), here (3), posts (3), data (3), about (3), them (3), they (3), 1962 (3), students (3), balanced (3), search (3), blog (2), views (2), with (2), even (2), who (2), reading (2), armor (2), maps (2), somewhat (2), turn (2), complete (2), old (2), games (2), computers (2), free (2), fröhlich (2), teaching (2), first (2), published (2), red (2), black (2), what (2), treaps (2), take (2), well (2), since (2), efficient (2), for (2), ordered (2), some (2), things (2), either (2), still (2), should (2), nil (2), null (2), simple, theme, powered, blogger, content, licensed, under, expressed, own, employer, creative, commons, attribution, sharealike, unported, license, reuse, recycle, reanimate, ratings, join, goodreads, club, reviews, read, montage, cares, almost, albums, required, arnesonisms, gygaxisms, quotes, bits, bytes, linux, lenovo, z585, editions, class, part, isle, dread, better, justifying, exploration, movement, strict, spell, installing, lfs, qemu, cobalt, qube, raq, notes, ternary, operator, skills, riffing, 2d6, reaction, rolls, popular, 2008, 2009, 2010, 2011, 2013, 2014, 2015, march, 2016, 2017, 2018, august, 2020, 2021, works, view, profile, like, dig, software, culture, believe, people, organizations, inalienable, rights, munich, germany, blogs, subscribe, atom, home, older, newer, pinterest, facebook, blogthis, email, comments, posted, 600, 226, structures, summer, session, course, right, now, covered, yesterday, was, ranting, suddenly, realized, eager, perplexed, blame, brain, never, been, able, develop, good, which, gather, respectable, schools, supposed, teach, anyway, because, little, code, yet, perform, but, feel, owe, least, one, tree, just, implement, hence, started, wonder, structure, sets, did, checking, found, 1970, symmetric, binary, 1972, finger, 1977, 1978, splay, 1985, 1989, losen, bit, include, demand, more, provide, fewer, general, operations, could, consider, these, tries, 1960, heaps, 1964, far, can, tell, after, quick, indeed, oldest, way, maintain, dynamic, set, map, trouble, implementing, today, guess, means, haven, made, lot, progress, our, proverbial, hats, off, nod, quiet, thanks, figuring, out, how, work, before, most, born, landis, adelson, velskii, messy, deterministic, intuition, saturday, random, osity, politics, life, stuff,

Text of the page (random words):
nil is not null july 2012 nil is not null random osity about computers and games and politics and life and stuff saturday july 28 2012 avl trees turn 50 i am teaching 600 226 data structures as a summer session course right now and we covered avl trees yesterday as i was ranting about them i suddenly realized that they were first published in 1962 and here i am in 2012 still teaching them to my eager and somewhat perplexed students so blame my brain i have never been able to develop a good intuition about red black trees which i gather is what respectable schools are supposed to teach my favorite balanced trees are treaps anyway because they take so little code yet perform so well but i feel that i owe my students at least one deterministic balanced search tree and 2 3 4 trees are just so messy to implement hence avl i started to wonder since avl trees were published in 1962 were they the first efficient data structure for ordered sets or maps so i did some checking and here is what i found avl trees 1962 b trees 1970 symmetric binary b trees 1972 finger trees 1977 red black trees 1978 splay trees 1985 treaps 1989 if we losen things up a bit and include things that either demand more of the data or provide fewer general operations we could consider these as well tries 1960 heaps 1964 so as far as i can tell after a quick search avl trees are indeed the oldest efficient way to maintain a dynamic ordered set or map and since students still have some trouble implementing them today i guess that means we either haven t made a lot of progress or we should take our proverbial hats off and nod a quiet thanks to adelson velskii and landis for figuring out how balanced search trees should work before most of us were even born posted by peter fröhlich at 11 17 pm no comments email this blogthis share to x share to facebook share to pinterest newer posts older posts home subscribe to posts atom who blogs here peter fröhlich munich germany i like old games and old computers i dig free software and free culture and i believe that people not organizations have inalienable rights view my complete profile complete works 2021 2 june 2 2020 3 november 1 august 1 july 1 2018 2 may 1 january 1 2017 3 october 2 july 1 2016 10 december 1 october 1 june 1 april 2 march 1 february 2 january 2 2015 22 december 9 november 2 october 3 may 2 april 4 february 2 2014 21 december 6 november 3 may 1 april 4 february 2 january 5 2013 47 december 4 november 2 october 1 september 1 july 7 june 16 may 11 april 2 february 2 january 1 2012 6 december 1 september 1 july 1 avl trees turn 50 april 3 2011 4 october 4 2010 13 july 2 june 8 may 2 april 1 2009 9 november 2 october 1 september 4 april 1 february 1 2008 9 november 1 october 2 september 6 somewhat popular riffing on 2d6 reaction rolls skills the d6 in b x ternary operator in go cobalt qube 2 raq 2 notes installing lfs with qemu the strict reading of spell books in b x justifying exploration movement isle of dread better maps editions of armor class part 1 no armor linux on lenovo z585 bits and bytes favorite quotes arnesonisms gygaxisms required reading almost albums who cares books books books peter s read book montage peter s favorite books share book reviews and ratings with peter and even join a book club on goodreads reuse recycle reanimate the content of this blog is licensed under a creative commons attribution sharealike 3 0 unported license the views expressed in this blog are my own and not the views of my employer simple theme powered by blogger