查看“︁左倾红黑树”︁的源代码

{{copyedit|time=2015-03-16T02:46:53+00:00}}
{{no footnotes|time=2015-03-16T02:46:53+00:00}}
{{Infobox data structure
|name=左傾紅黑樹
|image = Left-leaning_red–black_tree.png
|type=tree
|invented_by=[[羅伯特·塞奇威克]]
|invented_year=2008年
|space_avg=<math>O(n)</math>
|space_worst=<math>O(n)</math>
|search_avg=<math>O(\log n)</math>
|search_worst=<math>O(\log n)</math>
|insert_avg=<math>O(\log n)</math>
|insert_worst=<math>O(\log n)</math>
|delete_avg=<math>O(\log n)</math>
|delete_worst=<math>O(\log n)</math>
}}
'''左傾紅黑樹'''（{{lang-en|Left-leaning red–black tree}}，縮寫：'''LLRB'''）是一種類型的[[自平衡二元搜尋樹]]。它是[[紅黑樹]]的變體，並保證對操作相同漸近的複雜性，但被設計成更容易實現。

==外部連結==

===論文===

* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.282 Robert Sedgewick. Left-leaning Red–Black Trees] {{Wayback|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.282 |date=20140204052837 }}. [http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf Direct link to PDF] {{Wayback|url=http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf |date=20201118151520 }}.
* Robert Sedgewick. Left-Leaning Red–Black Trees (slides).  Two versions:
** [http://www.cs.princeton.edu/~rs/talks/LLRB/08Dagstuhl/RedBlack.pdf Robert Sedgewick. Left-Leaning Red–Black Trees (slides), from seminar at Dagstuhl in February 2008. Outdated.] {{Wayback|url=http://www.cs.princeton.edu/~rs/talks/LLRB/08Dagstuhl/RedBlack.pdf |date=20190916102849 }}
** [http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf Robert Sedgewick. Left-Leaning Red–Black Trees (slides), from April 2008; updated] {{Wayback|url=http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf |date=20201116192505 }}
* [http://web.student.chalmers.se/groups/datx02-dtp/ Linus Ek, Ola Holmström and Stevan Andjelkovic. May 19, 2009. Formalizing Arne Andersson trees and Left-leaning Red–Black trees in Agda] {{Wayback|url=http://web.student.chalmers.se/groups/datx02-dtp/ |date=20160806040811 }}
* [https://web.archive.org/web/20160304043338/http://www.reinference.net/llrb-delete-julien-oster.pdf Julien Oster. March 22, 2011. An Agda implementation of deletion in Left-leaning Red–Black trees]
* [http://www.mew.org/~kazu/proj/red-black-tree/ Kazu Yamamoto. 2011.10.19. Purely Functional Left-Leaning Red–Black Trees] {{Wayback|url=http://www.mew.org/~kazu/proj/red-black-tree/ |date=20210115203544 }}

===實現===

{| class="wikitable sortable"

|-
! 作者
! 時間
! 語言
! 變體
! 附註
! 連結

|-
| Robert Sedgewick, rkapsi
| 2008
| [[Java]]
| 
| From [http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf this Sedgewick paper] {{Wayback|url=http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf |date=20201118151520 }}
| [https://gist.github.com/741080 Left-leaning Red–Black Tree (LLRB)]{{dead link|date=2017年12月 |bot=InternetArchiveBot |fix-attempted=yes }} -- this code has errors, see github comments

|-
| David Anson
| 2 Jun 2009
| [[C Sharp (programming language)|C#]]
| 
| 
| [http://blogs.msdn.com/b/delay/archive/2009/06/02/maintaining-balance-a-versatile-red-black-tree-implementation-for-net-via-silverlight-wpf-charting.aspx Maintaining balance: A versatile red-black tree implementation for .NET] {{Wayback|url=http://blogs.msdn.com/b/delay/archive/2009/06/02/maintaining-balance-a-versatile-red-black-tree-implementation-for-net-via-silverlight-wpf-charting.aspx |date=20120326181422 }}

|-
| kazu-yamamoto
| 2011
| [[Haskell (programming language)|Haskell]]
| 
| 
| [https://github.com/kazu-yamamoto/llrbtree llrbtree] {{Wayback|url=https://github.com/kazu-yamamoto/llrbtree |date=20201026000314 }} ([http://hackage.haskell.org/packages/archive/llrbtree/latest/doc/html/Data-Set-LLRBTree.html Data.Set.LLRBTree])

|-
| gradbot
| 2010
| [[F Sharp (programming language)|F#]]
| 
| 
| [https://github.com/gradbot/f-sharp-llrbt f-sharp-llrbt] {{Webarchive|url=https://archive.today/20121217160103/https://github.com/gradbot/f-sharp-llrbt |date=2012-12-17 }}

|-
| Lee Stanza
| 2010
| [[C语言|C]]
|
| Includes discussion
| [http://www.teachsolaisgames.com/articles/balanced_left_leaning.html Balanced Trees, Part 4: Left Leaning Red–Black Trees] {{Wayback|url=http://www.teachsolaisgames.com/articles/balanced_left_leaning.html |date=20200224215818 }}

|-
| Jason Evans
| 2010
| [[C语言|C]]
| 2-3
| 
| [https://web.archive.org/web/20120709084229/http://www.canonware.com/rb/ rb.h]

|-
| Nicola Bortignon
| December 8, 2010
| [[ActionScript_3#ActionScript_3.0|ActionScript 3]]
| 
| 
| [https://web.archive.org/web/20150402141808/http://www.nicolabortignon.com/an-as3-left-leaning-red-black-tree/ AS3 implementation and discussion]

|-
| william at 25thandClement.com
| 2011
| [[C语言|C]]
| 2-3 variant using iteration with parent pointers
|
| [http://25thandclement.com/~william/projects/llrb.h.html llrb.h: Left-leaning Red–Black Tree] {{Wayback|url=http://25thandclement.com/~william/projects/llrb.h.html |date=20120319040606 }}

|-
| Maciej Piechotka
| 2009
| [[Vala (programming language)|Vala]]
| 
| 
| [http://www.valadoc.org/#!api=gee-1.0/Gee.TreeMap Gee.TreeMap] {{Wayback|url=http://www.valadoc.org/#!api=gee-1.0/Gee.TreeMap |date=20210306122057 }}

|-
| Petar Maymounkov
| 2010
| [[Go (programming language)|Go]]
| 
| 
| [https://github.com/petar/GoLLRB GoLLRB] {{Wayback|url=https://github.com/petar/GoLLRB |date=20200917174853 }}

|-
| Sebastien Chapuis
| 2015
| [[C语言|C]]
| 
| 
| [https://github.com/sebastiencs/rbtree C - Left-leaning rbtree implementation]

|}

===其他===

* [http://www.cs.princeton.edu/~rs/talks/LLRB/movies/ Robert Segdewick. 20 Apr 2008. Animations of LLRB operations] {{Wayback|url=http://www.cs.princeton.edu/~rs/talks/LLRB/movies/ |date=20190730132855 }}
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/9_2_RedBlackTree_Simulated_.html#SECTION001222000000000000000 Open Data Structures - Section 9.2.2 - Left-Leaning Red–Black Trees] {{Wayback|url=http://opendatastructures.org/versions/edition-0.1e/ods-java/9_2_RedBlackTree_Simulated_.html#SECTION001222000000000000000 |date=20200917045705 }}
* [http://read.seas.harvard.edu/~kohler/notes/llrb.html Left-Leaning Red-Black Trees Considered Harmful] {{Wayback|url=http://read.seas.harvard.edu/~kohler/notes/llrb.html |date=20201112033417 }}

{{计算机科学中的树}}
[[Category:樹結構]]