算法导论 动态顺序统计树练习题 14.1-3 14.1-4 14.1-5
*
* Description: 算法导论 第14章 动态顺序统计树练习题解答（伪代码）
*
* Version: 1.0
* Created: 2012年11月19日 22时59分16秒
* Author: sd44
* Organization:
*
* =====================================================================================
*/
// 14.1-3 OS-SELECT的非递归
OS-SELECT(ptr x, int i) {
if (i > x->size)
return NULL;
int r;
ptr tmp = x;
while (1) {
r = tmp->left->size + 1;
if (i < r) {
tmp = tmp->left;
} else if (i > r) {
i = i - r;
tmp = tmp->right;
}
else
return r;
}
}
// 14.1-4 OS-KEY-RANK(T, k) 较为简单，稍微修改树的find(元素）操作即可，
// 题目要求为递归形式，我实现的是非递归形式。
// 解答：
//
r为动态集合中k的秩。。
r初始化为0.
如果k比当前节点的元素值大，则向右子节点移动，并记录当前节点左子结点的size且
+1。r += currentNode->left->size + 1;
如果k比当前节点的元素值小，则向左子结点移动，不对r进行加减操作。
如果k等于当前节点的元素时，r += currentNode->left->size + 1;
//14.1-5 如何在O(lg N)的时间内，确定x在树的线性序中第i个后继。
//解答：
//
首先，find找到x在顺序统计树中的节点node。
如果node右节点的size大于i，则进入右结点，node = node->right,递归找第i个后继
如果node右结点的size小于i，则i = i - node->right->size，此时分两种情况：
1, 如果node为其父的右结点，则上移，node = node->parent
2, 如果node为其父的左节点，则上移，node = node->parent，i = i - 1。如果i == 1,返回此时的node(为原来node的parent）。
否则递归找第i个后继
算法导论思考题 13-4 Treap
struct treap {
type element;
int priority ;
}
treap array[n]; //由用户构建一个带有元素与互异优先级的数组。
for (int i = 0; i < n; i++) {
treePtr = treapTreeInsert(array[i].elemnt) //执行普通的二叉树插入,保存插入后的节点
while (treePtr != treepHeader && treePtr->priority < treePtr->parent->priority) {
// treePtr不为树根，且优先级比其父节点小。
if (treePtr = treePtr->parent->left)
rightRorate(treePtr->parent);
else
leftRorate(treePtr->parent);
未经验证，有过有错，请指正评论或给我发EMAIL
算法导论 红黑树的实现代码（C++）
代码结构参照了Mark Allen Weiss的《数据结构与算法分析 C++语言描述》中的模板结构。
代码根据《算法导论》中的伪代码而来。
在gtalk群与FXY兄说起红黑树，他介绍了一个非常牛B的算法网址--结构之法：
http://blog.csdn.net/v_july_v/article/details/6543438
http://blog.csdn.net/v_JULY_v/article/details/6284050
根据以上网址的图解，验证并DEBUG了自己的代码（早期代码有错误的地方）
DeleteFixup和InsertFixup中的颜色修改，维持红黑树性质的代码不是很清晰。。。。
/*
* =====================================================================================
*
* Filename: redblacktree.h
*
* Description: 红黑树的实现：
* 红黑树确保没有一条路径会比其他路径长出两倍，接近平衡。
*
* 红黑树的5个基本性质：
* 1,每个节点为红或黑
* 2,根节点为黑
* 3,每个叶结点(nullNode)为黑
* 4,如果一个节点是红的，那他的两个儿子都是黑的
* 5,对每个节点，从该结点到其子孙节点的所有路径上包含相同数目的黑节点
*
* Version: 1.0
* Created: 2012年11月16日 17时47分03秒
* Author: sd44 (sd44sd44@yeah.net),
*
* =====================================================================================
*/
#ifndef redblacktree_INC
#define redblacktree_INC
#include <iostream>
template <typename Comparable>
class RedBlackTree
{
// 调用以下返回RedBlackNode *类型的函数时，注意要检查值是不是nullNode，再进行操作。
public:
enum TreeColor {RED, BLACK};
struct RedBlackNode {
Comparable element;
RedBlackNode *parent;
RedBlackNode *left;
RedBlackNode *right;
TreeColor color;
RedBlackNode( const Comparable & theElement = Comparable( ), RedBlackNode *par = NULL,
RedBlackNode *lt = NULL, RedBlackNode *rt = NULL,
TreeColor defaultColor = RED )
: element( theElement ), parent(par), left( lt ), right( rt ), color(defaultColor)
{ }
};
// 显示构造函数，传入一个可以< >比较的元素
explicit RedBlackTree() {
nullNode = new RedBlackNode;
// nullNode的初始化未必有必要吧？
nullNode->parent = nullNode->left = nullNode->right = nullNode;
nullNode->color = BLACK;
header = nullNode;
}
~RedBlackTree() {
makeEmpty();
delete nullNode;
}
const Comparable &findMin() {
return findMinPos(header)->element;
}
const Comparable &findMax() {
return findMaxPos(header)->element;
}
RedBlackNode *treeHeader() { return header; }
RedBlackNode *treeNullNode() { return nullNode; }
RedBlackNode *find(RedBlackNode *pos, const Comparable &element) const;
RedBlackNode *findSuccessor(RedBlackNode *pos);
bool isEmpty() const;
void printTree() const { printTree(header); }
void printTree(RedBlackNode *pos) const;
void makeEmpty();
void rbInsert(const Comparable &x);
void rbDelete(const Comparable &x);
RedBlackNode *rbDelete(RedBlackNode *node);
void leftChildDeleteFixup(RedBlackTree::RedBlackNode * &node);
void rightChildDeleteFixup(RedBlackTree::RedBlackNode * &node);
private:
RedBlackNode *findMinPos(RedBlackNode *pos) const;
RedBlackNode *findMaxPos(RedBlackNode *pos) const;
void rbInsertFixup(RedBlackNode *node);
void rbDeleteFixup(RedBlackNode *node);
void leftRotate(RedBlackNode *x);
void rightRotate(RedBlackNode *x);
void emptySubTree(RedBlackNode *pos);
RedBlackNode *header;
RedBlackNode *nullNode;
};
#endif /* ----- #ifndef redblacktree_INC ----- */
#include "redblacktree.h"
#include <cstdlib>
#include <ctime>
template <typename Comparable>
typename RedBlackTree<Comparable>::RedBlackNode *RedBlackTree<Comparable>::findMinPos(RedBlackNode *pos) const
{
if (pos == nullNode)
return pos;
while (pos->left != nullNode)
pos = pos->left;
return pos;
}
template <typename Comparable>
typename RedBlackTree<Comparable>::RedBlackNode
*RedBlackTree<Comparable>::findMaxPos(RedBlackNode *pos) const
{
if (pos == NULL)
return pos;
// 此处用的是nullNode,而非NULL,也是红黑树与普通二叉树的NULL区别.
while (pos->left != nullNode)
pos = pos->left;
return pos;
}
template <typename Comparable>
typename RedBlackTree<Comparable>::RedBlackNode
*RedBlackTree<Comparable>::find(
RedBlackTree<Comparable>::RedBlackNode *pos, const Comparable &element) const
{
if (pos == NULL)
return pos;
while (pos != nullNode && pos->element != element) {
if (pos->element < element)
pos = pos->right;
else if (pos ->element > element)
pos = pos->left;
}
return pos;
}
template <typename Comparable>
typename RedBlackTree<Comparable>::RedBlackNode
*RedBlackTree<Comparable>::findSuccessor(RedBlackTree::RedBlackNode *pos)
{
if (pos->right != nullNode)
return findMinPos(pos->right);
RedBlackNode *successor = pos->parent;
while (successor != nullNode && pos == successor->right) {
pos = successor;
successor = pos->parent;
}
return successor;
}
template <typename Comparable>
bool RedBlackTree<Comparable>::isEmpty() const
{
return treeHeader() == nullNode;
}
template <typename Comparable>
void RedBlackTree<Comparable>::printTree(RedBlackNode *pos) const
{
if (pos == NULL || pos == nullNode)
return;
if (pos->left != nullNode)
printTree(pos->left);
//WARNING: 此处cout只适用于可以打印的元素,请参照自己的数据结构实现
std::cout << pos->element;
if (pos->color == BLACK)
std::cout << ":BLACK";
else
std::cout << ":RED";
std::cout << "\t";
if (pos->right != nullNode)
printTree(pos->right);
}
template <typename Comparable>
void RedBlackTree<Comparable>::makeEmpty()
{
emptySubTree(header);
header = nullNode;
}
template <typename Comparable>
void RedBlackTree<Comparable>::emptySubTree(RedBlackNode *pos) {
if (pos == nullNode)
return;
emptySubTree(pos->left);
emptySubTree(pos->right);
delete pos;
}
template <typename Comparable>
void RedBlackTree<Comparable>::rbInsert(const Comparable &x)
{
RedBlackNode *preFindPos = nullNode;
RedBlackNode *findPos = header;
while (findPos != nullNode) {
preFindPos = findPos;
if (findPos->element > x)
findPos = findPos->left;
else
findPos = findPos->right;
}
// 新节点元素为x，默认为红色，父节点为preFindPos，其他为nullNode。
RedBlackNode *newNode = new RedBlackNode(x, preFindPos, nullNode, nullNode, RED);
newNode->element = x;
newNode->parent = preFindPos;
if (preFindPos == nullNode)
header = newNode;
else if (x < preFindPos->element)
preFindPos->left = newNode;
else
preFindPos->right = newNode;
rbInsertFixup(newNode);
}
template <typename Comparable>
void RedBlackTree<Comparable>::rbInsertFixup(RedBlackTree::RedBlackNode *node)
{
RedBlackNode *uncle;
while (node->parent->color == RED) {
//以下六种情况前提均是，父节点为红，爷结点为黑
// 如果新插入结点node，执行以下操作：
// 因为根节点为黑色，根节点的子节点不执行此条语句，所以node的爷爷结点肯定不是nullNode。
// 访问不会越界。
if (node->parent == node->parent->parent->left) {
uncle = node->parent->parent->right;
if (uncle->color == RED) { // 第一种情况：node与其父结点，叔父结点均为RED
// 此时违反性质4：红节点的两个子节点均为黑，于是：
// 将 父、叔结点改为黑，
// 爷爷结点改为红，以维持性质五：黑高度相同。
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
// node上移两层，迭代考察前爷爷结点为红是否违反性质4
node = node->parent->parent;
} else { // 叔父结点为黑色，父节点为红的情况。
if (node == node->parent->right) {
//第二种情况：node父节点为左节点，node为右结点
node = node->parent;
// 左旋，将情况改为第三种情况
leftRotate(node);
}
// 第三种情况：node父节点为左节点，node为左节点。
node->parent->color = BLACK; //uncle为黑，node为左红节点时的情况
node->parent->parent->color = RED;
rightRotate(node->parent->parent);
}
} else {
//else 语句执行 node的父节点为右节点时的情况。
uncle = node->parent->parent->left;
if (uncle->color == RED) { // 第四种情况：父节点为右结点，node与其父，叔父结点均为RED
// 此时违反性质4：红节点的两个子节点均为黑，于是：
// 将 父、叔结点改为黑，
// 爷爷结点改为红，以维持性质五：黑高度相同。
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
// node上移两层，迭代考察前爷爷结点为红是否违反性质4
node = node->parent->parent;
} else { // 父节点为红，叔结点为黑色的情况。
if (node == node->parent->left) {
// 第五种情况 父节点为右结点，node为左节点，叔结点为黑。
node = node->parent;
// 右旋，将情况改为
rightRotate(node);
}
// 第六种情况 父节点为右结点，node为右节点，叔结点为黑。
node->parent->color = BLACK; //uncle为黑，node为左红节点时的情况
node->parent->parent->color = RED;
leftRotate(node->parent->parent);
}
}
}
header->color = BLACK;
}
template <typename Comparable>
void RedBlackTree<Comparable>::rbDelete(const Comparable &x)
{
RedBlackNode *ptr = find(header, x);
if (ptr != nullNode){
RedBlackNode *delNode = rbDelete(ptr);
if (delNode != nullNode)
delete delNode;
}
}
template <typename Comparable>
typename RedBlackTree<Comparable>::RedBlackNode *
RedBlackTree<Comparable>::rbDelete(RedBlackTree::RedBlackNode *node)
{
RedBlackNode *delNode;
if (node->left == nullNode || node->right == nullNode)
delNode = node;
else
delNode = findSuccessor(node);
RedBlackNode *delNodeChild;
// 以下if...else...语句要结合上边来看
// 如果node左右子女有一个为nullNode，则下面语句找到要提升的delNodeChild。
// 如果某节点有两个子女，则其后继没有左子女。此时如果delNode = findSuccessor的话，
// delNode->left一定等于nullNode，肯定会执行delNodeChild = delNode->right。
if (delNode->left != nullNode)
delNodeChild = delNode->left;
else
delNodeChild = delNode->right;
delNodeChild->parent = delNode->parent;
if (delNode->parent == nullNode)
header = delNodeChild;
else if (delNode == delNode->parent->left)
delNode->parent->left = delNodeChild;
else
delNode->parent->right = delNodeChild;
if (delNode != node)
node->element = delNode->element;
// 如果delNode->color为红的话，则红黑性质得以保持。
// 因为此时delNode肯定不为根，根节点仍为黑
// delNode的父节点肯定为黑，被提升的delNodeChild不会与之违反性质：红节点的子节点不能有红
// 黑高度没有变化
if (delNode->color == BLACK)
rbDeleteFixup(delNodeChild);
// WARNNING:此处没有delete delNode，用户需要接收此函数返回值然后delete
// 或者在此处delete，且将函数返回类型设置为void。
return delNode;
}
template <typename Comparable>
void RedBlackTree<Comparable>::rbDeleteFixup(RedBlackTree::RedBlackNode *node)
{
// 此时node->color因为父亲黑节点的删除，将其视为具有双重颜色特性，为黑黑或者红黑，要调整
while (node != header && node->color == BLACK) {
// while循环处理node->color为黑且不为header的情况,此时node为黑黑的双重黑特性。
if (node == node->parent->left)
leftChildDeleteFixup(node);
else
rightChildDeleteFixup(node);
}
// 如果node->color为红或者为header的话，此时只需简单的将其设置为BLACK即可，见此:
node->color =BLACK;
}
template <typename Comparable>
void RedBlackTree<Comparable>::leftChildDeleteFixup(RedBlackTree::RedBlackNode * &node)
{
//node为双重黑特性。
RedBlackNode *rightNode = node->parent->right;
// case 1: rightNode为红，两个子节点为黑,将其转换为以下case
if (rightNode->color == RED) {
rightNode->color = BLACK;
node->parent->color = RED;
leftRotate(node->parent);
// node的右子节点为旋转之前rightNode的左黑孩子，继续进入下面的case以维持红黑树性质
rightNode = node->parent->right;
}
// case 2: rightNode与其两个子节点均为黑。
if (rightNode->left->color == BLACK && rightNode->right->color == BLACK) {
rightNode->color = RED;
//简单将rightNode改为黑即可维持黑高度特性，node的双重特性取消，为单色。
// 此时将node设为其父，考察其父的红黑性质。
node = node->parent;
} else {
// case 3:rightNode与其右孩子为黑，左孩子为红，将其旋转后进入case 4
if (rightNode->right->color== BLACK) {
rightNode->left->color = BLACK;
rightNode->color = RED;
rightRotate(rightNode);
rightNode = node->parent->right;
}
// case 4:rightnode为黑，其右孩子为红
//rightNode颜色为其父颜色，旋转后以维持原来的黑高度
rightNode->color = node->parent->color;
// TODO:此时意义不明。。。node->parent此时一定为红色吗？
node->parent->color= BLACK;
rightNode->right->color = BLACK;
leftRotate(node->parent);
node = header;
}
}
template <typename Comparable>
void RedBlackTree<Comparable>::rightChildDeleteFixup(RedBlackTree::RedBlackNode *&node)
{
//node为双重黑特性。
RedBlackNode *leftNode = node->parent->left;
// case 1: rightNode为红，两个子节点为黑,将其转换为以下case
if (leftNode->color == RED) {
leftNode->color = BLACK;
node->parent->color = RED;
rightRotate(node->parent);
// node的左子节点为旋转之前leftNode的右黑孩子，继续进入下面的case以维持红黑树性质
leftNode = node->parent->left;
}
// case 2: lefttNode与其两个子节点均为黑。
if (leftNode->left->color == BLACK && leftNode->right->color == BLACK) {
leftNode->color = RED;
//简单将lefttNode改为黑即可维持黑高度特性，node的双重特性取消，为单色。
// 此时将node设为其父，考察其父的红黑性质。
node = node->parent;
} else {
// case 3:leftNode与其左孩子为黑，右孩子为红，将其旋转后进入case 4
if (leftNode->left->color== BLACK) {
leftNode->right->color = BLACK;
leftNode->color = RED;
leftRotate(leftNode);
leftNode = node->parent->left;
}
// case 4:leftNode为黑，其左孩子为红
//leftNode颜色为其父颜色，旋转后以维持原来的黑高度
leftNode->color = node->parent->color;
// TODO:此时意义不明。。。node->parent此时一定为红色吗？
node->parent->color= BLACK;
leftNode->left->color = BLACK;
rightRotate(node->parent);
node = header;
}
}
// 当在结点X上做左旋时，我们假设他的右孩子不是nullNode，
// x可以为任意右孩子不是nullNode的结点。
//左旋时，所影响到的结点，只有x，x的右孩子，与x右孩子的左节点。
template <typename Comparable>
void RedBlackTree<Comparable>::leftRotate(RedBlackTree::RedBlackNode *x)
{
RedBlackNode *y = x->right;
x->right = y->left; // 旋转中，x的右结点设为y的左结点
if (y->left != nullNode)
y->left->parent = x;
y->parent= x->parent;
if (x->parent == nullNode) {
header = y;
} else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}
//左旋时，所影响到的结点，只有x，x的左孩子，与x左孩子的右节点。
template <typename Comparable>
void RedBlackTree<Comparable>::rightRotate(RedBlackTree::RedBlackNode *x)
{
RedBlackNode *y = x->left;
x->left = y->right;
if (y->right != nullNode)
y->right->parent = x;
y->parent = x->parent;
if (x->parent == nullNode)
header = y;
else if ( x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->right = x;
x->parent = y;
}
int main(int argc, char *argv[])
{
RedBlackTree<int> tmp;
srand(unsigned(time(NULL)));
for (int i = 0; i < 20; i++)
tmp.rbInsert(rand() % 10000);
tmp.printTree();
std::cout << std::endl;
std::cout << std::endl;
tmp.makeEmpty();
tmp.rbInsert(12);
tmp.rbInsert(1);
tmp.rbInsert(9);
tmp.rbInsert(2);
tmp.rbInsert(0);
tmp.rbInsert(11);
tmp.rbInsert(7);
tmp.rbInsert(19);
tmp.rbInsert(4);
tmp.rbInsert(15);
tmp.rbInsert(18);
tmp.rbInsert(5);
tmp.rbInsert(14);
tmp.rbInsert(13);
tmp.rbInsert(10);
tmp.rbInsert(16);
tmp.rbInsert(6);
tmp.rbInsert(3);
tmp.rbInsert(8);
tmp.rbInsert(17);
tmp.printTree();
std::cout << std::endl << std::endl;
tmp.rbDelete(12);
tmp.rbDelete(1);
tmp.rbDelete(9);
tmp.rbDelete(2);
tmp.rbDelete(0);
tmp.printTree();
return 0;
}
二叉树的C++模板，摘自Mark Alen Weiss，中序用栈遍历摘自microgoogle
Mark Alen Weiss:
http://users.cis.fiu.edu/~weiss/#dsaac++3
《数据结构与算法分析 C++语言描述》
提供了较好的C++样式和代码风格，用到了模板，重载和指针引用，值得学习。。
但在效率上稍差一点，另外没有parent节点。
MicroGoogle:
http://www.cnblogs.com/shuaiwhu/archive/2011/04/20/2065055.html
非递归遍历用栈版本和不用栈版本。
我这里只参照micogoogle的实现了栈版本中序递归（基本全是照抄），非递归版本暂不考虑。
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
// #include "dsexceptions.h"
#include <iostream> // For NULL
#include <vector>
using namespace std;
// BinarySearchTree class
//
// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// bool contains( x ) --> Return true if x is present
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as warranted
template <typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree( ) : root( NULL ) {
}
BinarySearchTree( const BinarySearchTree & rhs ) : root( NULL ) {
*this = rhs;
}
/**
* Destructor for the tree
*/
~BinarySearchTree( ) {
makeEmpty( );
}
/**
* Find the smallest item in the tree.
* Throw UnderflowException if empty.
*/
const Comparable & findMin( ) const {
if ( isEmpty( ) ) {
// throw UnderflowException( );
;
}
return findMin( root )->element;
}
/**
* Find the largest item in the tree.
* Throw UnderflowException if empty.
*/
const Comparable & findMax( ) const {
if ( isEmpty( ) ) {
// throw UnderflowException( );
;
}
return findMax( root )->element;
}
/**
* Returns true if x is found in the tree.
*/
bool contains( const Comparable & x ) const {
return contains( x, root );
}
/**
* Test if the tree is logically empty.
* Return true if empty, false otherwise.
*/
bool isEmpty( ) const {
return root == NULL;
}
/**
* Print the tree contents in sorted order.
*/
void printTree( ostream & out = cout ) const {
if ( isEmpty( ) ) {
out << "Empty tree" << endl;
} else {
printTree( root, out );
}
}
/**
* Make the tree logically empty.
*/
void makeEmpty( ) {
makeEmpty( root );
}
/**
* Insert x into the tree; duplicates are ignored.
*/
void insert( const Comparable & x ) {
insert( x, root );
}
/**
* Remove x from the tree. Nothing is done if x is not found.
*/
void remove( const Comparable & x ) {
remove( x, root );
}
/**
* Deep copy.
*/
const BinarySearchTree & operator=( const BinarySearchTree & rhs ) {
if ( this != &rhs ) {
makeEmpty( );
root = clone( rhs.root );
}
return *this;
}
private:
struct BinaryNode {
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
: element( theElement ), left( lt ), right( rt ) { }
};
BinaryNode *root;
/**
* Internal method to insert into a subtree.
* x is the item to insert.
* t is the node that roots the subtree.
* Set the new root of the subtree.
*/
void insert( const Comparable & x, BinaryNode * & t ) {
if ( t == NULL ) {
t = new BinaryNode( x, NULL, NULL );
} else if ( x < t->element ) {
insert( x, t->left );
} else if ( t->element < x ) {
insert( x, t->right );
} else {
// ; // Duplicate; do nothing
}
}
/**
* Internal method to remove from a subtree.
* x is the item to remove.
* t is the node that roots the subtree.
* Set the new root of the subtree.
*/
void remove( const Comparable & x, BinaryNode * & t ) {
if ( t == NULL ) {
return; // Item not found; do nothing
}
if ( x < t->element ) {
remove( x, t->left );
} else if ( t->element < x ) {
remove( x, t->right );
} else if ( t->left != NULL && t->right != NULL ) { // Two children
t->element = findMin( t->right )->element;
remove( t->element, t->right );
} else {
BinaryNode *oldNode = t;
t = ( t->left != NULL ) ? t->left : t->right;
delete oldNode;
}
}
/**
* Internal method to find the smallest item in a subtree t.
* Return node containing the smallest item.
*/
BinaryNode * findMin( BinaryNode *t ) const {
if ( t == NULL ) {
return NULL;
}
if ( t->left == NULL ) {
return t;
}
return findMin( t->left );
}
/**
* Internal method to find the largest item in a subtree t.
* Return node containing the largest item.
*/
BinaryNode * findMax( BinaryNode *t ) const {
if ( t != NULL )
while ( t->right != NULL ) {
t = t->right;
}
return t;
}
/**
* Internal method to test if an item is in a subtree.
* x is item to search for.
* t is the node that roots the subtree.
*/
bool contains( const Comparable & x, BinaryNode *t ) const {
if ( t == NULL ) {
return false;
} else if ( x < t->element ) {
return contains( x, t->left );
} else if ( t->element < x ) {
return contains( x, t->right );
} else {
return true; // Match
}
}
/****** NONRECURSIVE VERSION*************************
bool contains( const Comparable & x, BinaryNode *t ) const
{
while( t != NULL )
if( x < t->element )
t = t->left;
else if( t->element < x )
t = t->right;
else
return true; // Match
return false; // No match
}
*****************************************************/
/**
* Internal method to make subtree empty.
*/
void makeEmpty( BinaryNode * & t ) {
if ( t != NULL ) {
makeEmpty( t->left );
makeEmpty( t->right );
delete t;
}
t = NULL;
}
//
// void printTree( BinaryNode *t, ostream & out ) const {
// if ( t != NULL ) {
// printTree( t->left, out );
// out << t->element << endl;
// printTree( t->right, out );
// }
// }
void printTree( BinaryNode *t, ostream &out) const {
// 将vector当作栈来实现，push_back,pop_back,back
vector<BinaryNode *> stackList;
while (t != NULL || !stackList.empty()) {
while (t != NULL) {
stackList.push_back(t);
t = t->left;
}
t = stackList.back();
stackList.pop_back();
out << t->element << "\t";
t = t->right;
}
}
/**
* Internal method to clone subtree.
*/
BinaryNode * clone( BinaryNode *t ) const {
if ( t == NUL
return NULL;
} else {
return new BinaryNode( t->element, clone( t->left ), clone( t->right ) );
}
}
};
#endif
算法导论习题 12-2
实现比较简单。
只需在二叉树节点内加入一个bool hasdata成员，表示此节点包含有效位串。
在插入时,遍历位串每一位，如果为1,则二叉树向右，如为0,则向左，在遍历位完成时，设置当前节点hasdata值为true。
最后的中序遍历更为简单
普通中序遍历原型为 middleOrder(currentNode)
代码为
判断 NODE不为NULL;
midlleOrder(currentNode->left);
printKey(currentNode);
middleOrder(currentNode->right);
基数树只需要加个形参即可。
原型 middleOrder(currentNode, string pre = string())
代码：
判断NODE不为NULL
middleOrder(currentNode->left, pre +"0");
if (currentNode->hasData)
print(string);
middleOrder(currentNode->right, pre +"1");
调用：
middleOrder(Tree)
算法导论9.1-1 用O(N + lgn -2 )的运行时间找出第二小元素
代码有点混乱，C/C++不分，主要集中在createtree的 int &size形参上，其实最好是建个类存储当前层的SIZE，或者其他办法。因时间问题，不再更改。
#include <iostream>
/*
* === FUNCTION ======================================================================
* Name: findSecond
* Description: 算法导论练习 9.1-1
* 证明：在最坏情况下，利用n + lgn -2次比较，，即可找到n个元素中的第2个小元素
* （提示：同时找最小元素）
* 限制：需要支持随机迭代
* 思路：起先想到用分治算法，但设计不出，还是忍不住看了算法导论的答案：
*
* To find the smallest element construct a tournament as follows:
* Compare all the numbers in pairs.
* Only the smallest number of each pair is potentially the
smallest of all so the problem is reduced to size n/2 .
* Continuing in this fashion until there is only one left clearly solves the problem.
* Exactly n − 1 comparisons are needed since the tournament can be drawn as an n-leaf binary
tree
which has n − 1 internal nodes (show by induction on n).
* Each of these nodes correspond to a comparison.
* We can use this binary tree to also locate the second
* smallest number. The path from the root to the smallest element
* (of height lg n ) must contain the second smallest element. Conducting
* a tournament among these uses lg n − 1 comparisons.
* The total number of comparisons are: n − 1 + lg n − 1 = n + lg n − 2.
* =====================================================================================
*/
bool compInt(const int &a, const int &b)
{
return a < b;
}
template <typename T>
class findSecondNode {
public:
findSecondNode() : element(0), compareElement(0), child(0) { }
findSecondNode(const T *elementArg, const T *compareElementArg, const findSecondNode<T> *childArg)
: element(elementArg), compareElement(compareElementArg), child(childArg) { }
const T *element; /* 本元素指针 */
const T *compareElement; /* 与本元素比较的元素指针 */
const findSecondNode<T> *child; /* 二叉树子节点，与本元素同值 */
};
template <typename T, typename compFunc>
const findSecondNode<T> *createTree(const findSecondNode<T> *array, int &size, compFunc func);
template <typename T, typename compFunc>
const T *findSecond(T *array, int size, compFunc func);
#include <iostream>
#include <vector>
#include "find2nd.h"
// 如果失败，返回0值。
template <typename T, typename compFunc>
const findSecondNode<T> *createTree(const findSecondNode<T> *array, int &size,
compFunc func)
{
if (size <= 0) {
size = 0;
return static_cast<findSecondNode<T> *>(0);
}
if (size == 1){
size = 0;
return array;
}
bool isEvenSize;
int rowSize;
if ((size % 2) != 0) {
isEvenSize = false;
rowSize = size / 2 + 1;
} else {
isEvenSize = true;
rowSize = size / 2;
}
findSecondNode<T> *row = new findSecondNode<T>[rowSize];
int i;
for (i = 0; i < size -1; i += 2)
if (func(*(array[i].element), *(array[i + 1].element))) {
row[i / 2] = findSecondNode<T>(array[i].element, array[i + 1].element, array + i);
} else {
row[i / 2] = findSecondNode<T>(array[i + 1].element, array[i].element, array
+ i + 1);
}
if (!isEvenSize) {
row[rowSize - 1] = findSecondNode<T>(array[i].element,
static_cast<T *>(0), array +
i - 1);
}
size = rowSize;
return row;
}
template <typename T, typename compFunc>
const T *findSecond( T *array, int size, compFunc func)
{
if (size <= 1)
return 0;
if (size == 2)
return func(array[0], array[1]) ? array : array + 1;
findSecondNode<T> *row;
bool evenNumSize;
int rowSize;
if ((size % 2) != 0) {
evenNumSize = false;
rowSize = size / 2 + 1;
} else {
evenNumSize = true;
rowSize = size / 2;
}
row = new findSecondNode<T>[rowSize];
int i;
for (i = 0; i < size -1; i += 2)
if (func(array[i], array[i + 1])) {
row[i / 2] = findSecondNode<T>(array + i, array +i + 1,
static_cast<findSecondNode<T> *>(0));
} else {
row[i / 2] = findSecondNode<T>(array + i + 1, array + i,
static_cast<findSecondNode<T> *>(0));
}
if (!evenNumSize)
row[rowSize -1] = findSecondNode<T>(array + i, static_cast<T *>(0),
static_cast<findSecondNode<T> *>(0));
std::vector<const findSecondNode<T> *> destructor;
destructor.push_back(row);
const findSecondNode<T> *ptr = row;
while ((ptr = createTree(ptr, rowSize, func)) !=
static_cast<const findSecondNode<T> *>(0))
destructor.push_back(ptr);
destructor.pop_back();
ptr = destructor.at(destructor.size() - 1);
const T *maySecond = ptr->compareElement;
const T *tmp;
while (ptr->child) {
tmp = ptr->child->compareElement;
if (tmp != 0 && func(*tmp, *maySecond))
maySecond = tmp;
ptr = ptr->child;
}
for (int i = destructor.size() - 1; i >= 0; i--)
delete [] destructor.at(i);
return maySecond;
}
//最好不要比较double值，不精确，此处只是展示
bool compDouble(const double &a, const double &b)
{
return a < b;
}
int main ( int argc, char *argv[] )
{
int a[10] = {90, 234, 234, 11, 5435, 89, 2423, 122, 99, 99};
const int *tmp = findSecond(a, 10, compInt);
std::cout << *tmp << std::endl;
double b[9] = {23.33, 2342.22, 12.33, 2134.222, 5555.33, 242.2, 888,
1.333, 2342.222};
//最好不要比较double值，不精确，此处只是展示
const double *tmpDouble = findSecond(b, 9, compDouble);
std::cout << *tmpDouble << std::endl;
return 0;
} /* ---------- end of function main ---------- */
计数排序和基数排序的实现。。
本想模板编程，无奈基本没使用过，最后出来个四不像。。。。既不简单明了，又不高聚合低耦合的。。。
过几天再修改，将所有算法都尽量做成模板性质。。
#include <iostream>
int intFunc(int *number, void *)
{
return *number;
}
// intbit 获取整数的第dbit位
int intbit(int *number, void *dbit);
/*
* === FUNCTION ======================================================================
* Name: CountingSort
* Description: 计数排序计数提供了O(N)的排序算法。
* 但受限于整数的Range，是一个用空间换取时间的算法。
* rangeArr的依次相加获取数组位置是为了稳定排序，适用于各种可由正整数排序的结构。
* 限制：必须是0开始的有range的正整数（可以通过func转换为此，再进行排序)
* =====================================================================================
*/
template <typename T>
struct PosWithPointer {
int posValue;
T *pointer;
};
template <typename T>
void CountingSort(T *array, int size, int range, int(*func)(T *element, void *), void *arg = 0)
{
PosWithPointer<T> *rangeArr = new PosWithPointer<T>[range +1];
for (int i = 0; i <= range; i++) {
rangeArr[i].posValue = 0;
rangeArr[i].pointer = 0;
}
for (int i = 0; i < size; i++) {
++rangeArr[func(array + i, arg)].posValue;
rangeArr[func(array +i, arg)].pointer = array + i;
}
for (int i = 1; i <= range; i++) {
rangeArr[i].posValue += rangeArr[i - 1].posValue;
}
T *sortArray = new T[size];
for (int i = size - 1; i >= 0; --i) {
// 注意此处要 -1,因为最小的数据位置为1,而数组初始为0.
sortArray[rangeArr[func(array + i, arg)].posValue - 1] = array[i];
--rangeArr[func(array +i, arg)].posValue;
}
for (int i = 0; i < size; i++) {
array[i] = sortArray[i];
}
delete [] rangeArr;
delete [] sortArray;
}
int tenPow(int basePow)
{
int result = 1;
for (int i = 1; i <= basePow; i++)
result *= 10;
return result;
}
/*
* === FUNCTION ======================================================================
* Name: RadixSort
* Description: 借助于计数排序的RaDixSort;
* 算法复杂度：线性 O(dbit(size+ 10)), 10为每一位可能的取值
* =====================================================================================
*/
// Dgit为数字的最大位数
void RadixSort(int *array, int size, int dbit)
{
for (int i = 1; i <= dbit; i++)
CountingSort(array, size, tenPow(dbit), intbit, static_cast<void *>(&i));
}
int intbit(int *number, void *dbit)
{
if (*number < 0)
return 0;
int *bit = static_cast<int *>(dbit);
return *number / tenPow(*bit - 1) % 10;
}
int main(int argc, char **argv)
{
int a[10] = {3, 5, 3, 2, 8, 984, 223, 82, 9234, 10};
std::cout << "计数排序数组" << std::endl;
CountingSort(a, 10, 9235, intFunc, 0);
for (int i = 0; i < 10; i++) {
std::cout << a[i] << "\t";
}
std::cout << "\n使用基数排序，底层用计数排序实现" << std::endl;
int b[10] = {3, 5, 3, 2, 8, 984, 223, 82, 9234, 10};
RadixSort(b, 10, 4);
for (int i = 0; i < 10; i++) {
std::cout << b[i] << "\t";
}
return 0;
}
算法导论中关于堆的习题解决。6.5-8 k路链表排序 6-3Young氏矩阵
最大/最小优先级的结构代码不再赘述，需要考虑C/C++编程中0为初始，从而在代码上修改即可。
如有需要，我会给出我的。。。
问题：6.5-8
给出一个时间为O(nlgk)，用来将k个已排序链表合并为一个排序链表的算法。n为所有输入链表中元素的总数。（提示：用一个最小堆来做k路合并）
答案：
所有比较以多路链表首元素为基数，并以此来建立最小优先级队列。
总是弹出根节点链表的首元素。每次弹出后，如果根节点已经0元素，就extract-min()，否则minHeapify()下移根节点（有可能仍是最小元素，不必小移）。
问题： 6-5
Young氏矩阵：
答案：
（1）Extract-Min()
将第一个元素保存，最后返回。
Y[m,n]（最大的）与第一个元素交换，并比较最大元素的行/列两个临近元素，取小的值与最大值交换。注意边界，递归。
(2)排序：
将每个元素放入y[m,n]，然后运行Extract-Min
n^2个元素需要2n^3的运行时间。
(3)查找：
总是与最右上角比较，如果等于，则返回。
如果大于，去除这一行
如果小于，去除这一列。。
单链表，双向链表，栈ADT
/*
* =====================================================================================
* Filename: list.h
* Description: 链表ADT
*
* Version: 1.0
* Created: 2011年03月19日 20时29分27秒
* Author: hohosd44 (), sd44sd44@yeah.net
* Company:
* =====================================================================================
*/
typedef int elem_t;
#ifndef _LIST_H_
#define _LIST_H_
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct node {
elem_t element;
struct node *next;
} Node;
typedef Node *List;
typedef Node *Position;
List initialization(void);
bool isempty(List);
bool islast(Position, List);
Position find(elem_t, List);
Position findprev(elem_t, List);
void deletes(elem_t, List);
void insert(elem_t, List, Position);
void deletelist(List);
bool additem(elem_t, List);
#endif
List initialization(void)
{
Position l;
l = (List) malloc(sizeof(Node));
if (l == NULL)
fprintf(stderr, "%s\n", "Out of memory!");
l->next = NULL;
return l;
}
bool isempty(List l)
{
return l->next == NULL;
}
bool islast(Position y, List l)
{
return y->next == NULL;
}
Position find(elem_t x, List l)
{
Position tmp;
tmp = l->next;
while (tmp != NULL && tmp->element != x)
tmp = tmp->next;
return tmp;
}
Position findprev(elem_t x, List l)
{
Position tmp;
tmp = l;
while (tmp->next != NULL && tmp->next->element != x)
tmp = tmp->next;
return tmp;
}
void deletes(elem_t x, List l)
{
Position prevpos, tmp;
prevpos = findprev(x, l);
if (!islast(prevpos, l)) {
tmp = prevpos->next;
prevpos->next = tmp->next;
free(tmp);
}
}
void insert(elem_t x, List l, Position y)
{
Position tmppos;
tmppos = (Position) malloc(sizeof(Node));
if (tmppos == NULL)
fprintf(stderr, "%s\n", "out of space!!!");
tmppos->element = x;
tmppos->next = y->next;
y->next = tmppos;
}
void deletelist(List l)
{
Position tmppos, tmp2pos;
tmppos = l->next;
while (tmppos != NULL) {
tmp2pos = tmppos->next;
free(tmppos);
tmppos = tmp2pos;
}
free(l);
}
bool additem(elem_t x, List l)
{
Position tmppos = l->next;
Position newpos;
newpos = (Position) malloc(sizeof(Node));
if (newpos == NULL) {
fprintf(stderr, "%s\n", "Out of space!!!");
return false;
}
newpos->element = x;
newpos->next = NULL;
if (tmppos == NULL)
l->next = newpos;
else {
while (tmppos->next != NULL) {
tmppos = tmppos->next;
}
tmppos->next = newpos;
}
return true;
}
// 双链表ADT
typedef int elem_t;
#ifndef _LIST_H_
#define _LIST_H_
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
elem_t element;
struct node *prev;
struct node *next;
} Node;
typedef Node *List;
typedef Node *Position;
List initialization(void);
bool isempty(List);
bool islast(Position, List);
Position find(int , List);
Position findprev(int, List);
void deletes(elem_t, List);
void insert(elem_t, List, Position);
void deletelist(List);
bool additem(elem_t, List);
#endif
List initialization(void)
{
Position l;
l = (List) malloc(sizeof(Node));
if (l == NULL)
fprintf(stderr, "%s\n", "Out of memory!");
l->prev = NULL;
l->next = NULL;
return l;
}
bool isempty(List l)
{
return l->next == NULL;
}
bool islast(Position y, List l)
{
return y->next == NULL;
}
Position find(elem_t x, List l)
{
Position tmp;
tmp = l->next;
while (tmp != NULL && tmp->element != x)
tmp = tmp->next;
return tmp;
}
Position findprev(elem_t x, List l)
{
Position tmp;
tmp = l;
while (tmp->next != NULL && tmp->next->element != x)
tmp = tmp->next;
return tmp;
}
void deletes(elem_t x, List l)
{
Position prevpos, tmp;
prevpos = findprev(x, l);
if (!islast(prevpos, l)) {
tmp = prevpos->next;
prevpos->next = tmp->next;
tmp->next->prev = prevpos;
free(tmp);
}
}
void insert(elem_t x, List l, Position y)
{
Position tmppos;
tmppos = (Position) malloc(sizeof(Node));
if (tmppos == NULL)
fprintf(stderr, "%s\n", "out of space!!!");
tmppos->element = x;
tmppos->prev = y;
tmppos->next = y->next;
y->next->prev = tmppos;
y->next = tmppos;
}
void deletelist(List l)
{
Position tmppos, tmp2pos;
tmppos = l->next;
while (tmppos != NULL) {
tmp2pos = tmppos->next;
free(tmppos);
tmppos = tmp2pos;
}
free(l);
}
bool additem(elem_t x, List l)
{
Position tmppos = l->next;
Position newpos;
newpos = (Position) malloc(sizeof(Node));
if (newpos == NULL) {
fprintf(stderr, "%s\n", "Out of space!!!");
return false;
}
newpos->element = x;
newpos->next = NULL;
if (tmppos == NULL) {
l->next = newpos;
newpos->prev = l;
} else {
while (tmppos->next != NULL) {
tmppos = tmppos->next;
}
tmppos->next = newpos;
newpos->prev = tmppos;
}
return true;
}
/*
* =====================================================================================
* Filename: stack.c
* Description: 栈链表ADT
*
* Version: 1.0
* Created: 2011年03月20日 14时17分49秒
* Author: hohosd44 (), sd44sd44@yeah.net
* Company:
* =====================================================================================
*/
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#ifndef _stack_h__INC
#define _stack_h__INC
typedef int elementtype;
struct node;
typedef struct node Node;
typedef Node *Stack;
typedef Node *Position;
bool isempty(Stack s);
Stack creatstack(void);
void freestack(Stack s);
void makeempty(Stack s);
void push(elementtype x, Stack s);
elementtype pop(Stack s);
#endif /* ----- #ifndef _stack_h__INC ----- */
struct node {
elementtype x;
Position next;
};
bool isempty(Stack s)
{
return s->next == NULL;
}
Stack creatstack(void)
{
Stack s;
s = (Position) malloc(sizeof(Node));
if (s == NULL) {
fprintf(stderr, "Out of space!!!");
exit(1);
}
s->next = NULL;
makeempty(s);
return s;
}
void freestack(Stack s)
{
makeempty(s);
free(s);
}
void makeempty(Stack s)
{
if (s == NULL) {
fprintf(stderr, "Out of space!!!");
exit(1);
}
while (!isempty(s))
pop(s);
}
void push(elementtype x, Stack s)
{
Position tmp;
tmp = (Position) malloc(sizeof(Node));
tmp->x = x;
tmp->next = s->next;
s->next = tmp;
}
elementtype pop(Stack s)
{
Position tmp1;
elementtype tmpdata;
if (!isempty(s)) {
tmpdata = s->next->x;
tmp1 = s->next;
s->next = s->next->next;
free(tmp1);
return tmpdata;
} else {
fprintf(stderr, "Empty Stack!!");
exit(1);
}
}
一些小题
#include <stdio.h>
int majority(int [], int, int); /* 确认候选值是不是主要元素 */
int primarykey(int arr[], int n) /* 找出候选值 */
{
int gal = 1;
int key = arr[0];
int i;
for (i = 1; i < n; i++) {
if (key == arr[i]) {
gal++;
}
else
gal--;
if (gal == 0) {
gal = 1;
key = arr[i];
}
}
return majority(arr, n, key);
}
int majority(int a[], int n, int key)
{
int i;
int sumkey = 0;
for (i = 0; i < n; i++)
if (a[i] == key)
sumkey++;
if (sumkey > n / 2)
return key;
else
return 0;
}
int main(void)
{
int a[] = {3, 3, 4, 3, 3, 4, 2, 4, 3};
printf("%d\n", primarykey(a, 8));
printf("%d\n", primarykey(a, 9));
return 0;
}
啊啊