Data Structures and Algorithms (DSA)

Created Issue: Sorting.Exchange with T[] missing

pelikhan — Mon, 15 Sep 2008 02:17:24 GMT

There should be an overload for arrays instead of IList<T> to avoid 3 virtual calls when swapping 2 elements. Swapping is a critical operations in algorithms and should be implemented efficiently.

Created Issue: Heap api unclear?

pelikhan — Mon, 15 Sep 2008 01:59:19 GMT

It seems that a 'RemoveMinimum' or something related is missing from the List API. Currently one has to 1) get the element at index 0, 2) remove it. it's not really easy to use.

Created Issue: Heap has useless constract on T

pelikhan — Sun, 14 Sep 2008 22:58:15 GMT

Why do you have a constrain that T is IComparable<T>? It would be more efficient to simply take a Comparison<T>, which works for any T and let the user provide the logic.

Source code checked in, #24256

gbarnett — Fri, 12 Sep 2008 18:51:47 GMT

- fixed a bug in letting go of an object in the heap deletion algorithm

Closed Feature: Graphs

gbarnett — Fri, 12 Sep 2008 17:19:55 GMT

To be further defined.

Closed Issue: BST Remove Algorithm typo

gbarnett — Fri, 12 Sep 2008 17:18:39 GMT

In order to keep consistency, make sure you don't use 'null' when meaning to use the null zero character. An example is at line 11 of the Remove algorithm for the BST.

Updated Release: 0.6 (Sep 12, 2008)

gbarnett — Fri, 12 Sep 2008 10:33:47 GMT

New features in this release:

AVL Tree
Deque
Radix sort (strings)

We have also done a significant amount of tidying up the design in places as well as adding a few minor feaures to several existing data structures.

Released: 0.6 (Sep 12, 2008)

Fri, 12 Sep 2008 10:33:47 GMT

New features in this release:

AVL Tree
Deque
Radix sort (strings)

We have also done a significant amount of tidying up the design in places as well as adding a few minor feaures to several existing data structures.

Source code checked in, #24193

gbarnett — Thu, 11 Sep 2008 19:20:52 GMT

- updated README-dsa.htm

Closed Feature: AVL balance

gbarnett — Thu, 11 Sep 2008 19:15:21 GMT

AVL balanced tree, i.e. both left and right subtree differ in depth by at most 1.
Comments: Closed in change set #24173

Commented Issue: BST Remove Algorithm typo

gbarnett — Thu, 11 Sep 2008 19:13:43 GMT

In order to keep consistency, make sure you don't use 'null' when meaning to use the null zero character. An example is at line 11 of the Remove algorithm for the BST.
Comments: ** Comment from web user: gbarnett **

Couldn't find this on first scan.

New Post: The base class is missing.

lukadt — Thu, 11 Sep 2008 12:51:00 GMT

Sorry for the inconvenience, it has been fixed...

Source code checked in, #24173

lukadt — Thu, 11 Sep 2008 12:14:37 GMT

AvlTree ======== Added some comments to facilitate some subtle step Changed some minor bits AvlTreeTest ======== Added a test that simulate both insertion and deletion All 338 tests passed AvlTree and AvlTreeNode have full coverage

Source code checked in, #24102

lukadt — Wed, 10 Sep 2008 09:26:12 GMT

AvlTreeNode =========== Added height setting in node constructor Tree height convention adopted for algorithm convenience: empty tree has a height equal to zero, a tree with one node has an height of one AvlTreeNodeTest =============== updated with new height convention AvlTree =============== Added deletion code and refactoring the old FixHeightAndBalance method into two distinct method one for updating height and one for rebalancing (Soc principle) AvlTreeNodeTest =============== Added removal tests

Source code checked in, #23859

lukadt — Sat, 06 Sep 2008 08:19:20 GMT

BinarySearchTree ================ Converted recursion insert method to an iterative one The new method is quite simple it loops until find the correct position to insert and then exit. All insertion tests passed the first time i ran them

Source code checked in, #23823

lukadt — Fri, 05 Sep 2008 16:39:45 GMT

AvlTree ============= Rename Balance method to FixHeightAndBalance because it adjust the height and if necessary do rebalancing AvlTreeTest ============= Rename insertion test method BinarySearchTree ============= Improved deletion method, now we find nodeToRemove and its parent with only one tree descendant. Now deletion method is totally recursive

Source code checked in, #23732

lukadt — Fri, 05 Sep 2008 04:47:52 GMT

AvlTree - - - - - - - - - - - - - - - - Improved and fixed AVL insertion algorithm AvlTreeTest - - - - - - - - - - - - Added avl insertion tests with a lot of number of nodes and rebalancing

Source code checked in, #23702

gbarnett — Thu, 04 Sep 2008 22:31:31 GMT

Deleted ===== - CommonTree - ICommonTreeNode

Source code checked in, #23701

gbarnett — Thu, 04 Sep 2008 22:31:11 GMT

Renamed ====== - CommonBinaryTree (formerly CommonTree) - ICommonBinaryTreeNode (formerly ICommonTreeNode)

Source code checked in, #23601

lukadt — Thu, 04 Sep 2008 07:14:13 GMT

Enforced new tree hierarchy with the addition of abstract to CommonTree class and removed Add and Remove methods from it, these will be overriden in concrete tree implementation (avl and bst) AvlTree Added the improved add method and renamed correctly the rotation method. Added also another test for the balance property