百科问答小站 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行左右。

欢迎关注:




  

相关话题

  请教拓扑排序中的一点疑问? 
  Apriori算法是什么?适用于什么情境? 
  怎么证明每个位上的数字之和可以被3整除的数可以被3整除? 
  为什么有些算法工程师从来不谈业务,不谈解决问题,不谈价值挖掘,开口闭口就是算法模型,炼丹调参工程化? 
  为什么现在有这么多人工智能无用论? 
  Matlab中的conv函数与卷积公式是什么关系呢? 
  学数据结构有多痛苦? 
  如何评价各种关联因素分析算法,尤其是在算法效果对比方面? 
  Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异? 
  刷完算法导论和leetcode,能找到什么水平的工作? 

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





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