Binary Trees - Revision history

Admin: Fix math syntax error: missing underscore in n_I (was nI) (via update-page on MediaWiki MCP Server)

2026-06-14T23:00:42Z

Fix math syntax error: missing underscore in n_I (was nI) (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 23:00, 14 June 2026
Line 38:		Line 38:

	<math>		<math>
	h \leq nI \leq 2^h - 1		h \leq n_I \leq 2^h - 1
	</math>		</math>

Admin: /* Flags */

2017-07-09T19:45:44Z

Flags

← Older revision		Revision as of 19:45, 9 July 2017
Line 292:		Line 292:

	[[Category:Binary Trees]]		[[Category:Binary Trees]]
	~~[[Category:Skiena]]~~
	[[Category:Java]]		[[Category:Java]]

Admin: /* Goodrich Chapter 8 Trees */

2017-07-09T19:45:10Z

Goodrich Chapter 8 Trees

← Older revision		Revision as of 19:45, 9 July 2017
Line 4:		Line 4:

	See [[Trees]] for more notes from this chapter.		See [[Trees]] for more notes from this chapter.

			===Properties Revisited===

			The list of properties of binary trees is stated below but is repeated here for its importance, along with some notes as to where the identities come from.

			====Properties of general binary trees====

			There are two properties that relate the number of nodes of a binary tree, n, to the height of a binary tree, h. They both say the same thing, but in different ways:

			<math>
			\log{(n+1)} - 1 \leq h \leq n - 1
			</math>

			<math>
			h+1 \leq n \leq 2^{h+1} - 1
			</math>

			These relations come from the fact that, at a given level in a binary tree, the number of nodes is <math>2^{h}</math>. Now, the maximum number of nodes that your binary tree could possibly have would be twice the number of external nodes, if you squashed down the whole tree. (Positional argument here, a bit hand-wavey, but okay.) If you were to pick pairs of nodes, and pair up the nodes one by one, you always have 1 left out. Since there are never ''quite'' twice the total number of external nodes, we have

			<math>
			2(2^h) - 1 = 2^{h+1} - 1
			</math>

			which sets a maximum limit on the number of nodes. This relies on a property for complete binary trees that relates <math>n_{E}</math> to <math>n_{I}</math>, <math>n_{E} = n_{I}+1</math>, which we shall see in a moment.

			The other set limits on the number of internal and external nodes:

			<math>
			1 \leq n_{E} \leq 2^{h}
			</math>

			and on the number of internal nodes:

			<math>
			h \leq nI \leq 2^h - 1
			</math>

			Here again, the lower limits correspond to the worst-case binary tree, which looks like a linked list.

			====Properties of complete/proper binary trees====

			For proper or complete binary trees, we have another set of properties that hold:

			<math>
			\log{(n+1)} - 1 \leq h \leq \dfrac{n-1}{2}
			</math>

			or written slightly differently,

			<math>
			2h + 1 \leq n \leq 2^{h+1} - 1
			</math>

			We also have a relation between the number of internal and external nodes, and limits on them:

			<math>
			n_E = n_I + 1
			</math>

			<math>
			h+1\leq n_E \leq 2^h
			</math>

			<math>
			h \leq n_I \leq 2^h - 1
			</math>

	===Binary Trees===		===Binary Trees===

Admin at 06:53, 8 July 2017

2017-07-08T06:53:24Z

← Older revision		Revision as of 06:53, 8 July 2017
Line 1:		Line 1:
	~~[[File:BinTreeInsert.png\|300px]]~~

	=Notes=		=Notes=

Admin at 06:53, 8 July 2017

2017-07-08T06:53:08Z

← Older revision		Revision as of 06:53, 8 July 2017
Line 1:		Line 1:
			[[File:BinTreeInsert.png\|300px]]

	=Notes=		=Notes=

Admin: /* Flags */

2017-07-04T01:47:38Z

Flags

← Older revision		Revision as of 01:47, 4 July 2017
Line 228:		Line 228:
	[[Category:Skiena]]		[[Category:Skiena]]
	[[Category:Java]]		[[Category:Java]]
	{{~~DataStructuresFlag~~}}
			{{SearchTreesFlag}}

			{{TreesFlag}}

Admin: /* Implementations of sorted binary trees */

2017-07-04T00:58:35Z

Implementations of sorted binary trees

← Older revision		Revision as of 00:58, 4 July 2017
Line 195:		Line 195:
	==Implementations of sorted binary trees==		==Implementations of sorted binary trees==

	{{Main\|~~Sorted~~ Binary Trees}}		{{Main\|Binary Search Trees}}

	The fundamental property of a binary tree is that it hierarchically divides things into two categories, allowing O(h) insert, remove, and search algorithms, while using O(N) space.		The fundamental property of a binary tree is that it hierarchically divides things into two categories, allowing O(h) insert, remove, and search algorithms, while using O(N) space.

Admin: /* Implementations of sorted binary trees */

2017-07-04T00:58:21Z

Implementations of sorted binary trees

← Older revision		Revision as of 00:58, 4 July 2017
Line 195:		Line 195:
	==Implementations of sorted binary trees==		==Implementations of sorted binary trees==

	The fundamental property of a binary tree is that it hierarchically divides things into two categories, allowing ~~log~~(N) insert, remove, and search algorithms, while using O(N) space.		{{Main\|Sorted Binary Trees}}

			The fundamental property of a binary tree is that it hierarchically divides things into two categories, allowing O(h) insert, remove, and search algorithms, while using O(N) space.

			To keep the height limited to log N, so that insertion/removal/search takes O(log N) time, we need to ensure that the left and right halves of the tree contain roughly the same number of elements. This is called balancing the binary tree.

	The basic operations of a sorted binary tree:		The basic operations of a sorted binary tree:

Admin: /* Depth/Height Operations */

2017-07-03T21:28:59Z

Depth/Height Operations

@@ Line 111: / Line 111: @@
          return 1 + max( height(c) for c in self.children(p) )
 </pre>
 ==Skiena Chapter 3 Data Structures==

Admin: /* =Depth/Height Operations */

2017-07-03T20:59:49Z

=Depth/Height Operations

← Older revision		Revision as of 20:59, 3 July 2017
Line 86:		Line 86:
	the relationship above does not hold for improper trees and nonbinary trees.		the relationship above does not hold for improper trees and nonbinary trees.

	===Depth/Height Operations==		===Depth/Height Operations===

	For a given node at a given position p in the tree, the depth of the node is defined as the number of ancestors of p, excluding p itself. The height of a position p is defined as 0 if p is a leaf, otherwise it is 1 more than the maximum heights of p's children.		For a given node at a given position p in the tree, the depth of the node is defined as the number of ancestors of p, excluding p itself. The height of a position p is defined as 0 if p is a leaf, otherwise it is 1 more than the maximum heights of p's children.