Search Trees Study Guide - Revision history

Admin: /* OOP Principles */

2017-07-11T11:22:43Z

OOP Principles

← Older revision		Revision as of 11:22, 11 July 2017
Line 439:		Line 439:

	=OOP Principles=		=OOP Principles=

			Search trees are rife with applications of object-oriented programming. These are a great place to focus for object-oriented examples.

			More delegation of roles:
			* Who performs comparisons?
			* Who gets left child and how?
			* Who gets ancestors?
			* Know, before you start, how these questions will be resolved.
			* The answer to these questions will rapidly propagate throughout your solution

			Separation of position and node:
			* Position object points to tree and points to node
			* Node holds data, position does not
			* Tree has a validate method to turn positions into nodes
			* Why use this mode?
			** allows for validation - is this position actually in our tree?
			** protects data/node while also allowing users a way to point to locations and have O(1) accesss
			* Why not?
			** confusing, abstract, a bit wishy-washy
			** Extra level of cognitive burden - how to convert position to node? do I return a node? what if protected? position? value?

			Multiple inheritance:
			* inherit from abstract map or abstract data type interfaces to implement a tree map
			* inherit from linked binary tree to implement a tree map as a tree directly
			* This is why it is important, even early on, to decide your abstraction and inheritance diagram

			Hooks:
			* pseudo-virtual methods useful for different purposes

			Inheritance diagram:
			* AVL, Splay, RedBlack trees inherit from TreeMap
			* TreeMap inherits from Abstract Map and Linked Bin Map

			Tree Node factory:
			* Subtlety in design of LinkedBinTree and TreeMap classes:
			* Node class is defined in parent class
			* However, a balanced search tree requires storing additional info (AVL - height, redblack - color)
			* The classes all use the BASE Node class in the parent implementation
			* This is not linked to the specific parent class's implementation of the node - rather, we utilize polymorphism and maintain parent type pointer (ore general) so that it can still refer to the child type (Node carrying more information)
			* Polymorphism in action

	=Flags=		=Flags=

Admin: /* Splay Trees */

2017-07-11T11:14:38Z

Splay Trees

← Older revision		Revision as of 11:14, 11 July 2017
Line 427:		Line 427:
	\|-		\|-
	\|		\|
	\|~~<br /><br />~~		\|Splay Tree
	Splay Tree

	\|-		\|-
	\|height		\|height

Admin: /* Splay Trees */

2017-07-11T11:14:23Z

Splay Trees

← Older revision		Revision as of 11:14, 11 July 2017
Line 423:		Line 423:
	==Splay Trees==		==Splay Trees==

	{\| class="wikitable" cellpadding="100" width="66%"		{\| class="wikitable" cellpadding="100" width="33%"
	!colspan="4"\|Big-O Complexity of Lists		!colspan="4"\|Big-O Complexity of Lists
	\|-		\|-

Admin: /* Complexity and Cost */

2017-07-11T11:14:14Z

Complexity and Cost

← Older revision		Revision as of 11:14, 11 July 2017
Line 355:		Line 355:

	=Complexity and Cost=		=Complexity and Cost=

			==Big O Complexity Table==

			{\| class="wikitable" cellpadding="100" width="66%"
			!colspan="4"\|Big-O Complexity of Lists
			\|-
			\|
			\|<br /><br />
			General/Unbalanced
			Binary Search Tree
			\|<br /><br />
			Balanced
			Binary Search Tree
			\|<br /><br />
			AVL Tree

			\|-
			\|search
			\|O(h)
			\|O(log N)
			\|O(log N)

			\|-
			\|insert
			\|O(h)
			\|O(log N)
			\|O(log N)

			\|-
			\|remove
			\|O(h)
			\|O(log N)
			\|O(log N)

			\|-
			\|find range
			\|O(h + S)
			\|O(log N + S)
			\|O(log N + S)

			\|-
			\|rotation
			\| -
			\|O(1)
			\|O(1)

			\|-
			\|restructure
			\| -
			\|O(1)
			\|O(1)

			\|-
			\|find lt/gt
			\| -
			\|O(log N)
			\|O(log N)

			\|-
			\|iterate
			\|O(N)
			\|O(N)
			\|O(N)

			\|}

			==Splay Trees==

			{\| class="wikitable" cellpadding="100" width="66%"
			!colspan="4"\|Big-O Complexity of Lists
			\|-
			\|
			\|<br /><br />
			Splay Tree

			\|-
			\|height
			\|O(d) (zigs and zags)

			O(h) ~ O(N) (worst case)

			O(log N) amortized

			\|}

	=OOP Principles=		=OOP Principles=

Admin at 10:30, 11 July 2017

2017-07-11T10:30:22Z

← Older revision		Revision as of 10:30, 11 July 2017
Line 49:		Line 49:
	'''red-black tree''' - search tree in which nodes are colored red or black to maintain balance		'''red-black tree''' - search tree in which nodes are colored red or black to maintain balance

	=ADTs ~~and Interfaces~~=
			=ADTs, Implementations=

	==Binary Search Tree==		==Binary Search Tree==
Line 108:		Line 109:
	* fix deficit		* fix deficit

	=~~Implementations~~=		=Algorithms for Operations=

	==Binary Search Tree==		==Binary Search Tree==
Line 352:		Line 353:
	* if underflow(w):		* if underflow(w):
	** fusion or transfer(u)		** fusion or transfer(u)

	~~=Algorithms for Operations=~~

	=Complexity and Cost=		=Complexity and Cost=

Admin: /* Splay Tree */

2017-07-11T08:19:50Z

Splay Tree

@@ Line 315: / Line 315: @@
 *** rotate(p)
 *** rotate(p)
 =Algorithms for Operations=

Admin: /* Implementations */

2017-07-11T08:16:13Z

Implementations

Show changes

Admin: /* ADTs and Interfaces */

2017-07-11T07:54:02Z

ADTs and Interfaces

← Older revision		Revision as of 07:54, 11 July 2017
Line 50:		Line 50:

	=ADTs and Interfaces=		=ADTs and Interfaces=

			==Binary Search Tree==

			Binary search tree interface:
			* get
			* set
			* insert
			* remove
			* node navigation methods:
			** first
			** last
			** before
			** after
			** parent
			** left/right

			TreeMap:
			* see map implementation
			* inherits from map base class and binary tree class directly (multiple inheritance)

			Balanced Search Tree:
			* rotate(p) - rotate p and its parent
			* restructure(p) - trinode restructuring

			AVL Tree:
			* Node:
			** int height
			** extends other node classes
			* recompute height
			* is balanced
			* tall child
			* tall grandchild
			* rebalance

			Splay Tree:
			* splay
			* extends TreeMap type
			* utilizes rotation method

			(2,4) Tree
			* standard map/tree implementation
			* Node:
			** Multiple entries per node
			** Use a hash table to keep track of nodes
			** Use a sorted array, b/c O(1) size means its cheap and you go with what is simple

			Red Black Trees:
			* Node:
			** boolean red black
			** get/set red
			** get/set black
			* is leaf
			* get red child
			* rebalance inset
			* resolve red
			* rebalance delete
			* fix deficit

	=Implementations=		=Implementations=

Admin: /* Definitions */

2017-07-11T07:42:15Z

Definitions

@@ Line 30: / Line 30: @@
 | \mbox{left tree height} - \mbox{right tree height} | \leq 1
 </math>
 =ADTs and Interfaces=

Admin: /* Definitions and Variations */

2017-07-11T07:35:47Z

Definitions and Variations

← Older revision		Revision as of 07:35, 11 July 2017
Line 1:		Line 1:
	=Definitions and Variations=		=Definitions and Variations=

			==Definitions==

			'''binary search trees''' - binary tree data structure, guarantes keys in left subtree < k, keys in right subtree > k

			'''in order traversal''' - visiting each node of a BST in sorted order
			* traverse left subtree, visit action, traverse right subtree.
			* sorted iteration of keys can be made in O(n) time.

			'''binary search''' - search algorithm in which successive halves of the array of data are chosen; utilizes comparison and equals info

			'''rebalancing''' - as nodes are added and removed, left and right nodes can become imbalanced, affecting search speed - O(log N) becomes O(N)

			'''rotation''' - principal operation of rebalancing, rotates a child above its parent

			'''trinode restructuring''' - restructure connection from grandparent node to grandchild node to shorten path between them

			[[Image:SearchTree_Rotation.jpg\|500px]]

			[[Image:SearchTree_TrinodeRestructuring.jpg\|500px]]

			'''splay tree''' - binary tree structure in which most frequently used/accessed items are kept near the root

			'''factory method pattern''' - subclass controls behavior details, implementation handled in parent class

			'''AVL (Adelson-Velski-Landis) tree''' - self-balancing binary tree that ensures the height is O(log N) by guaranteeing the following:

			<math>
			\| \mbox{left tree height} - \mbox{right tree height} \| \leq 1
			</math>

	=ADTs and Interfaces=		=ADTs and Interfaces=