Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

添加 rbt，B树，leafy tree，toptree #6

Closed
4 of 5 tasks
Ir1d opened this issue Jul 17, 2018 · 15 comments · Fixed by #5141
Closed
4 of 5 tasks

添加 rbt，B树，leafy tree，toptree #6

Ir1d opened this issue Jul 17, 2018 · 15 comments · Fixed by #5141
Assignees
@CoelacanthusHex
Labels
Content Request / 内容请求 New feature or request div. 1 new page help wanted / 需要帮助 Extra attention is needed
Projects
添加内容
Milestone
2019.2

Comments

@Ir1d
Copy link
Member

Ir1d commented Jul 17, 2018 •
edited by Tiphereth-A

ref: http://scaffrey.blog.uoj.ac/blog/3667#comment-8435

  • 红黑树
  • B 树
  • B+ 树
  • Leafy Tree
  • Top Tree
@Ir1d Ir1d added Content Request / 内容请求 New feature or request help wanted / 需要帮助 Extra attention is needed labels Aug 13, 2018
@Ir1d Ir1d added this to To do in 添加内容 Aug 29, 2018
Ir1d pushed a commit that referenced this issue Nov 27, 2018
@dkz051
Merge pull request #6 from 24OI/master
ffdb0ce 
Resync with upstream
@Ir1d Ir1d added this to the pre-winter2019 milestone Jan 9, 2019
@Ir1d Ir1d mentioned this issue Jan 17, 2019
Closed
20 tasks
Marcythm pushed a commit that referenced this issue Mar 6, 2019
@StudyingFather
Merge pull request #6 from 24OI/master
5e687d9 
sync 2019.3.6
@Ir1d Ir1d mentioned this issue May 24, 2019
Closed
44 tasks
@abc1763613206 abc1763613206 mentioned this issue Aug 30, 2019
Closed
61 tasks
@Enter-tainer
Copy link
Member

我或许可以写一下 llrbt （咕咕预警

AngelKitty pushed a commit that referenced this issue Jan 23, 2020
@yjl9903
Merge pull request #6 from OI-wiki/master
09e95e7 
merge
@Marcythm Marcythm added the div. 1 new page label Apr 22, 2020
Enter-tainer pushed a commit that referenced this issue May 7, 2020
@countercurrent-time
Merge pull request #6 from OI-wiki/master
343821c 
sync
@StudyingFather StudyingFather mentioned this issue Aug 24, 2020
Closed
58 tasks
sshwy pushed a commit that referenced this issue Feb 3, 2021
@H-J-Granger
Merge pull request #6 from OI-wiki/master
99bd846 
Update data
@abc1763613206 abc1763613206 mentioned this issue Feb 8, 2021
Closed
60 tasks
@StudyingFather StudyingFather mentioned this issue Jun 30, 2021
Closed
56 tasks
@ksyx ksyx mentioned this issue Jan 22, 2022
Closed
69 tasks
@CoelacanthusHex
Copy link
Member

CoelacanthusHex commented Jan 23, 2022 •
edited

我可能会写篇 b tree 和 b+ tree 上去（超级大鸽子警告

@CoelacanthusHex CoelacanthusHex mentioned this issue Mar 12, 2022
Closed
@pluveto
Copy link

pluveto commented Jul 13, 2022

怎么回事？还没有啊

@Enter-tainer
Copy link
Member

怎么回事？还没有啊

@pluveto 欢迎来开一个 PR 来添加这些内容~

@william-song-shy
Copy link
Contributor

还在鸽啊

@Persdre
Copy link
Contributor

Persdre commented Aug 1, 2022

working on it...

@Great-designer
Copy link
Contributor

Great-designer commented Aug 2, 2022 •
edited

这看来是祖坟级issue，留个名先：
B树和B+树是408考研当中的内容（另外似乎还有b-树和b*树），可以在王道考研上找到，在《算法导论》上也有相应讲解……
我好像还没见过使用这两个树的题目与代码，算是见识过于浅薄了……

@CoelacanthusHex
Copy link
Member

我好像还没见过使用这两个树的题目与代码，算是见识过于浅薄了……

这两个都是为磁盘优化的数据结构，在 OI 这种根本不会去操作磁盘的环境优势不明显

@Enter-tainer
Copy link
Member

Rust标准库里面的map就是btreemap，原因是局部性比较好（

@CoelacanthusHex
Copy link
Member

Rust标准库里面的map就是btreemap，原因是局部性比较好（

我记得也和语言设计也有关，有人用 Java 写 BTreeMap，性能并不理想

@Great-designer
Copy link
Contributor

Great-designer commented Aug 2, 2022 •
edited

我好像还没见过使用B树和B+树的题目与代码，算是见识过于浅薄了……

我见过手写avl树的，avl树代码不长。当然，avl树在OI Wiki上已经有了。
手写红黑树也见过，红黑树代码就很长了，大概12000字符左右。据说STL的map底层用的是左偏红黑树。红黑树在OI Wiki上暂时还没有……

@Great-designer Great-designer mentioned this issue Aug 2, 2022
Merged
@Persdre
Copy link
Contributor

Persdre commented Aug 4, 2022

working on b tree...

@Persdre
Copy link
Contributor

Persdre commented Sep 17, 2022

working on leafy tree...

@ACHL-02
Copy link

ACHL-02 commented May 12, 2023

expected ovo

@yuhuoji yuhuoji mentioned this issue Sep 12, 2023
Open
@Tiphereth-A Tiphereth-A mentioned this issue Sep 15, 2023
Merged
1 task
@Great-designer
Copy link
Contributor

祝贺

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@CoelacanthusHex CoelacanthusHex

Labels
Content Request / 内容请求 New feature or request div. 1 new page help wanted / 需要帮助 Extra attention is needed
Projects
No open projects
添加内容
  
To do
Milestone
2019.2
Development

Successfully merging a pull request may close this issue.

feat(ds/top-tree.md): 新增 top tree 的 satt 实现及相关图片 F7487/OI-wiki
9 participants
@Ir1d @Enter-tainer @Persdre @Marcythm @CoelacanthusHex @william-song-shy @pluveto @Great-designer @ACHL-02