算法之平衡树 - 红黑树（JQuery+Js+Canvas版本的，帮助大家理解）.pdf

cqs_2012
experiments to theory and person puter
[置顶] 算法之平衡树- 红黑树(JQuery+Js+Canvas版本的,帮助大家理解)
分类: C++ 树算法 2013-12-12 11:53 222人阅读评论(0) 收藏举报
红黑树

红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在
1972年由Rudolf Bayer发明的,他称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick
于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效
的:它可以在O(log n)时间内做查找,插入和删除,这里的n是树中元素的数目。
 

我写这篇文章,是因为听到大家说,红黑树不好理解,并且写代码的时候调试不太方便。对于增删查改其中的两种
操作插入和删除来说,调试的结果看起来特别不方便,因为我们看不到图,只是看到了树的某种遍历,然后根据其
顺序再在纸上将其画出来。我现在就是要用canvas将其画出来,方便大家理解红黑树的操作原理。
 
 

至于红黑树的理解,我想大家有的人已经看过July已经为大家总结过的知识了,我在总结也不过如此,我想大家还
是去看他的吧
 请看 July的教你了解红黑树
 
 
我们先看我的代码怎么用的,我自己走个例子,然后大家自己感兴趣的可以自己去拿代码尝试一下哈
步骤
1. 首先我们运行我们的C++程序,我们会看到如下图所示
1
1. 首先我们运行我们的C++程序,我们会看到如下图所示
2. 我们先解释一下,上面为什么那么多数据,这些数据干么用的,我们要用这些数据跑实验,用这些数据建立
红黑树,并插入到红黑树中
3. 这时候,你的C++ 文件,这个文件是干么的?这个文件保存了一颗红黑树的
信息,也就是现在插入41之后的红黑树,即只有根。
4. 如图所示
2
5.
6. 里面的信息如下图
7.
8. ,
9.
10. 找到 var data变量(在代码里是13行),如图所示
3
11.
12.
13. 然后把刚才的红黑树的信息复制粘贴给变量data,然后保存,如图
4
14.
15. ok,,用浏览器打开即可,看到如下所示
16.
5
17. ok,我们已经看到我们想要看的红黑树,只有一个根41,是黑节点。
18. 然后看我们的C++程序控制窗口
19.
20. 然后我们再次输入一个数据如下:
6
21.
22. 这时候插入18467,它是红色的,(注意是关闭再打开,而不是F5刷新,否则你又会错
的)。如下
23.
7
23.
24. 变量,即刚才我们已经用过的变量,然后保
存,为如下
25.
26.
8
27.
28. 这时候18467已经插入到红黑树中,虽然不太好看哈。。。。
29. 好了,我已经循环演示操作两遍了,相信大家应该会用了。自己试着玩吧。
30. 看看这个,嘿嘿
9
31.

代码
// red black : Defines the entry point for the console application.
//
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
using namespace std ;
int const size = 100 ;
// b stands "black" ; r stands "red"
char const B = 'b';
char const R = 'r';
class node
{
int key ;
char color ;
public:
10