Click here to Skip to main content
14,356,134 members

Welcome to the Lounge

   

For discussing anything related to a software developer's life but is not for programming questions. Got a programming question?

The Lounge is rated Safe For Work. If you're about to post something inappropriate for a shared office environment, then don't post it. No ads, no abuse, and no programming questions. Trolling, (political, climate, religious or whatever) will result in your account being removed.
 
GeneralRe: yay i published my b-tree and binary tree classes finally Pin
honey the codewitch13-Sep-19 9:29
memberhoney the codewitch13-Sep-19 9:29 
GeneralRe: yay i published my b-tree and binary tree classes finally Pin
Nand3214-Sep-19 0:41
memberNand3214-Sep-19 0:41 
GeneralRe: yay i published my b-tree and binary tree classes finally Pin
q1213q13-Sep-19 7:03
memberq1213q13-Sep-19 7:03 
GeneralRe: yay i published my b-tree and binary tree classes finally Pin
honey the codewitch13-Sep-19 8:03
memberhoney the codewitch13-Sep-19 8:03 
GeneralRe: yay i published my b-tree and binary tree classes finally Pin
q1213q13-Sep-19 8:09
memberq1213q13-Sep-19 8:09 
GeneralRe: yay i published my b-tree and binary tree classes finally Pin
honey the codewitch13-Sep-19 8:11
memberhoney the codewitch13-Sep-19 8:11 
GeneralRe: yay i published my b-tree and binary tree classes finally Pin
q1213q13-Sep-19 8:25
memberq1213q13-Sep-19 8:25 
GeneralRe: yay i published my b-tree and binary tree classes finally Pin
honey the codewitch13-Sep-19 8:49
memberhoney the codewitch13-Sep-19 8:49 
This is a splay tree. Worst case is different because it's doing tree rotations.

Yes, I could increase the stack size but that's not really the proper way to do this - that's like cleaning your carpet with a blowtorch - i mean sure, it gets rid of the filth, but...

but i am tempted. THis is the function i need to make non-recursive:

_Node _Splay(_Node root, TKey key)
{
	// TODO: if this function wasn't recursive it could deal with more items
	int c;
	// Base cases: root is null or key is present at root 
	if (null==root || 0==(c = _comparer.Compare(root.Key, key)))
		return root;

	// Key lies in left subtree 
	if (0<c)
	{
		// Key is not in tree, we are done 
		if (null==root.Left)
			return root;
		c = _comparer.Compare(root.Left.Key, key);
		// Zig-Zig (Left Left) 
		if (0<c)
		{
			// First recursively bring the key as root of left-left 
			root.Left.Left = _Splay(root.Left.Left, key);

			// Do first rotation for root, second rotation is  
			// done after else 
			root = _Ror(root);
		}
		else if (0>c) // Zig-Zag (Left Right) 
		{
			// First recursively bring the key as root of left-right 
			root.Left.Right = _Splay(root.Left.Right, key);

			// Do first rotation for root.left 
			if (null!=root.Left.Right)
				root.Left = _Rol(root.Left);
		}

		// Do second rotation for root 
		return (null==root.Left) ? root : _Ror(root);
	}
	else // Key lies in right subtree 
	{
		// Key is not in tree, we are done 
		if (null==root.Right)
			return root;
		c = _comparer.Compare(root.Right.Key, key);
		// Zag-Zig (Right Left) 
		if (0<c)
		{
			// Bring the key as root of right-left 
			root.Right.Left = _Splay(root.Right.Left, key);

			// Do first rotation for root.right 
			if (null!=root.Right.Left)
				root.Right = _Ror(root.Right);
		}
		else if (0>c)// Zag-Zag (Right Right) 
		{
			// Bring the key as root of right-right and do  
			// first rotation 
			root.Right.Right = _Splay(root.Right.Right, key);
			root = _Rol(root);
		}

		// Do second rotation for root 
		return (null==root.Right ) ? root : _Rol(root);
	}
}


=( =( =(
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.

GeneralRe: yay i published my b-tree and binary tree classes finally Pin
q1213q13-Sep-19 9:08
memberq1213q13-Sep-19 9:08 
GeneralRe: yay i published my b-tree and binary tree classes finally Pin
honey the codewitch13-Sep-19 9:16
memberhoney the codewitch13-Sep-19 9:16 
GeneralRe: yay i published my b-tree and binary tree classes finally Pin
honey the codewitch13-Sep-19 9:44
memberhoney the codewitch13-Sep-19 9:44 
GeneralWSO CCC OTD (themed) 2019-09-13 Pin
OriginalGriff12-Sep-19 22:51
protectorOriginalGriff12-Sep-19 22:51 
GeneralRe: WSO CCC OTD (themed) 2019-09-13 Pin
PeejayAdams12-Sep-19 23:07
memberPeejayAdams12-Sep-19 23:07 
GeneralRe: WSO CCC OTD (themed) 2019-09-13 - we have a winner! Pin
OriginalGriff12-Sep-19 23:15
protectorOriginalGriff12-Sep-19 23:15 
GeneralNot the WSO CCC OTD 2019-09-13 Pin
OriginalGriff12-Sep-19 22:16
protectorOriginalGriff12-Sep-19 22:16 
GeneralRe: Not the WSO CCC OTD 2019-09-13 Pin
Abbas A. Ali12-Sep-19 22:35
professionalAbbas A. Ali12-Sep-19 22:35 
GeneralRe: Not the WSO CCC OTD 2019-09-13 Pin
OriginalGriff12-Sep-19 22:42
protectorOriginalGriff12-Sep-19 22:42 
GeneralRe: Not the WSO CCC OTD 2019-09-13 Pin
Abbas A. Ali12-Sep-19 22:47
professionalAbbas A. Ali12-Sep-19 22:47 
GeneralRe: Not the WSO CCC OTD 2019-09-13 Pin
OriginalGriff12-Sep-19 22:50
protectorOriginalGriff12-Sep-19 22:50 
GeneralRe: Not the WSO CCC OTD 2019-09-13 Pin
PeejayAdams12-Sep-19 23:03
memberPeejayAdams12-Sep-19 23:03 
GeneralRe: Not the WSO CCC OTD 2019-09-13 Pin
OriginalGriff12-Sep-19 23:06
protectorOriginalGriff12-Sep-19 23:06 
GeneralRe: Not the WSO CCC OTD 2019-09-13 Pin
DRHuff13-Sep-19 4:32
memberDRHuff13-Sep-19 4:32 
GeneralSound of the Week Pin
Sander Rossel12-Sep-19 22:09
professionalSander Rossel12-Sep-19 22:09 
GeneralRe: Sound of the Week Pin
Tachyonx13-Sep-19 4:43
memberTachyonx13-Sep-19 4:43 
GeneralRe: Sound of the Week Pin
Sander Rossel14-Sep-19 3:08
professionalSander Rossel14-Sep-19 3:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.