BST renderer

[avansc]

Dandy buzzed me on irc asking about something like this, I think he did end up solving it, but it gave me something to do for a bit. Thought I'd dump the code here incase someone might be interested.

main call is the draw func,

void draw(node *n, int x, int y, int tree_height, int level, int depth, int seperation)
param break down
{
root node,
start x,
start y,
how high the tree should be,
start level, should be 0 all the time, its a messy way to do it this way,
total depth of the tree,
the least separation between leafs on the depth level.
}

ps: this code does no clean up, and is just a proof of concept. I tested it somewhat, and think it works, but there may be bugs. lemme know if you have any questions about it.

Code: Select all

#include <stdlib.h>

#include <GLUT/glut.h>
#include <math.h>

class node
{
public:
	node()
	{
		this->child[0] = NULL;
		this->child[1] = NULL;
		this->value = 0;
	}
	node(int v)
	{
		this->child[0] = NULL;
		this->child[1] = NULL;
		this->value = v;
	}
	int value;
	node *child[2];
};


node *root;


void drawline(int x1, int y1, int x2, int y2)
{
	glPushMatrix();
	glBegin(GL_LINES);
	glVertex2f(x1, y1);
	glVertex2f(x2, y2);
	glEnd();
	glPopMatrix();

}

void draw(node *n, int x, int y, int tree_height, int level, int depth, int seperation)
{
	glPushMatrix();
	glTranslatef(x, y, 0);
	glBegin(GL_LINE_LOOP);
	glVertex2f(-5, -5);
	glVertex2f(5, -5);
	glVertex2f(5, 5);
	glVertex2f(-5, 5);
	glEnd();
	glPopMatrix();
	
	if(n->child[0])
	{
		drawline(x, y, x-pow(2, depth-level)*seperation/4.0f, y-(tree_height/(float)depth));
		draw(n->child[0], x-pow(2, depth-level)*seperation/4.0f, y-(tree_height/(float)depth), tree_height, level+1, depth, seperation);
	}
	if(n->child[1])
	{
		drawline(x, y, x+pow(2, depth-level)*seperation/4.0f, y-(tree_height/(float)depth));
		draw(n->child[1], x+pow(2, depth-level)*seperation/4.0f, y-(tree_height/(float)depth), tree_height, level+1, depth, seperation);
	}
}

void display(void)
{
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    
	glPushMatrix();
	glTranslatef(350, 430, 0);
	draw(root, 0, 0, 400, 0, 4,40);
	glPopMatrix();
	
    glutSwapBuffers();
}

void reshape(int width, int height)
{
    glViewport(0, 0, width, height);
	glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0, width, 0, height);
    glMatrixMode(GL_MODELVIEW);
}

void idle(void)
{
	glutPostRedisplay();
}


int main(int argc, char** argv)
{
	root = new node(0);
	root->child[0] = new node(1);
	root->child[1] = new node(1);
	root->child[0]->child[0] = new node(2);
	root->child[0]->child[0]->child[1] = new node(2);
	root->child[0]->child[0]->child[0] = new node(2);
	root->child[0]->child[1] = new node(2);
	root->child[0]->child[1]->child[1] = new node(2);
	root->child[0]->child[1]->child[1]->child[0] = new node(2);
	root->child[0]->child[1]->child[1]->child[1] = new node(2);
	
	root->child[0]->child[1]->child[0] = new node(2);
    
	root->child[1]->child[0] = new node(2);
	root->child[1]->child[0]->child[0] = new node(2);
	root->child[1]->child[0]->child[0]->child[0] = new node(2);
	
	glutInit(&argc, argv);
    
    glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE | GLUT_DEPTH);
    glutInitWindowSize(640, 480);
    
    glutCreateWindow("GLUT Program");
    
    glutDisplayFunc(display);
    glutReshapeFunc(reshape);
    glutIdleFunc(idle);
    
    glutMainLoop();
    return EXIT_SUCCESS;
}

[dandymcgee]

Yeah, thanks for the help. This is what mine ended up looking like. The colors are random until I actually implement RedBlack style insertion/deletion.

treedraw.png (9.01 KiB) Viewed 579 times

[avansc]

cool stuff. its been a long time since data structures, but if i recall the AVL tree is a little better/easier than redblack tree in terms of insertion and deletion. both are O(log n).

[dandymcgee]

cool stuff. its been a long time since data structures, but if i recall the AVL tree is a little better/easier than redblack tree in terms of insertion and deletion. both are O(log n).

Essentially AVL does more work to obtain a better balanced tree. And you're right, their time complexities are the same.