Skip to content

Latest commit

 

History

History
25 lines (16 loc) · 1.68 KB

red_black_tree.md

File metadata and controls

25 lines (16 loc) · 1.68 KB

Red Black Tree, RBTree

https://ivanzz1001.github.io/records/post/data-structure/2018/06/24/ds-red-black-tree#11-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84

https://blog.csdn.net/xiazhiyiyun/article/details/76641752

https://www.cxyxiaowu.com/7374.html

红黑树的大名早就如雷贯耳,但是从未在教科书中学到过。 一开始在考研的时候接触到平衡二叉树(更多地叫法是AVL树)。 二叉平衡树的思想比较容易理解,想要维护一个二叉搜索树,且保持树是平衡的,即左右高度差不超过1,这样的话,很自然地 想到在进行插入或者删除操作的时候,需要做一些“手脚”,把树重新调整成平衡的状态。最早是在考研的时候接触到,没有 觉得很难(因为只是在脑中理解这个概念,而不是手写这个数据结构),一些旋转操作也不难理解,(但是不知道竟然是被 很多人称作梦魇的算法题),直到现在自己开始刷题,才知道很多数据结构理解起来并不难,但是如果能在短时间内写出正确的代码 是非常考验功底的。 需要大量的练习。(果然计算机是一门动手的学科,而不是只是靠看书和记忆)

看书的过程中,可以较容易理解这个算法,因为复杂程度确实不高,但是当真正自己实现的时候,会遇到很多问题,很多的边界条件。

今天,时隔这么多年,我决定认真学习一下这两个数据结构,然后尝试着手动实现以下(可能很少会遇到手写这个算法的时候),最后 最重要的是,要熟悉知道java,c++中的hashmap,set都用到了这个结构,要能够做到熟练使用!

Code