罗朝辉(飘飘白云)

关注嵌入式操作系统,移动平台,图形开发。-->加微博 ^_^

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  85 随笔 :: 0 文章 :: 169 评论 :: 0 Trackbacks

04 2011 档案

     摘要: 前面写了好些排序,红黑树,B 树算法的文章,还剩下查找这一大块没有写,查找相关的算法代码已经实现,但是却没有写查找算法日志的闲情了,只好先在这里放出代码来,以后有空有闲情再补上吧。

算法代码 Google 仓库:点击这里
  阅读全文
posted @ 2011-04-10 12:11 罗朝辉 阅读(717) | 评论 (0)  编辑

     摘要: 红黑树本质是二叉查找树的一种,它的性能高于普通的二叉查找树,即使是在最坏的情况下也能保证时间复杂度为O(lgn)。红黑树在每个结点上增加一个存储位表示结点的颜色(或红或黑,故称红黑树)。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树可以保证没有一条路径会比其他路径长出两倍,因而是接近平衡的。

红黑树的每个结点至少包含五个域:color,key,left,right 和 parent(一般我们都会在结点中存储额外的数据 data,但前面的五个域是必不可少的),如果某个结点没有子结点或者结节点,则将相应的指针设置为空值(NIL,注意不是 NULL,NIL是一个特定的空结点对象,类似于Obj-C 中 Nil对象)。我们将这些 NIL 当作叶子结点(在实际处理过程中,往往将最底层的孩子结点和根结点的父亲都指向同一个 NIL 结点,以便于处理红黑树代码中的边界条件),而将其它结点当作内结点。
  阅读全文
posted @ 2011-04-03 11:21 罗朝辉 阅读(1672) | 评论 (0)  编辑