Binary Trees/ArrayBinTree - Revision history

Admin: /* Advantages */

2017-06-12T12:27:27Z

Advantages

← Older revision		Revision as of 12:27, 12 June 2017
Line 20:		Line 20:

	Left child of p has index 2f(p) + 1, the right child of p has index 2 f(p) + 2, parent has index (f(p)-1)/2		Left child of p has index 2f(p) + 1, the right child of p has index 2 f(p) + 2, parent has index (f(p)-1)/2

			==Disadvantages==

	Space usage is not great - there may be a number of empty cells that do not refer to existing nodes of T. The maximum number of "empty" slots for nodes can be as high as <math>N = 2^n - 1</math>, an exponential cost.		Space usage is not great - there may be a number of empty cells that do not refer to existing nodes of T. The maximum number of "empty" slots for nodes can be as high as <math>N = 2^n - 1</math>, an exponential cost.

	For general binary trees, the exponential worst-case space requirements of array-based representations are ~~prhibitive~~.		For general binary trees, the exponential worst-case space requirements of array-based representations are prohibitive.

	Deleting an node and promoting its child takes O(n) time because it is not just the child that moves locations within the array, but all descendants o that child.		Deleting an node and promoting its child takes O(n) time because it is not just the child that moves locations within the array, but all descendants o that child.




	=Flags=		=Flags=

Admin: /* Flags */

2017-06-07T02:25:30Z

Flags

← Older revision		Revision as of 02:25, 7 June 2017
Line 31:		Line 31:

	=Flags=		=Flags=

			{{TreesFlag}}

	[[Category:Trees]]		[[Category:Trees]]

Admin: /* Flags */

2017-06-07T02:25:14Z

Flags

← Older revision		Revision as of 02:25, 7 June 2017
Line 32:		Line 32:
	=Flags=		=Flags=

	[{Category:Trees]]		[[Category:Trees]]
	[[Category:Arrays]]		[[Category:Arrays]]
	[[Category:Binary Trees]]		[[Category:Binary Trees]]
	{{DataStructuresFlag}}		{{DataStructuresFlag}}

Admin: Created page with "=Array memory structure binary tree= ==Notes== We can number the positions sequentially according to their level - called level numbering. This is a function of position as..."

2017-06-07T02:24:38Z

Created page with "=Array memory structure binary tree= ==Notes== We can number the positions sequentially according to their level - called level numbering. This is a function of position as..."

New page

=Array memory structure binary tree=

==Notes==

We can number the positions sequentially according to their level - called level numbering. This is a function of position as follows.

If p is the root of the tree, then f(p) = 0.

If p is the left child of position q, then f(p) = 2 f(q) + 1.

If p is the right child of position q, then f(p) = 2 f(q) + 2.

Level numbering is based on potential position in the tree, so tree nodes may not all be consecutive.

==Advantages==

Why an array-based representation? Position can be represented by the single integer f(p)

Position based methos like root, parent, left, and right can be implemented using simple arithmetic

Left child of p has index 2f(p) + 1, the right child of p has index 2 f(p) + 2, parent has index (f(p)-1)/2

Space usage is not great - there may be a number of empty cells that do not refer to existing nodes of T. The maximum number of "empty" slots for nodes can be as high as <math>N = 2^n - 1</math>, an exponential cost.

For general binary trees, the exponential worst-case space requirements of array-based representations are prhibitive.

Deleting an node and promoting its child takes O(n) time because it is not just the child that moves locations within the array, but all descendants o that child.

=Flags=

[{Category:Trees]]
[[Category:Arrays]]
[[Category:Binary Trees]]
{{DataStructuresFlag}}