Search Trees/OOP - Revision history

Admin: /* Pseudo-Concrete Implementations */

2017-07-03T07:05:57Z

Pseudo-Concrete Implementations

← Older revision		Revision as of 07:05, 3 July 2017
Line 15:		Line 15:
	I call this a pseudo-concrete implementation because it is, in fact, a concrete implementation, but one that is missing features and is therefore less efficient than it could be.		I call this a pseudo-concrete implementation because it is, in fact, a concrete implementation, but one that is missing features and is therefore less efficient than it could be.

			Here's what it looks like in action:

			<pre>
			class TreeMap(LinkedBinaryTree,MapBase):

			...

			def __getitem__(self,k):
			"""Return value associated with key K."""
			if self.is_empty():
			raise KeyError("Key Error: "+repr(k))
			else:
			p = self._subtree_search(self.root(), k)
			self._rebalance_access(p) # hook for balanced subtree calsses
			if k!= p.key():
			raise KeyError("Key Error: " + repr(k))
			return p.value()

			def __iter__(self):
			"""Generate an iteration of all keys in the map in order."""
			p = self.first()
			while p is not None:
			yield p.key()
			p = self.after(p)

			def __reverse__(self):
			"""Generate a reverse iteration of all keys in the map in order."""
			p = self.last()
			while p is not None:
			yield p.key()
			p = self.before(p)
			</pre>

			Note the following line:

			<code>self._rebalance_access(p) # hook for balanced subtree calsses</code>

			This calls a private method to rebalance the tree. However, because this class is an unbalanced search tree, this method is an empty method that does nothing to rebalance the tree. Thus, the class is intended to be extended by search trees that provide a similar interface, but that provide their own implementation of rebalancing nodes.

	==Flags==		==Flags==

Admin at 07:01, 3 July 2017

2017-07-03T07:01:35Z

← Older revision		Revision as of 07:01, 3 July 2017
Line 1:		Line 1:
			Object oriented programming concepts as applied to search trees.

	Also see: [[Trees/OOP]]		Also see: [[Trees/OOP]]

	==Notes==		==Notes==

	~~Object~~ oriented ~~programming concepts as applied~~ to search trees:		The Goodrich book shows several really nice examples of how we can apply object oriented thinking to this type of data structure.

			===Pseudo-Concrete Implementations===

			The first was in Section 11.1, introducing binary search trees. The TreeMap class introduced in that section implemented a binary search tree, albeit with no balancing.

	The ~~Goodrich book shows several really nice examples~~ of ~~how we can apply object oriented thinking~~ to this ~~type~~ of ~~data structure~~.		The class is a concrete implementation (it inherited from LinkedBinaryTree, itself a concrete implementation of the binary tree class and the abstract tree class) but it is also a class that is intended to be extended. Like an abstract class, it implements certain methods and leaves others "blank" with the intention that the class be extended to new implementations that define those methods. However, this is done in a clever way, such that the TreeMap class stands on its own, or can be extended into new and more efficient types of tree maps.

			I call this a pseudo-concrete implementation because it is, in fact, a concrete implementation, but one that is missing features and is therefore less efficient than it could be.

	The first was in Section 11.1, introducing binary search trees. The TreeMap class introduced in that section implemented a binary search tree, albeit with no balancing. The class is a concrete implementation (it inherited from LinkedBinaryTree, itself a concrete implementation of the binary tree class and the abstract tree class) but it is also a class that is intended to be extended. Like an abstract class, it implements certain methods and leaves others "blank" with the intention that the class be extended to new implementations that define those methods. However, this is done in a clever way, such that the TreeMap class stands on its own, or can be extended into new and more efficient types of tree maps.

	==Flags==		==Flags==

Admin at 06:57, 3 July 2017

2017-07-03T06:57:50Z

← Older revision		Revision as of 06:57, 3 July 2017
Line 1:		Line 1:
			Also see: [[Trees/OOP]]

	==Notes==		==Notes==

Admin: Created page with "==Notes== Object oriented programming concepts as applied to search trees: The Goodrich book shows several really nice examples of how we can apply object oriented thinking..."

2017-07-03T06:50:25Z

Created page with "==Notes== Object oriented programming concepts as applied to search trees: The Goodrich book shows several really nice examples of how we can apply object oriented thinking..."

New page

==Notes==

Object oriented programming concepts as applied to search trees:

The Goodrich book shows several really nice examples of how we can apply object oriented thinking to this type of data structure.

The first was in Section 11.1, introducing binary search trees. The TreeMap class introduced in that section implemented a binary search tree, albeit with no balancing. The class is a concrete implementation (it inherited from LinkedBinaryTree, itself a concrete implementation of the binary tree class and the abstract tree class) but it is also a class that is intended to be extended. Like an abstract class, it implements certain methods and leaves others "blank" with the intention that the class be extended to new implementations that define those methods. However, this is done in a clever way, such that the TreeMap class stands on its own, or can be extended into new and more efficient types of tree maps.

==Flags==
{{SearchTreesFlag}}
[[Category:OOP]]
[[Category:Trees]]