note description: "[ Binary search trees; left child item is less than current item, right child item is greater ]" library: "Free implementation of ELKS library" legal: "See notice at end of class." status: "See notice at end of class." names: binary_search_tree, tree representation: recursive, array access: cursor, membership contents: generic date: "$Date: 2018-11-14 15:15:17 +0000 (Wed, 14 Nov 2018) $" revision: "$Revision: 102463 $" class interface BINARY_SEARCH_TREE [G -> COMPARABLE] create make create {BINARY_SEARCH_TREE} bt_make feature -- Access parent: detachable BINARY_SEARCH_TREE [G] -- Parent of current node has (v: like item): BOOLEAN -- Does tree contain a node whose item -- is equal to v (object comparison)? tree_item (v: like item): detachable like Current -- Node whose item is equal to v (object_comparison) -- otherwise default value. require v_not_void: v /= Void feature -- Measurement min: like item -- Minimum item in tree ensure minimum_present: has (Result) max: like item -- Maximum item in tree ensure maximum_present: has (Result) feature -- Status report sorted: BOOLEAN -- Is tree sorted? sorted_and_less (i: like item): BOOLEAN -- Is tree sorted and all its elements less then i feature -- Cursor movement node_action (v: like item) -- Operation on node item, -- to be defined by descendant classes. -- Here it is defined as an empty operation. -- Redefine this procedure in descendant classes if useful -- operations are to be performed during traversals. preorder -- Apply node_action to every node's item -- in tree, using pre-order. i_infix -- Apply node_action to every node's item -- in tree, using infix order. postorder -- Apply node_action to every node's item -- in tree, using post-order. feature -- Element change put (v: like item) -- Put v at proper position in tree -- (unless v exists already). -- (Reference or object equality, -- based on object_comparison.) -- Was declared in BINARY_SEARCH_TREE as synonym of extend. require new_item_exists: v /= Void ensure item_inserted: has (v) extend (v: like item) -- Put v at proper position in tree -- (unless v exists already). -- (Reference or object equality, -- based on object_comparison.) -- Was declared in BINARY_SEARCH_TREE as synonym of put. require new_item_exists: v /= Void ensure item_inserted: has (v) feature -- Transformation sort -- Sort tree. ensure is_sorted: sorted note copyright: "Copyright (c) 1984-2018, Eiffel Software and others" license: "Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)" source: "[ Eiffel Software 5949 Hollister Ave., Goleta, CA 93117 USA Telephone 805-685-1006, Fax 805-685-6869 Website http://www.eiffel.com Customer support http://support.eiffel.com ]" end -- class BINARY_SEARCH_TREE
Generated by ISE EiffelStudio