スプレー木(Splay tree) external_link
📓 Contents
AVL木や赤黒木よりプログラムが容易で、最近アクセスした要素に素早くアクセスすることができる。
このため、キャッシュやガーベージコレクションなどに利用される。
スプレー木は、ノードを探索(1st pass)した後にその戻り(2nd pass)で探索ノードが根となるように木の回転を行うボトムアップ・スプレーと、1st passの中で木の回転を行うトップダウン・スプレーがある。
一般にはボトムアップ・スプレーで実装されることが多いが、トップダウン・スプレーでは親情報を必要としないというメリットがある。
性質
- 最近アクセスした要素への高速な再アクセスを保証する。
※スプレー木は最悪時間計算量 O(log n) を保証できない。なぜなら、小さい順にアクセスすると最後にはスキュー木となるため、つぎに最小値にアクセスすると時間計算量は O(n) となる。 しかし、同様の処理を繰り返したとしても(1つは最悪時間計算量 O(n) となるかもしれないが)ならし時間計算量は O(log n) となる。
構造
下記は、ボトムアップ・スプレーの構造である。トップダウン・スプレーでは親情報(parent)は必要ない。
5V3Pd+MmEP5rfOw+CfTzmHh328P2vbzm0N2j1iK2Wtm4Mk7s/vVFFkgWQ2I3kQAlL4cIhGT4ZuZjGAZ7hufrw69Vtl39TnNSzpCXH2b48wwh3w8j/q+uOTY1MfabimVV5KJRV3Ff/EtEpSdq90VOdr2GjNKSFdt+5YJuNmTBenVZVdGnfrMHWvY/dZstCai4X2QlrP2zyNmqqU1Q3NX/RorlSn6yH6XNnXUmG4uR7FZZTp/O3oq/zPC8opQ1V+vDnJQ1eBKX5rmvz9xtO1aRDbvmgaB54DEr92Jsol/sKAdb0f0mJ3V7b4Zvn1YFI/fbbFHffeLi5XUrti55yeeXD0VZzmlJK17e0A1vdLtjFf2bKJWwn6Lrj6Ri5KACwjWJ0DVh1ZE3eeogDwSMqzO0ZV0mhLxsn+xw4BcCCj0s4QRhkXc9TwBgAKcIwEJybimiKAbVR4pWbEWXdJOV3yjdCnz+IowdhZ1ne0b76HEwquP3+vlPoSz+EK87FT4feqVjW8pvamvvusJrvhb1aE73n0V7R/fVQgwoEfySVUvS2nNTV4/1RZFUpMxY8dhnjbfgHX9MvJEtvBMND0Ql79btT36xZKdBNRUPlA/qXDTRP3sqb/yyO2F9wxv44fbQ3ZRvSeRreI+aN/XfzqvPPlHVgbLkMx+5TEMD0AtKzbFLeoF0X6XaA6iotP+ejga2dFQ6RaOTwljIxdaQk9o/unkHUzFvPxLaJDzzxJy1S5YfXxo+moo4gsCeOPCEaCXQ0EpijVZ0i6pRFHkyepz01bhlGRN6HE5Ij2ONHqfW9NjU6u5l5MihYN/Prn/I5/h1txCpC8f/hTWCWMuojAWsY1OcEU2FM1BgkTSMLfzwVMTho744WpxNiCM1JY5wKuJAnj1xSE0w4Kl7U5EHjuyxVTu9OTJRf8JBdDZZe5/SFL84YdeFO1IVfOSkeqvjjwaPFopH72hx0mUh8VQReBr039D0UzykCLPtxXXyNbcynoq5BfbYL9W5agoUna35l+GogRZG54eiLPeFZgjP5169paPdRMqz3ar9mBq9YpGVN2Wx3PC6n5Qxuh4Gb4XdsAZvLeAtDb4J8eQFgF9JZteC3pFaOOz6Ix18XaenKWXpHSSKQBrqHIKmUuilleSBXZDdK4xDTmya3e63RiYCg5unvgf9qDxj2XiAeQMApjqeZhGDVDuGp2OdHHwPm2EHg/TQjulM3auTfjhNEKqrYVbfA6f0/UrdDc3orrpXhVVfY0jdhRlBAganlVcN2uiUNxlNeWH82F5qynhMrYvZy9D52CaA4758Q9UEhluEtgM9M4FvY2r/KBuoITLJ3jCKvNnXTcYETeHu29PfQGAmNsGEq4tLy0L76heiy4ihsRCT6S2uZgu2lIyG5mTd3p4f2EsI0KS2/OG+7tqkTmPZJ665E9pUFtnShurCZBb3Z311zRaZXLP5cKlw5z5iyWXExpuoIoAYXPe6hhj2bCIGXZ8PQo+pjh4HDzhcLwjolbo/s2NkkR41yQMToEfV2DWJuKMZe9vdDjHkPmKqjhlFDOLzMegRYR092jtggWDI3316BN6j0UMQ0N92nx7VKJtZY4f+9qXAswOIRTYRg/62+zqmrlBiTYLdeIjB2DcMULiGmLpCMYsYPLz5MabgRBfAwfZWKBh6j+4be2TT38YIIKY5Y+scZDYdbvwevBaj/Iih1wIPqjmHWGQRscDUQT7XZpQg0s0oyNqMEkD30f0tgcjmlkAA3Uf36TGyuSUQwNQJuYnqMGSxzT2BGLot7iuZmqBmdEaJYXQKpkw4h5hNryWGZjky9SvpTJ53KRX19d91YjTOF8ONo0nnhl0RnRnvsDbcUpo0lqpimgUTxgsmDaYazTcLJpyTJw2munNsFsyPmhMW674TMTZ1QihURI4VWT6TYg5z1VXdiZUXDXhcIzGetTainxJcEQwdz+hgnGrSDKaCaZbBYORk2mBa9fpgUGXSYMY2s7KSd3ZUBYT7jHLmO1vbhTYXyvJrVt4LmCpnjggmL3a/JNC4Ud3vMeAv/wE=
🌏 Map
same layer | lower layer |
---|---|