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-12-01T06:53", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_41.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 N4bcb3ed8442a4958b8403fe5ecef5210
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 N712859133e1645f19333a9be5f4fb493
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Ne0ea6a224d4b4bb5be1c12025f33b022
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 Nb65f8e13911742f692d12c746d9aca9d
65 Ne5fd87dde7be4aeb9051e8cd18c5e741
66 schema:publisher Nd6cefdc9f9ff4d55a649f9f410f4096b
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-12-01T06:53
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher N249561007a1d441eb04d67614c61d0cf
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 N249561007a1d441eb04d67614c61d0cf schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 N29db835c1db440e796cd80eb24df551b schema:familyName Finocchi
79 schema:givenName Irene
80 rdf:type schema:Person
81 N2f9e3822133743b3a7bd462bddd96c5c schema:familyName Bansal
82 schema:givenName Nikhil
83 rdf:type schema:Person
84 N3c0a9b1e02a44f6591e957ac80a7b649 rdf:first sg:person.012421743515.16
85 rdf:rest rdf:nil
86 N4bcb3ed8442a4958b8403fe5ecef5210 rdf:first sg:person.011252741475.62
87 rdf:rest Nd5dafcfc4d6c479d973403048656f861
88 N6f813e3957584bfb9c45f1fdc54ebc88 rdf:first sg:person.011757371347.43
89 rdf:rest N3c0a9b1e02a44f6591e957ac80a7b649
90 N712859133e1645f19333a9be5f4fb493 rdf:first N2f9e3822133743b3a7bd462bddd96c5c
91 rdf:rest N7d59a1cba0524c529e09868fd1ffe703
92 N783611129de3466f9eb6cd7714149659 rdf:first sg:person.010247136227.30
93 rdf:rest N6f813e3957584bfb9c45f1fdc54ebc88
94 N7d59a1cba0524c529e09868fd1ffe703 rdf:first N29db835c1db440e796cd80eb24df551b
95 rdf:rest rdf:nil
96 Nb65f8e13911742f692d12c746d9aca9d schema:name dimensions_id
97 schema:value pub.1037928027
98 rdf:type schema:PropertyValue
99 Nd5dafcfc4d6c479d973403048656f861 rdf:first sg:person.01357776101.38
100 rdf:rest N783611129de3466f9eb6cd7714149659
101 Nd6cefdc9f9ff4d55a649f9f410f4096b schema:name Springer Nature
102 rdf:type schema:Organisation
103 Ne0ea6a224d4b4bb5be1c12025f33b022 schema:isbn 978-3-662-48349-7
104 978-3-662-48350-3
105 schema:name Algorithms - ESA 2015
106 rdf:type schema:Book
107 Ne5fd87dde7be4aeb9051e8cd18c5e741 schema:name doi
108 schema:value 10.1007/978-3-662-48350-3_26
109 rdf:type schema:PropertyValue
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)


...