红黑树 B树和哈夫曼树

一 红黑树的概念在平衡二叉树中为了保持平衡需要不断地做旋转往往就会消耗过多的性能。为了防止这种情况又保持相对的平衡我们可以使用红黑树。红黑树一中利用红黑规则来保持相对平衡的二叉搜索树是一种2-3-4树即结点可以是23或4对应有234个子节点 2结点类型就是最基本的二叉树结构对应一个黑色节点3结点类型则有一个黑色父结点和一个红色子节点4结点类型有一个黑色父节点和两个红色子节点。二 红黑规则:1 节点非黑即红2 根节点黑色3 null节点空黑色4 红一定连黑不能连续红5任意节点到叶子它们路径上的黑节点数相同。红黑树在创建时先默认一个黑色节点然后依照BST插入下一个节点默认红色再插一个新节点时若父结点为红色则需要操作来平衡此时:1叔节点为黑色则旋转然后把原来的父节点变为黑色祖父节点变为红色2叔节点为红色直接变色父节点变为黑色叔节点变为黑色祖父节点变为红色三 B树B树是多叉平衡搜索树一个节点存储多个数据从而达到少量次数的读取存储就可以获得大量数据的目的。四 哈夫曼树哈夫曼树是一棵带权路径长度最小的二叉树。这里的带权路径指的是每一个子结点的权值*节点路径长的总和。哈夫曼树的构造步骤1找最小的两个权作为子节点加和得到父节点2 删除这两个子节点把父节点纳入到我们范围内。3 在我们的范围内重复第一步和第二步直到只有两个权值。4 把最后这个权值求和得到最终的根节点。由此而画出的树就是我们要求的哈夫曼树。这棵树的最短路径长为12 * 2 7 *2 9 * 2 6 * 3 1 * 4 3 * 4 90得到哈夫曼树有什么用呢为了由此对节点进行哈夫曼编码。从根到该子节点的路径就是我们这个点的哈夫曼编码通常我们采取左支记0右支记1比如上面图的12 我们可以记作 00而 7可以记作10这样得来的哈夫曼编码压缩率非常之高所以是很多压缩工具的核心技术。