Self-Adjusting Binary Search Trees: What Makes Them Tick? View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015-11-12

AUTHORS

Parinya Chalermsook , Mayank Goswami , László Kozma , Kurt Mehlhorn , Thatchaphol Saranurak

ABSTRACT

Splay trees (Sleator and Tarjan [11]) satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs) satisfy the access lemma? After each access, self-adjusting BSTs replace the search path by a tree on the same set of nodes (the after-tree). We identify two simple combinatorial properties of the search path and the after-tree that imply the access lemma. Our main result(i) implies the access lemma for all minimally self-adjusting BST algorithms for which it was known to hold: splay trees and their generalization to the class of local algorithms (Subramanian [12], Georgakopoulos and McClurkin [7]), as well as Greedy BST, introduced by Demaine et al. [5] and shown to satisfy the access lemma by Fox [6],(ii) implies that BST algorithms based on “strict” depth-halving satisfy the access lemma, addressing an open question that was raised several times since 1985, and(iii) yields an extremely short proof for the O(logn loglogn) amortized access cost for the path-balance heuristic (proposed by Sleator), matching the best known bound (Balasubramanian and Raman [2]) to a lower-order factor.One of our combinatorial properties is locality. We show that any BST-algorithm that satisfies the access lemma via the sum-of-log (SOL) potential is necessarily local. The other property states that the sum of the number of leaves of the after-tree plus the number of side alternations in the search path must be at least a constant fraction of the length of the search path. We show that a weak form of this property is necessary for sequential access to be linear. More... »

PAGES

300-312

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-48350-3_26

DOI

http://dx.doi.org/10.1007/978-3-662-48350-3_26

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1037928027


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/03", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Chemical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0303", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Macromolecular and Materials Chemistry", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chalermsook", 
        "givenName": "Parinya", 
        "id": "sg:person.011252741475.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011252741475.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Goswami", 
        "givenName": "Mayank", 
        "id": "sg:person.01357776101.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01357776101.38"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Saarland University, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.11749.3a", 
          "name": [
            "Department of Computer Science, Saarland University, 66123, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kozma", 
        "givenName": "L\u00e1szl\u00f3", 
        "id": "sg:person.010247136227.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010247136227.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "KTH Royal Institute of Technology, 11428, Stockholm, Sweden", 
          "id": "http://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "KTH Royal Institute of Technology, 11428, Stockholm, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saranurak", 
        "givenName": "Thatchaphol", 
        "id": "sg:person.012421743515.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012421743515.16"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-11-12", 
    "datePublishedReg": "2015-11-12", 
    "description": "Splay trees (Sleator and Tarjan [11]) satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs) satisfy the access lemma? After each access, self-adjusting BSTs replace the search path by a tree on the same set of nodes (the after-tree). We identify two simple combinatorial properties of the search path and the after-tree that imply the access lemma. Our main result(i) implies the access lemma for all minimally self-adjusting BST algorithms for which it was known to hold: splay trees and their generalization to the class of local algorithms (Subramanian [12], Georgakopoulos and McClurkin [7]), as well as Greedy BST, introduced by Demaine et al. [5] and shown to satisfy the access lemma by Fox [6],(ii) implies that BST algorithms based on \u201cstrict\u201d depth-halving satisfy the access lemma, addressing an open question that was raised several times since 1985, and(iii) yields an extremely short proof for the O(logn loglogn) amortized access cost for the path-balance heuristic (proposed by Sleator), matching the best known bound (Balasubramanian and Raman [2]) to a lower-order factor.One of our combinatorial properties is locality. We show that any BST-algorithm that satisfies the access lemma via the sum-of-log (SOL) potential is necessarily local. The other property states that the sum of the number of leaves of the after-tree plus the number of side alternations in the search path must be at least a constant fraction of the length of the search path. We show that a weak form of this property is necessary for sequential access to be linear.", 
    "editor": [
      {
        "familyName": "Bansal", 
        "givenName": "Nikhil", 
        "type": "Person"
      }, 
      {
        "familyName": "Finocchi", 
        "givenName": "Irene", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-48350-3_26", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-48349-7", 
        "978-3-662-48350-3"
      ], 
      "name": "Algorithms - ESA 2015", 
      "type": "Book"
    }, 
    "keywords": [
      "binary search trees", 
      "search path", 
      "self-adjusting binary search trees", 
      "BST algorithm", 
      "splay trees", 
      "search tree", 
      "access cost", 
      "sequential access", 
      "local algorithm", 
      "algorithm", 
      "simple combinatorial properties", 
      "nice properties", 
      "combinatorial properties", 
      "side alternation", 
      "access", 
      "property states", 
      "path", 
      "trees", 
      "same set", 
      "heuristics", 
      "log potential", 
      "nodes", 
      "constant fraction", 
      "Demaine", 
      "open question", 
      "set", 
      "cost", 
      "lemma", 
      "proof", 
      "number", 
      "generalization", 
      "short proof", 
      "class", 
      "sum", 
      "localities", 
      "time", 
      "state", 
      "weak form", 
      "questions", 
      "form", 
      "properties", 
      "potential", 
      "al", 
      "length", 
      "factors", 
      "alternation", 
      "lower-order factors", 
      "fraction", 
      "number of leaves", 
      "leaves", 
      "foxes"
    ], 
    "name": "Self-Adjusting Binary Search Trees: What Makes Them Tick?", 
    "pagination": "300-312", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037928027"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-48350-3_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-48350-3_26", 
      "https://app.dimensions.ai/details/publication/pub.1037928027"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_336.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-48350-3_26"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48350-3_26'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48350-3_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48350-3_26'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48350-3_26'


 

This table displays all metadata directly associated to this object as RDF triples.

149 TRIPLES      22 PREDICATES      75 URIs      68 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-48350-3_26 schema:about anzsrc-for:03
2 anzsrc-for:0303
3 schema:author N592dd9eb828b4da0809bb034279eaf6b
4 schema:datePublished 2015-11-12
5 schema:datePublishedReg 2015-11-12
6 schema:description Splay trees (Sleator and Tarjan [11]) satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs) satisfy the access lemma? After each access, self-adjusting BSTs replace the search path by a tree on the same set of nodes (the after-tree). We identify two simple combinatorial properties of the search path and the after-tree that imply the access lemma. Our main result(i) implies the access lemma for all minimally self-adjusting BST algorithms for which it was known to hold: splay trees and their generalization to the class of local algorithms (Subramanian [12], Georgakopoulos and McClurkin [7]), as well as Greedy BST, introduced by Demaine et al. [5] and shown to satisfy the access lemma by Fox [6],(ii) implies that BST algorithms based on “strict” depth-halving satisfy the access lemma, addressing an open question that was raised several times since 1985, and(iii) yields an extremely short proof for the O(logn loglogn) amortized access cost for the path-balance heuristic (proposed by Sleator), matching the best known bound (Balasubramanian and Raman [2]) to a lower-order factor.One of our combinatorial properties is locality. We show that any BST-algorithm that satisfies the access lemma via the sum-of-log (SOL) potential is necessarily local. The other property states that the sum of the number of leaves of the after-tree plus the number of side alternations in the search path must be at least a constant fraction of the length of the search path. We show that a weak form of this property is necessary for sequential access to be linear.
7 schema:editor Ne7e980d793574cfabdb340220bb61248
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N8932baf0d402460aa4da8327086364b7
11 schema:keywords BST algorithm
12 Demaine
13 access
14 access cost
15 al
16 algorithm
17 alternation
18 binary search trees
19 class
20 combinatorial properties
21 constant fraction
22 cost
23 factors
24 form
25 foxes
26 fraction
27 generalization
28 heuristics
29 leaves
30 lemma
31 length
32 local algorithm
33 localities
34 log potential
35 lower-order factors
36 nice properties
37 nodes
38 number
39 number of leaves
40 open question
41 path
42 potential
43 proof
44 properties
45 property states
46 questions
47 same set
48 search path
49 search tree
50 self-adjusting binary search trees
51 sequential access
52 set
53 short proof
54 side alternation
55 simple combinatorial properties
56 splay trees
57 state
58 sum
59 time
60 trees
61 weak form
62 schema:name Self-Adjusting Binary Search Trees: What Makes Them Tick?
63 schema:pagination 300-312
64 schema:productId Nd13c6e96442947a19ce23680687b4f2f
65 Ne8d710a3d36a4f2c830ffe225f81c527
66 schema:publisher Nebffe2d40bcb435e96d85f5923bbf633
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037928027
68 https://doi.org/10.1007/978-3-662-48350-3_26
69 schema:sdDatePublished 2022-10-01T06:57
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher N7905fbe322ce4eceba470551f9354859
72 schema:url https://doi.org/10.1007/978-3-662-48350-3_26
73 sgo:license sg:explorer/license/
74 sgo:sdDataset chapters
75 rdf:type schema:Chapter
76 N34960c773fcc4014a1faaa7c5be4137e rdf:first sg:person.012421743515.16
77 rdf:rest rdf:nil
78 N592dd9eb828b4da0809bb034279eaf6b rdf:first sg:person.011252741475.62
79 rdf:rest N789641cdafe843de99bdd753e853d99b
80 N789641cdafe843de99bdd753e853d99b rdf:first sg:person.01357776101.38
81 rdf:rest Ncf57f3b01cad4f7889f2c2525b148a01
82 N7905fbe322ce4eceba470551f9354859 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 N7ed00181ebae4612937128d648aae762 rdf:first sg:person.011757371347.43
85 rdf:rest N34960c773fcc4014a1faaa7c5be4137e
86 N8932baf0d402460aa4da8327086364b7 schema:isbn 978-3-662-48349-7
87 978-3-662-48350-3
88 schema:name Algorithms - ESA 2015
89 rdf:type schema:Book
90 Nacb37fc201424cd8bafc43af2625266e schema:familyName Finocchi
91 schema:givenName Irene
92 rdf:type schema:Person
93 Ncc63b7645cbf44709344507b10ccc71f rdf:first Nacb37fc201424cd8bafc43af2625266e
94 rdf:rest rdf:nil
95 Ncf57f3b01cad4f7889f2c2525b148a01 rdf:first sg:person.010247136227.30
96 rdf:rest N7ed00181ebae4612937128d648aae762
97 Nd13c6e96442947a19ce23680687b4f2f schema:name dimensions_id
98 schema:value pub.1037928027
99 rdf:type schema:PropertyValue
100 Ne7b7c0a5aac64ab4873717f0e1205cbd schema:familyName Bansal
101 schema:givenName Nikhil
102 rdf:type schema:Person
103 Ne7e980d793574cfabdb340220bb61248 rdf:first Ne7b7c0a5aac64ab4873717f0e1205cbd
104 rdf:rest Ncc63b7645cbf44709344507b10ccc71f
105 Ne8d710a3d36a4f2c830ffe225f81c527 schema:name doi
106 schema:value 10.1007/978-3-662-48350-3_26
107 rdf:type schema:PropertyValue
108 Nebffe2d40bcb435e96d85f5923bbf633 schema:name Springer Nature
109 rdf:type schema:Organisation
110 anzsrc-for:03 schema:inDefinedTermSet anzsrc-for:
111 schema:name Chemical Sciences
112 rdf:type schema:DefinedTerm
113 anzsrc-for:0303 schema:inDefinedTermSet anzsrc-for:
114 schema:name Macromolecular and Materials Chemistry
115 rdf:type schema:DefinedTerm
116 sg:person.010247136227.30 schema:affiliation grid-institutes:grid.11749.3a
117 schema:familyName Kozma
118 schema:givenName László
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010247136227.30
120 rdf:type schema:Person
121 sg:person.011252741475.62 schema:affiliation grid-institutes:grid.419528.3
122 schema:familyName Chalermsook
123 schema:givenName Parinya
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011252741475.62
125 rdf:type schema:Person
126 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
127 schema:familyName Mehlhorn
128 schema:givenName Kurt
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
130 rdf:type schema:Person
131 sg:person.012421743515.16 schema:affiliation grid-institutes:grid.5037.1
132 schema:familyName Saranurak
133 schema:givenName Thatchaphol
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012421743515.16
135 rdf:type schema:Person
136 sg:person.01357776101.38 schema:affiliation grid-institutes:grid.419528.3
137 schema:familyName Goswami
138 schema:givenName Mayank
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01357776101.38
140 rdf:type schema:Person
141 grid-institutes:grid.11749.3a schema:alternateName Department of Computer Science, Saarland University, 66123, Saarbrücken, Germany
142 schema:name Department of Computer Science, Saarland University, 66123, Saarbrücken, Germany
143 rdf:type schema:Organization
144 grid-institutes:grid.419528.3 schema:alternateName Max-Planck Institute for Informatics, 66123, Saarbrücken, Germany
145 schema:name Max-Planck Institute for Informatics, 66123, Saarbrücken, Germany
146 rdf:type schema:Organization
147 grid-institutes:grid.5037.1 schema:alternateName KTH Royal Institute of Technology, 11428, Stockholm, Sweden
148 schema:name KTH Royal Institute of Technology, 11428, Stockholm, Sweden
149 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...