;;; Manually constructed tests for AVL trees.

:;;;-------------------------------------------------------------------------
:;;; Insertion.

:
:;; Starting point for the following tests.
=					((((_ 110 _)
				120
					(_ 130 _))
		140
			(_ 150 _))
	200
			((_ 310 _)
		320
					((_ 330 _)
				340
					(_ 350 _))))
D

:
:;; Counter-biased parent.
;;	p - or + -> =
;;	     ( )
;;	 n  /   \
;;	h + 1   h + 1
" V+ 305k+
	V:XYLA-AVL INSERT parent = (left child): ascend tree
	V:XYLA-AVL INSERT parent + (left child)
  D V )
" V+ 155k+
	V:XYLA-AVL INSERT parent = (right child): ascend tree
	V:XYLA-AVL INSERT parent - (right child)
  D V )

:
:;; Cobiased parent, outer descendant.
;;		 p			      n
;;		  (- -)			       (=)
;;	    n	 /     \		     /	  \    p
;;	     (-)	  n	--->	h + 1	    (=)
;;	    /   \				   /   \
;;	h + 1     h				 h	 h
" V+ 105k+
	V:XYLA-AVL INSERT parent = (left child): ascend tree
	V:XYLA-AVL INSERT parent = (left child): ascend tree
	V:XYLA-AVL INSERT parent -, node - (left child)
  D V )
" V+ 355k+
	V:XYLA-AVL INSERT parent = (right child): ascend tree
	V:XYLA-AVL INSERT parent = (right child): ascend tree
	V:XYLA-AVL INSERT parent +, node + (right child)
  D V )

:
:;; Cobiased parent, inner descendant.
;;		 p
;;		  (- -)			       c
;;	    n    /     \			(=)
;;	     (+)	 h	       n   ,---'   `---,   p
;;	    /   \   c		--->	(*)		(*)
;;	  h	 (*)		       /   \	       /   \
;;		/   \		     h	     h	     h	     h
;;	      h	      h			   h - 1   h - 1
;;	    h - 1   h - 1

" V+ 125k+
	V:XYLA-AVL INSERT parent = (left child): ascend tree
	V:XYLA-AVL INSERT parent = (right child): ascend tree
	V:XYLA-AVL INSERT parent -, node +, child - (left child)
  D V )
" V+ 135k+
	V:XYLA-AVL INSERT parent = (right child): ascend tree
	V:XYLA-AVL INSERT parent = (right child): ascend tree
	V:XYLA-AVL INSERT parent -, node +, child + (left child)
  D V )
" 110k- 130k- 150k- D V+ 135k+
	V:XYLA-AVL INSERT parent = (right child): ascend tree
	V:XYLA-AVL INSERT parent -, node +, child = (left child)
  D V )

" V+ 335k+
	V:XYLA-AVL INSERT parent = (right child): ascend tree
	V:XYLA-AVL INSERT parent = (left child): ascend tree
	V:XYLA-AVL INSERT parent +, node -, child + (right child)
  D V )
" V+ 325k+
	V:XYLA-AVL INSERT parent = (left child): ascend tree
	V:XYLA-AVL INSERT parent = (left child): ascend tree
	V:XYLA-AVL INSERT parent +, node -, child - (right child)
  D V )
" 350k- 330k- 310k- D V+ 325k+
	V:XYLA-AVL INSERT parent = (left child): ascend tree
	V:XYLA-AVL INSERT parent +, node -, child = (right child)
  D V )

:
:;; Ascend tree.
;;	  p = -> -		p = -> +
;;	     ( )	or	   ( )
;;	 n  /   \		  /   \  n
;;	h + 1     h		h     h + 1

" 125k+ 135k+ D V+ 105k+
	V:XYLA-AVL INSERT parent = (left child): ascend tree
	V:XYLA-AVL INSERT parent = (left child): ascend tree
	V:XYLA-AVL INSERT parent = (left child): ascend tree
	V:XYLA-AVL INSERT parent = (left child): extend tree
  D V )
" 325k+ 335k+ D V+ 355k+
	V:XYLA-AVL INSERT parent = (right child): ascend tree
	V:XYLA-AVL INSERT parent = (right child): ascend tree
	V:XYLA-AVL INSERT parent = (right child): ascend tree
	V:XYLA-AVL INSERT parent = (right child): extend tree
  D V )

:
:;;;-------------------------------------------------------------------------
:;;; Removal.

:
:;; Starting point for the following tests.
=			(((_ 110
				(_ 120 _))
		130
				((_ 140 _)
			150 _))
	200
			((_ 310
				(_ 320 _))
		330
				((_ 340 _)
			350 _)))
D

:
:;; Cobiased parent.
;;	   p				    p
;;	    (-)				     (=)
;;	n  /   \		--->	 n  /	\
;;	 h     h - 1			h - 1	h - 1
" 120k- D V- 140k-
	V:XYLA-AVL REMOVE parent - (left child)
	V:XYLA-AVL REMOVE parent + (right child)
	V:XYLA-AVL REMOVE parent = (left child)
  D V )
" 340k- D V- 320k-
	V:XYLA-AVL REMOVE parent + (right child)
	V:XYLA-AVL REMOVE parent - (left child)
	V:XYLA-AVL REMOVE parent = (right child)
  D V )

:
:;; Balanced parent.
;;	   p				    p
;;	    (=)				     (+)
;;	n  /   \		--->	 n  /	\
;;	 h	 h			h - 1	  h
" 120k- 140k- D V- 110k-
	V:XYLA-AVL REMOVE parent = (left child)
  D V )
" 320k- 340k- D V- 350k-
	V:XYLA-AVL REMOVE parent = (right child)
  D V )

:
:;; Counter-biased parent, balanced or counter-biased sibling.
;;	     p					  s
;;	      (+ +)				   (*)
;;	     /	   \	s		    p	 /     \
;;	h - 1	     (*)	--->	     (*)	  h
;;		    /	\		    /	\
;;		  h	  h		h - 1	  h
;;		h - 1				h - 1
" 120k- 155k+ D V- 110k-
	V:XYLA-AVL REMOVE parent +, sibling = (left child)
  D V )
" 120k- 140k- 155k+ D V- 110k-
	V:XYLA-AVL REMOVE parent +, sibling + (left child)
	V:XYLA-AVL REMOVE parent = (left child)
  D V )
" 310k- 330k- 320k- D V- 340k-
	V:XYLA-AVL REMOVE parent -, sibling = (right child)
  D V )

:
:;; Counter-biased parent, cobiased sibling.

;;	     p
;;	      (+ +)			     t
;;	     /	   \	s		      (=)
;;	h - 1	     (-)	     p	 ,---'	 `---,   s
;;		t   /	\	--->  (*)	      (*)
;;		 (*)	h - 1	     /   \	     /	 \
;;		/   \		 h - 1   h - 1	 h - 1	 h - 1
;;	    h - 1   h - 1		 h - 2	 h - 2
;;	    h - 2   h - 2
" 120k- D V- 110k-
	V:XYLA-AVL REMOVE parent +, sibling -, nibling = (left child)
	V:XYLA-AVL REMOVE parent = (left child)
  D V )
" 155k+ 145k+ D V- 120k-
	V:XYLA-AVL REMOVE parent + (right child)
	V:XYLA-AVL REMOVE parent +, sibling -, nibling + (left child)
	V:XYLA-AVL REMOVE parent - (left child)
	V:XYLA-AVL REMOVE shorten tree
  D V )
" 155k+ 135k+ D V- 120k-
	V:XYLA-AVL REMOVE parent + (right child)
	V:XYLA-AVL REMOVE parent +, sibling -, nibling - (left child)
	V:XYLA-AVL REMOVE parent - (left child)
	V:XYLA-AVL REMOVE shorten tree
  D V )
" 340k- D V- 350k-
	V:XYLA-AVL REMOVE parent -, sibling +, nibling = (right child)
	V:XYLA-AVL REMOVE parent = (right child)
  D V )
" D 305k+ 325k+ D V- 340k-
	V:XYLA-AVL REMOVE parent - (left child)
	V:XYLA-AVL REMOVE parent -, sibling +, nibling + (right child)
	V:XYLA-AVL REMOVE parent + (right child)
	V:XYLA-AVL REMOVE shorten tree
  D V )
" D 305k+ 315k+ D V- 340k-
	V:XYLA-AVL REMOVE parent - (left child)
	V:XYLA-AVL REMOVE parent -, sibling +, nibling - (right child)
	V:XYLA-AVL REMOVE parent + (right child)
	V:XYLA-AVL REMOVE shorten tree
  D V )

:
:;;;-------------------------------------------------------------------------
:;;; Joining.

:
:;; Splice, short counter-biased node.
;;					    n
;;	  n				     (+)
;;	   (-)				   /	 \    m
;;	  /   \			--->	h	   (+)
;;	h     h - 1				  /   \
;;					      h - 1     h
=_ #14 14- D ( #15-17 D V~ 14k~
	V:XYLA-AVL JOIN short subtree (right child)
	V:XYLA-AVL JOIN ascent, node = (right child)
	V:XYLA-AVL JOIN extend tree (right child)
   D V
=_ #1-3 D ( #17-4 4- D V~ 4k~
	V:XYLA-AVL JOIN short subtree (left child)
	V:XYLA-AVL JOIN ascent, node = (left child)
	V:XYLA-AVL JOIN extend tree (left child)
   D V

:
:;; Splice, standard balanced or counter-biased node.
;;					      n
;;	    n				       (*)
;;	     (*)			     /	   \    m
;;	    /   \		--->	   h	     (=)
;;	  h       h			 h + 1	    /   \
;;        h + 1					  h       h
=_ #15 D ( #17-19 D V~ 16k~
	V:XYLA-AVL JOIN splice, node = (right child)
	V:XYLA-AVL JOIN ascent, node = (right child)
	V:XYLA-AVL JOIN extend tree (right child)
   D V
=_ #14 14- D ( 15+ D V~ 14k~
	V:XYLA-AVL JOIN splice, node - (right child)
   D V
=_ #1-3 D ( #19-5 D V~ 4k~
	V:XYLA-AVL JOIN splice, node = (left child)
	V:XYLA-AVL JOIN ascent, node = (left child)
	V:XYLA-AVL JOIN extend tree (left child)
   D V
=_ 1+ D ( #15-2 2- D V~ 2k~
	V:XYLA-AVL JOIN splice, node + (left child)
   D V

:
:;; Splice, cobiased node, balanced or counter-biased parent.
;;					     p
;;	      p				      (*)
;;	       (*)			    /	  \    m
;;	     /	   \    n	       h + 1	    (-)
;;	h + 1	     (+)	--->   h + 2   n   /   \
;;	h + 2	    /   \			(+)	 h
;;		h - 1	  h		       /   \
;;					   h - 1     h
=_ #12 #14-17 13+ D ( 19+ D V~ 18k~
	V:XYLA-AVL JOIN splice, node +, parent = (right child)
	V:XYLA-AVL JOIN ascent, node + (right child)
   D V
=_ #8 #10-16 14- 9+ D ( 18+ D V~ 17k~
	V:XYLA-AVL JOIN splice, node +, parent - (right child)
   D V
=_ 1+ D ( #19-7 #5-3 6+ D V~ 2k~
	V:XYLA-AVL JOIN splice, node -, parent = (left child)
	V:XYLA-AVL JOIN ascent, node - (left child)
   D V
=_ 1+ D ( #18-11 #9-3 5- 10+ D V~ 2k~
	V:XYLA-AVL JOIN splice, node -, parent + (left child)
   D V

:
:;; Splice, cobiased node, cobiased parent.
;;	   p					n
;;	    (+)					 (=)
;;	  /     \    n			 p     /     \	   m
;;	h	 (+)		--->	  (-)		(=)
;;		/   \			 /   \	       /   \
;;	    h - 1     h		       h     h - 1   h	     h
=_ #12 D ( 14+ D V~ 13k~
	V:XYLA-AVL JOIN splice, node +, parent + (right child)
   D V
=_ 1+ D ( #14-3 D V~ 2k~
	V:XYLA-AVL JOIN splice, node -, parent - (left child)
   D V

:
:;; Ascent, cobiased node.
;;						  c
;;	    n					   (=)
;;	     (+)			    n	 /     \
;;	    /   \  c		--->	     (=)	  h
;;	h - 1     h			    /	\
;;					h - 1	h - 1
=_ #13 D ( 15+ D V~ 14k~
	V:XYLA-AVL JOIN splice, node = (right child)
	V:XYLA-AVL JOIN ascent, node + (right child)
   D V
=_ 1+ D ( #15-3 D V~ 2k~
	V:XYLA-AVL JOIN splice, node = (left child)
	V:XYLA-AVL JOIN ascent, node - (left child)
   D V

:
:;; Ascent, counter-biased node.
;;					      n
;;	    n				       (=)
;;	     (-)			     /	   \    c
;;	    /   \  c		--->	h + 1	     (+)
;;	h + 1     h				    /	\
;;						h - 1	  h
=_ #8 #10-16 9+ D ( 18+ D V~ 17k~
	V:XYLA-AVL JOIN splice, node = (right child)
	V:XYLA-AVL JOIN ascent, node - (right child)
   D V
=_ 1+ D ( #18-11 #9-3 10+ D V~ 2k~
	V:XYLA-AVL JOIN splice, node = (left child)
	V:XYLA-AVL JOIN ascent, node + (left child)
   D V

:
:;; Ascent, balanced node.
;;					    n
;;	  n				     (+)
;;	   (=)				   /	 \    c
;;	  /   \  c		--->	h	   (+)
;;	h       h				  /   \
;;					      h - 1	h
=_ #15 D ( 17+ D V~ 16k~
	V:XYLA-AVL JOIN splice, node = (right child)
	V:XYLA-AVL JOIN ascent, node = (right child)
	V:XYLA-AVL JOIN ascent, node = (right child)
	V:XYLA-AVL JOIN extend tree (right child)
   D V
=_ 1+ D ( #3-17 D V~ 2k~
	V:XYLA-AVL JOIN splice, node = (left child)
	V:XYLA-AVL JOIN ascent, node = (left child)
	V:XYLA-AVL JOIN ascent, node = (left child)
	V:XYLA-AVL JOIN extend tree (left child)
   D V

:
:;;;----- That's all, folks -------------------------------------------------