Sorted heap trees
in [Theory]
|
Prev: find all directed paths between a source and destination
Next: Goedell's Incompleteness Reconsidered
From: Richard Harter on 9 Apr 2008 17:35 This is a repost to comp.theory. I'm looking at a data structure that I have (re)invented that I am calling a sorted heap tree. I dare say there is an official name but I haven't a clue as to what it might be. What I am looking for are references, preferably on-line, and anything useful I can snarf up. A sorted heap tree is a heap tree with the further requirement that left and right subtrees are partitions. That is, all of the elements of the left subtree are less than the elements of the right subtree. For example, here is a sorted heap tree in outline form. T: 1 L: 2 L: 3 L: 4 R: 5 R: 6 L: 7 R: 8 R: 9 L: 10 L: 11 R: 12 R: 13 L: 14 R: 15 This is a sorted tree, albeit not a BST. The recursive traversal routine is procedure traverse node print node.data traverse node.left traverse node.right There are four types of sorted heap trees, because we can exchange left and right, and the direction of ordering. Searches are necessarily asymetric. That is, in this tree we first compare with the right child and then with the left. Sorted heap trees are analogous with binary search trees - for every type of BST, e.g., splay trees, AVL trees, etc, there are corresponding sorted heap trees. It turns out that there are some special situations where a sorted heap tree is better than an ordinary BST. I am wondering if anyone knows the proper name for these type of trees and of any references, e.g., properties, uses, adaptations of standard algorithms for them. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Save the Earth now!! It's the only planet with chocolate.
From: matt.timmermans on 9 Apr 2008 22:16 On Apr 9, 5:35 pm, c...(a)tiac.net (Richard Harter) wrote: > It turns out that there are some special situations where a > sorted heap tree is better than an ordinary BST. I am wondering > if anyone knows the proper name for these type of trees and of > any references, e.g., properties, uses, adaptations of standard > algorithms for them. Hi Richard, There are a wide variety of well-known ways for laying out a tree in an array, and the issue of layout is usually considered separately from what is actually in the tree nodes or how the node keys are ordered. The layout used by a heap is called the "breadth-first layout" in the literature. It has many uses, including as a benchmark against which various cache-oblivious layouts are compared, so if you google for "breadth-first layout", you'll find lots of interesting things. The particular ordering of nodes that you're using is called "preorder", but the word is usually to refer to an order in which nodes are visited, not an ordering for the nodes' keys. The characteristics of searching in your tree are similar to those of a "finger search tree", so you may want to goole for that to get some more information about the application you have in mind. Cheers, Matt
From: Richard Harter on 10 Apr 2008 01:25
On Wed, 9 Apr 2008 19:16:44 -0700 (PDT), matt.timmermans(a)gmail.com wrote: >On Apr 9, 5:35=A0pm, c...(a)tiac.net (Richard Harter) wrote: >> It turns out that there are some special situations where a >> sorted heap tree is better than an ordinary BST. =A0I am wondering >> if anyone knows the proper name for these type of trees and of >> any references, e.g., properties, uses, adaptations of standard >> algorithms for them. > >Hi Richard, > >There are a wide variety of well-known ways for laying out a tree in >an array, and the issue of layout is usually considered separately >from what is actually in the tree nodes or how the node keys are >ordered. > >The layout used by a heap is called the "breadth-first layout" in the >literature. It has many uses, including as a benchmark against which >various cache-oblivious layouts are compared, so if you google for >"breadth-first layout", you'll find lots of interesting things. > >The particular ordering of nodes that you're using is called >"preorder", but the word is usually to refer to an order in which >nodes are visited, not an ordering for the nodes' keys. The >characteristics of searching in your tree are similar to those of a >"finger search tree", so you may want to goole for that to get some >more information about the application you have in mind. Many thanks for the comments and suggestions. I wasn't considering layout at all and wasn't thinking in terms of embedding a tree in an array. AFAIK the heap data structure is usually defined as a tree - the breadth first layout in an array is a convenience. That said, a search on "breadth-first layout" does turn up some interesting things. It occurs to me that the layout I used might have been misleading. I just listed the nodes sequentially because of the limitations of ascii art. I'm not sure that I follow your thought that the search characteristics are similar to those of a finger search tree. Could you elucidate. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Save the Earth now!! It's the only planet with chocolate. |