百科问答小站 logo
百科问答小站 font logo



红黑树的实现可以有多精简(各种语言随意)? 第1页

  

user avatar   luo-bi-cheng 网友的相关建议: 
      

20行实现一个完整的红黑树的话,还是太困难了。如果不考虑删除操作的话,可以参考

Purely Functional Data Structures

一书当中3.3节介绍的用Haskell实现的一个红黑树。

       module RedBlackSet( empty                   , member                   , insert                   ) where  data Tree a = Empty             | T Color (Tree a) a (Tree a)  data Color  = R             | B  empty :: Ord a => Tree a empty = Empty  member :: Ord a => Tree a -> a -> Bool member (T _ left e right) x | x == e = True                             | x < e  = member left x                             | x > e  = member right x member Empty _                       = False  insert :: Ord a => a -> Tree a -> Tree a insert x s = let T _ a y b = ins s              in  T B a y b         where           ins s'@(T color a' y' b')                     | x < y'    = build color (ins a') y' b'                     | x > y'    = build color a' y' (ins b')                     | otherwise = s'           ins Empty             = T R Empty x Empty  build :: Color -> Tree a -> a -> Tree a -> Tree a build B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d) build B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d) build B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d) build B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d) build color left x right          = T color left x right      

看了下,大概30度行。上述实现直接搬运自

The easy way to implement a Red-Black tree

。如果想要再在这个基础上增加删除操作的话,可以参阅

cs.kent.ac.uk/people/st

,大概80行左右。

欢迎关注:




  

相关话题

  如果想大体地了解凸优化和非凸优化中比较重要的概念、理论知识和算法应该看哪些书籍或者论文? 
  红黑树的实现可以有多精简(各种语言随意)? 
  戴克斯特拉算法(Dijkstra)的本质是贪心,还是动态规划? 
  在知乎你见过哪些明显抱团点反对的问题,对社区有怎样的影响,你有什么好的建议? 
  如何看待 2021 年图灵奖授予美国计算机科学家 Jack J. Dongarra? 
  带一堆指针的链式结构怎么写才好? 
  有哪些手算对数的方法? 
  美团公开外卖订单分配算法,详解算法如何判断一个骑手的时间宽裕程度和顺路程度,有哪些值得关注的信息? 
  使用数组可以表示哪些数据结构? 
  数据结构与算法中,树一般会应用在哪些方面?为什么? 

前一个讨论
你写过哪些比较酷的十行以内的 Matlab 代码?
下一个讨论
高校规定学生不删游戏就没收电脑,你怎么看?





© 2025-05-07 - tinynew.org. All Rights Reserved.
© 2025-05-07 - tinynew.org. 保留所有权利