Home

Data Structures

Binary Tree Searching: Improving Search Performance with Sentinels

Thu, 06/08/2006 - 07:29 — tekpool

A normal search across a BST (Binary Search Tree) would look like this


bool BinaryTree::Search (int data )
{
	Node *current = this->root;

	while ( current != NULL )
	{
		if (current->data < data)
		{
			current = current->left;
		}
		else if (current->data > data)
		{
			current = current->right;
		}
		else if ( current->data == data )
		{
			return true;
		}
	}

  return false;
}

Binary Tree Traversal: Breadth First aka Width First aka Level Order

Thu, 06/01/2006 - 07:07 — tekpool

Binary Tree Traversal: Breadth First aka Width First aka Level Order

This is the lesser know of the different kinds of binary tree traversals. Most beginner books and articles only cover the depth first searches. Breadth first traversals are an extremely important tool when working with Binary Trees. The idea is pretty nifty. Basically you work with a Queue, and push the root node into the Queue. Then do the following until you have visited all nodes in the tree.

Rectangle Intersection - Determine if two given rectangles intersect each other or not

Tue, 11/29/2005 - 04:09 — tekpool

Q: Rectangle Intersection: Determine if two given rectangles intersect each other or not

Definitions:

Intersect: Two Rectangles intersect each other if the share a common area.

Assumptions:

  • Both the rectangles are aligned with the x and y axes.
  • Rectangles just touching each other are considered as non-intersecting.

Shuffling - Shuffle a deck of cards - Knuth Shuffle

Sun, 11/27/2005 - 04:45 — tekpool

Q: Shuffling - Shuffle a deck of cards – Knuth Shuffle

Shuffling is a process where the order of elements in a data set is randomized to provide an element of chance. One of the most common applications of this is to shuffle a deck of cards.

Mathematically, the shuffling problem, is basically a problem of computing a random permutation of N objects, since shuffling a deck of cards is basically subjecting a deck of cards to a random permutation.

Linked List: Detect a Cycle in a linked list and Fix the cycle

Thu, 10/20/2005 - 03:29 — tekpool

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.

In the Previous posts, we discussed several ways to find cycles in a list, starting from some O (n^2) trival solutions, to the classic Flyod's Cycle Finding Algorithm (also known as the Hare and Tortoise approach, or the 2 pointer approach) and a asymptotic faster variant, to a list reversal technique (which I havent seen being used anywhere). There are a few O(n lg n) solutions which I did not mentoin here. (If there is enought interest I will post this).

Linked List: Detect a Cycle in a linked list - List Reversal

Thu, 10/06/2005 - 15:40 — tekpool

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a few soIutions prior to this. Lets look into an easy but not so commonly used solution.

Sol 5: Find Cycle through List Reversal

We've looked into some classic approaches of Linked List Cycle Finding Methods (Hare and Tortoise) in the previous posts. Lets see a more easier straightforward approach. I am a bit surprised this is not a usually used method.

Linked List: Detect a Cycle in a linked list - Two Pointers Approach (Faster)

Wed, 10/05/2005 - 15:25 — tekpool

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a couple of soIutions before. Lets look into more commonly used (classic) solutions

Sol 4: Two pointer approach (Faster)

In the last post we discussed about the regular two pointer approach and a bit about its background. Lets look into how we can make it a bit faster.

Linked List: Detect a Cycle in a linked list - Two Pointers Approach (Slow)

Mon, 10/03/2005 - 02:27 — tekpool

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a couple of soIutions before. Lets look into more commonly used (classic) solutions

Sol 3: Two pointer approach (Slow)

Linked List: Detect a Cycle in a linked list - Trival Approaches

Thu, 09/29/2005 - 05:24 — tekpool

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.

I will use the following code use in all (single) linked list programs:


struct LNode {

	int data;
	LNode* next;
	LNode() {
		next=NULL;
	}

};

class LinkedList {

	LNode* head;

}

For the sake of simplicity, I have put only an int field 'data' in the LNode struct. The LinkedList class currently only has a head pointer. I will add functions to it as we go along.

Syndicate content