#include "stdio.h" 
#include "stdlib.h" 
#include "string.h" 
#include "avl_tree.h" 
#include "avl_tree.h" 
void
O110011100001
(
const
char
*
l110011100010
)
{
printf
(
"%s\n"
,
l110011100010
)
;
exit
(
01
)
;
}
const
unsigned
l110011100011
=
(
~
(
(
(
unsigned
)
(
~
0
)
)
>>
01
)
)
;
struct
{
signed
char
l110010000100
;
int
O110011100100
;
unsigned
l110001111000
,
lt
;
}
l110011100101
[
0621
]
,
O110011100110
[
0620
]
;
class
l110001111001
{
public
:
typedef
unsigned
l110001111010
;
typedef
unsigned
size
;
typedef
int
O110001111011
;
static
l110001111010
l110001111100
(
l110001111010
h
,
bool
access
)
{
if
(
!
(
h
&
l110011100011
)
)
O110011100001
(
"get_less"
)
;
l110001111010
O110011001011
=
l110011100101
[
h
&
~
l110011100011
]
.
lt
;
if
(
access
)
O110011001011
|=
l110011100011
;
return
(
O110011001011
)
;
}
static
void
l110001111101
(
l110001111010
h
,
l110001111010
O110001111110
)
{
if
(
!
(
h
&
l110011100011
)
)
{
printf
(
"%x %x\n"
,
h
,
O110001111110
)
;
O110011100001
(
"set_less"
)
;
}
if
(
O110001111110
!=
~
0
)
O110001111110
&=
~
l110011100011
;
l110011100101
[
h
&
~
l110011100011
]
.
lt
=
O110001111110
;
}
static
l110001111010
l110001111111
(
l110001111010
h
,
bool
access
)
{
if
(
!
(
h
&
l110011100011
)
)
O110011100001
(
"get_greater"
)
;
l110001111010
O110011001011
=
l110011100101
[
h
&
~
l110011100011
]
.
l110001111000
;
if
(
access
)
O110011001011
|=
l110011100011
;
return
(
O110011001011
)
;
}
static
void
l110010000000
(
l110001111010
h
,
l110001111010
O110010000001
)
{
if
(
!
(
h
&
l110011100011
)
)
O110011100001
(
"set_greater"
)
;
if
(
O110010000001
!=
~
0
)
O110010000001
&=
~
l110011100011
;
l110011100101
[
h
&
~
l110011100011
]
.
l110001111000
=
O110010000001
;
}
static
int
l110010000010
(
l110001111010
h
)
{
if
(
!
(
h
&
l110011100011
)
)
O110011100001
(
"get_balance_factor"
)
;
return
(
l110011100101
[
h
&
~
l110011100011
]
.
l110010000100
)
;
}
static
void
O110010000011
(
l110001111010
h
,
int
l110010000100
)
{
if
(
!
(
h
&
l110011100011
)
)
O110011100001
(
"set_balance_factor"
)
;
l110011100101
[
h
&
~
l110011100011
]
.
l110010000100
=
l110010000100
;
}
static
int
l110010000101
(
O110001111011
O110010000110
,
l110001111010
h
)
{
if
(
!
(
h
&
l110011100011
)
)
O110011100001
(
"compare_key_node"
)
;
return
(
O110010000110
-
l110011100101
[
h
&
~
l110011100011
]
.
O110011100100
)
;
}
static
int
l110010000111
(
l110001111010
l110010001000
,
l110001111010
O110010001001
)
{
if
(
!
(
l110010001000
&
l110011100011
)
)
O110011100001
(
"compare_node_node - h1"
)
;
if
(
!
(
O110010001001
&
l110011100011
)
)
O110011100001
(
"compare_node_node - h2"
)
;
return
(
l110011100101
[
l110010001000
&
~
l110011100011
]
.
O110011100100
-
l110011100101
[
O110010001001
&
~
l110011100011
]
.
O110011100100
)
;
}
static
l110001111010
l110010001010
(
void
)
{
return
(
~
0
)
;
}
static
bool
l110010001011
(
void
)
{
return
(
false
)
;
}
}
;
class
l110011100111
:
public
l110010001100
::
O110010001101
<
l110001111001
>
{
public
:
l110001111010
&
O110011101000
;
l110011100111
(
void
)
:
O110011101000
(
l110010110101
)
{
}
}
;
l110011100111
O110010001111
;
typedef
l110011100111
::
O110010010010
O110010010010
;
int
l110011101001
(
unsigned
l110011101010
=
O110010001111
.
O110011101000
&
~
l110011100011
)
{
int
l110011101011
,
l110011101100
;
unsigned
h
;
if
(
l110011100101
[
l110011101010
]
.
lt
==
~
0
)
l110011101011
=
0
;
else
{
h
=
l110011100101
[
l110011101010
]
.
lt
&
~
l110011100011
;
if
(
l110011100101
[
l110011101010
]
.
O110011100100
<=
l110011100101
[
h
]
.
O110011100100
)
{
printf
(
"not less: %u %d %d %d\n"
,
l110011101010
,
l110011100101
[
l110011101010
]
.
O110011100100
,
h
,
l110011100101
[
h
]
.
O110011100100
)
;
O110011100001
(
"verify_tree"
)
;
}
l110011101011
=
l110011101001
(
h
)
;
}
if
(
l110011100101
[
l110011101010
]
.
l110001111000
==
~
0
)
l110011101100
=
0
;
else
{
h
=
l110011100101
[
l110011101010
]
.
l110001111000
&
~
l110011100011
;
if
(
l110011100101
[
l110011101010
]
.
O110011100100
>=
l110011100101
[
h
]
.
O110011100100
)
{
printf
(
"not greater: %u %d %d %d\n"
,
l110011101010
,
l110011100101
[
l110011101010
]
.
O110011100100
,
h
,
l110011100101
[
h
]
.
O110011100100
)
;
O110011100001
(
"verify_tree"
)
;
}
l110011101100
=
l110011101001
(
h
)
;
}
if
(
l110011100101
[
l110011101010
]
.
l110010000100
!=
(
l110011101100
-
l110011101011
)
)
{
printf
(
"bad bf: n=%u bf=%d gd=%d ld=%d\n"
,
l110011101010
,
l110011100101
[
l110011101010
]
.
l110010000100
,
l110011101100
,
l110011101011
)
;
O110011100001
(
"verify_tree"
)
;
}
return
(
(
l110011101100
>
l110011101011
?
l110011101100
:
l110011101011
)
+
01
)
;
}
void
l110011101101
(
void
)
{
if
(
O110010001111
.
O110011101000
!=
~
0
)
O110011100001
(
"not empty"
)
;
}
void
insert
(
unsigned
h
)
{
unsigned
l110011101110
=
O110010001111
.
insert
(
h
|
l110011100011
)
;
if
(
l110011101110
==
~
0
)
O110011100001
(
"insert null"
)
;
l110011101110
&=
~
l110011100011
;
if
(
l110011100101
[
h
]
.
O110011100100
!=
l110011100101
[
l110011101110
]
.
O110011100100
)
{
printf
(
"bad - %u %u\n"
,
h
,
l110011101110
)
;
O110011100001
(
"insert"
)
;
}
}
void
remove
(
int
O110010000110
,
bool
O110011101111
=
false
)
{
unsigned
l110011101110
=
O110010001111
.
remove
(
O110010000110
)
;
if
(
l110011101110
==
~
0
)
{
if
(
!
O110011101111
)
{
printf
(
"null key=%d\n"
,
O110010000110
)
;
O110011100001
(
"remove"
)
;
}
}
else
{
if
(
O110011101111
)
{
printf
(
"not null key=%d rh=%u\n"
,
O110010000110
,
l110011101110
)
;
O110011100001
(
"remove"
)
;
}
l110011101110
&=
~
l110011100011
;
if
(
l110011100101
[
l110011101110
]
.
O110011100100
!=
O110010000110
)
{
printf
(
"wrong key=%d rh=%u [rh].val=%d\n"
,
O110010000110
,
l110011101110
,
l110011100101
[
l110011101110
]
.
O110011100100
)
;
O110011100001
(
"remove"
)
;
}
l110011100101
[
l110011101110
]
.
l110010000100
=
0173
;
}
}
unsigned
l110011110000
;
void
l110011110001
(
void
)
{
unsigned
l110010100101
=
l110011110000
;
while
(
l110010100101
)
{
l110010100101
--
;
l110011100101
[
l110010100101
]
.
l110010000100
=
0173
;
}
}
void
l110011110010
(
int
O110001111011
,
l110010001100
::
l110010101000
O110010110010
,
unsigned
l110011101110
)
{
if
(
O110010001111
.
search
(
O110001111011
,
O110010110010
)
!=
(
l110011101110
|
l110011100011
)
)
{
printf
(
"%d %x %u\n"
,
O110001111011
,
(
unsigned
)
O110010110010
,
l110011101110
)
;
O110011100001
(
"search_test"
)
;
}
O110010010010
l110010010011
;
l110010010011
.
l110010111000
(
O110010001111
,
O110001111011
,
O110010110010
)
;
if
(
*
l110010010011
!=
(
l110011101110
|
l110011100011
)
)
{
printf
(
"%d %x %x %x\n"
,
O110001111011
,
(
unsigned
)
O110010110010
,
l110011101110
,
*
l110010010011
)
;
O110011100001
(
"search_test - iter"
)
;
}
if
(
(
O110010110010
==
l110010001100
::
l110010101001
)
&&
(
l110011101110
!=
~
0
)
)
{
unsigned
h
=
*
l110010010011
;
O110010010010
O110011110011
=
l110010010011
;
l110010010011
++
;
O110011110011
--
;
if
(
*
l110010010011
!=
O110010001111
.
search
(
O110001111011
,
l110010001100
::
O110010101011
)
)
{
printf
(
"%d %x %x %x\n"
,
O110001111011
,
(
unsigned
)
O110010110010
,
h
,
*
l110010010011
)
;
O110011100001
(
"search_test - iter ++"
)
;
}
if
(
*
O110011110011
!=
O110010001111
.
search
(
O110001111011
,
l110010001100
::
O110010101010
)
)
{
printf
(
"%d %x %x %x\n"
,
O110001111011
,
(
unsigned
)
O110010110010
,
h
,
*
O110011110011
)
;
O110011100001
(
"search_test - iter --"
)
;
}
}
return
;
}
void
l110011110010
(
unsigned
h
)
{
if
(
l110011100101
[
h
]
.
l110010000100
==
0173
)
l110011110010
(
02
*
h
,
l110010001100
::
l110010101001
,
~
0
)
;
else
{
l110011110010
(
02
*
h
,
l110010001100
::
l110010101001
,
h
)
;
l110011110010
(
02
*
h
,
l110010001100
::
O110010101100
,
h
)
;
l110011110010
(
02
*
h
,
l110010001100
::
O110010101101
,
h
)
;
l110011110010
(
02
*
h
+
01
,
l110010001100
::
l110010101001
,
~
0
)
;
l110011110010
(
02
*
h
+
01
,
l110010001100
::
O110010101010
,
h
)
;
l110011110010
(
02
*
h
+
01
,
l110010001100
::
O110010101100
,
h
)
;
l110011110010
(
02
*
h
-
01
,
l110010001100
::
l110010101001
,
~
0
)
;
l110011110010
(
02
*
h
-
01
,
l110010001100
::
O110010101011
,
h
)
;
l110011110010
(
02
*
h
-
01
,
l110010001100
::
O110010101101
,
h
)
;
}
}
void
O110011110100
(
void
)
{
unsigned
h
=
l110011110000
,
min
=
~
0
,
max
=
~
0
;
while
(
h
)
{
h
--
;
l110011110010
(
h
)
;
if
(
l110011100101
[
h
]
.
l110010000100
!=
0173
)
{
if
(
max
==
~
0
)
max
=
h
;
min
=
h
;
}
}
h
=
O110010001111
.
l110010110011
(
)
;
if
(
h
!=
(
min
|
l110011100011
)
)
{
printf
(
"%x %x\n"
,
h
,
min
)
;
O110011100001
(
"search_all least"
)
;
}
h
=
O110010001111
.
l110010110100
(
)
;
if
(
h
!=
(
max
|
l110011100011
)
)
{
printf
(
"%x %x\n"
,
h
,
max
)
;
O110011100001
(
"search_all greatest"
)
;
}
O110010010010
l110010010011
;
l110010010011
.
O110010010100
(
O110010001111
)
;
if
(
*
l110010010011
!=
(
min
|
l110011100011
)
)
{
printf
(
"%x %x\n"
,
h
,
min
)
;
O110011100001
(
"search_all least - iter"
)
;
}
while
(
*
l110010010011
!=
(
max
|
l110011100011
)
)
{
h
=
*
l110010010011
;
l110010010011
++
;
if
(
*
l110010010011
!=
O110010001111
.
search
(
02
*
h
,
l110010001100
::
O110010101011
)
)
{
printf
(
"%x %x\n"
,
h
,
*
l110010010011
)
;
O110011100001
(
"search_all increment - iter"
)
;
}
}
l110010010011
++
;
if
(
*
l110010010011
!=
~
0
)
O110011100001
(
"search_all increment - end"
)
;
l110010010011
.
O110011000011
(
O110010001111
)
;
if
(
*
l110010010011
!=
(
max
|
l110011100011
)
)
{
printf
(
"%x %x\n"
,
h
,
max
)
;
O110011100001
(
"search_all greatest - iter"
)
;
}
while
(
*
l110010010011
!=
(
min
|
l110011100011
)
)
{
h
=
*
l110010010011
;
l110010010011
--
;
if
(
*
l110010010011
!=
O110010001111
.
search
(
02
*
h
,
l110010001100
::
O110010101010
)
)
{
printf
(
"%x %x\n"
,
h
,
*
l110010010011
)
;
O110011100001
(
"search_all increment - iter"
)
;
}
}
l110010010011
--
;
if
(
*
l110010010011
!=
~
0
)
O110011100001
(
"search_all increment - end"
)
;
}
void
l110010010001
(
unsigned
l110011101010
,
unsigned
O110010110111
)
{
if
(
l110011100101
[
l110011101010
]
.
lt
!=
~
0
)
l110010010001
(
l110011100101
[
l110011101010
]
.
lt
,
O110010110111
+
01
)
;
printf
(
"%u(%u, %d) "
,
l110011101010
,
O110010110111
,
l110011100101
[
l110011101010
]
.
l110010000100
)
;
if
(
l110011100101
[
l110011101010
]
.
l110001111000
!=
~
0
)
l110010010001
(
l110011100101
[
l110011101010
]
.
l110001111000
,
O110010110111
+
01
)
;
}
void
l110010010001
(
void
)
{
l110010010001
(
O110010001111
.
O110011101000
&
~
l110011100011
,
0
)
;
putchar
(
'\012'
)
;
}
void
O110011110101
(
unsigned
l110011110110
,
unsigned
l110011110111
)
{
unsigned
in
=
0
,
O110011011101
=
0
;
printf
(
"inserting\n"
)
;
do
{
insert
(
in
)
;
l110011101001
(
)
;
in
+=
l110011110110
;
in
%=
l110011110000
;
}
while
(
in
!=
0
)
;
O110011110100
(
)
;
printf
(
"removing\n"
)
;
for
(
;
;
)
{
remove
(
O110011011101
*
02
)
;
O110011011101
+=
l110011110111
;
O110011011101
%=
l110011110000
;
if
(
O110011011101
==
0
)
break
;
l110011101001
(
)
;
}
l110011101101
(
)
;
}
class
O110011111000
{
private
:
unsigned
O110011111001
;
struct
l110011111010
{
unsigned
l110010110101
,
size
;
}
;
l110011111010
O110011111011
;
l110011111010
first
(
unsigned
start
,
unsigned
O110010110111
)
{
l110011111010
O110011111100
;
if
(
O110010110111
==
0
)
{
O110011111100
.
size
=
0
;
O110011111100
.
l110010110101
=
~
0
;
}
else
if
(
O110010110111
==
01
)
{
O110011100110
[
start
]
.
l110010000100
=
0
;
O110011100110
[
start
]
.
lt
=
~
0
;
O110011100110
[
start
]
.
l110001111000
=
~
0
;
O110011111100
.
size
=
01
;
O110011111100
.
l110010110101
=
start
;
}
else
{
O110011111100
=
first
(
start
,
O110010110111
-
01
)
;
start
+=
O110011111100
.
size
;
O110011100110
[
start
]
.
l110010000100
=
-
01
;
O110011100110
[
start
]
.
lt
=
O110011111100
.
l110010110101
;
l110011111010
l110011111101
=
first
(
start
+
01
,
O110010110111
-
02
)
;
O110011100110
[
start
]
.
l110001111000
=
l110011111101
.
l110010110101
;
O110011111100
.
l110010110101
=
start
;
O110011111100
.
size
+=
l110011111101
.
size
+
01
;
}
return
(
O110011111100
)
;
}
l110011111010
l110011111110
(
unsigned
start
,
unsigned
l110011101010
,
unsigned
O110010110111
)
{
l110011111010
O110011111100
;
if
(
O110010110111
<
02
)
O110011111100
.
size
=
0
;
else
{
O110011111100
=
l110011111110
(
l110011101010
+
01
,
O110011100110
[
l110011101010
]
.
l110001111000
,
O110010110111
-
(
O110011100110
[
l110011101010
]
.
l110010000100
==
-
01
?
02
:
01
)
)
;
if
(
O110011111100
.
size
!=
0
)
{
O110011100110
[
l110011101010
]
.
l110001111000
=
O110011111100
.
l110010110101
;
O110011111100
.
size
+=
l110011101010
-
start
+
01
;
O110011111100
.
l110010110101
=
l110011101010
;
}
else
{
int
l110010000100
=
O110011100110
[
l110011101010
]
.
l110010000100
;
O110011111100
=
l110011111110
(
start
,
O110011100110
[
l110011101010
]
.
lt
,
O110010110111
-
(
l110010000100
==
01
?
02
:
01
)
)
;
if
(
O110011111100
.
size
==
0
)
{
if
(
l110010000100
==
01
)
return
(
O110011111100
)
;
l110010000100
++
;
O110011111100
=
first
(
start
,
O110010110111
-
(
l110010000100
==
01
?
02
:
01
)
)
;
}
start
+=
O110011111100
.
size
;
O110011100110
[
start
]
.
lt
=
O110011111100
.
l110010110101
;
O110011111100
.
l110010110101
=
start
;
l110011111010
l110011111101
=
first
(
O110011111100
.
l110010110101
+
01
,
O110010110111
-
(
l110010000100
==
-
01
?
02
:
01
)
)
;
O110011100110
[
O110011111100
.
l110010110101
]
.
l110001111000
=
l110011111101
.
l110010110101
;
O110011100110
[
O110011111100
.
l110010110101
]
.
l110010000100
=
l110010000100
;
O110011111100
.
size
+=
l110011111101
.
size
+
01
;
}
}
return
(
O110011111100
)
;
}
void
l110010010001
(
unsigned
l110011101010
,
unsigned
O110010110111
)
{
if
(
O110011100110
[
l110011101010
]
.
lt
!=
~
0
)
l110010010001
(
O110011100110
[
l110011101010
]
.
lt
,
O110010110111
+
01
)
;
printf
(
"%u(%u, %d) "
,
l110011101010
,
O110010110111
,
O110011100110
[
l110011101010
]
.
l110010000100
)
;
if
(
O110011100110
[
l110011101010
]
.
l110001111000
!=
~
0
)
l110010010001
(
O110011100110
[
l110011101010
]
.
l110001111000
,
O110010110111
+
01
)
;
}
public
:
void
O110011111111
(
void
)
{
memcpy
(
l110011100101
,
O110011100110
,
O110011111011
.
size
*
sizeof
(
l110011100101
[
0
]
)
)
;
O110010001111
.
O110011101000
=
O110011111011
.
l110010110101
|
l110011100011
;
}
void
first
(
unsigned
O110010111101
)
{
O110011111001
=
O110010111101
;
O110011111011
=
first
(
0
,
O110011111001
)
;
}
bool
l110011111110
(
void
)
{
if
(
O110011111011
.
size
==
0
)
O110011100001
(
"possible_trees::next"
)
;
O110011111011
=
l110011111110
(
0
,
O110011111011
.
l110010110101
,
O110011111001
)
;
return
(
O110011111011
.
size
>
0
)
;
}
void
l110010010001
(
void
)
{
l110010010001
(
O110011111011
.
l110010110101
,
0
)
;
putchar
(
'\012'
)
;
}
O110011111000
(
void
)
{
O110011111011
.
size
=
0
;
}
}
;
O110011111000
O110100000000
;
void
O110100000001
(
void
)
{
O110100000000
.
O110011111111
(
)
;
unsigned
h
=
O110010001111
.
l110010110011
(
)
;
while
(
h
!=
~
0
)
{
l110011100101
[
0620
]
.
O110011100100
=
02
*
h
-
01
;
insert
(
0620
)
;
l110011101001
(
)
;
O110100000000
.
O110011111111
(
)
;
l110011100101
[
0620
]
.
O110011100100
=
02
*
h
+
01
;
insert
(
0620
)
;
l110011101001
(
)
;
O110100000000
.
O110011111111
(
)
;
remove
(
02
*
h
)
;
l110011101001
(
)
;
O110100000000
.
O110011111111
(
)
;
h
=
O110010001111
.
search
(
02
*
h
,
l110010001100
::
O110010101011
)
;
}
}
void
O110100000010
(
unsigned
O110010110111
)
{
O110100000000
.
first
(
O110010110111
)
;
do
O110100000001
(
)
;
while
(
O110100000000
.
l110011111110
(
)
)
;
}
unsigned
O110100000011
[
0620
]
;
void
O110100000100
(
void
)
{
unsigned
l110010100101
;
O110010001111
.
O110011000110
(
O110100000011
,
0
)
;
l110011101101
(
)
;
for
(
l110010100101
=
0
;
l110010100101
<
0620
;
l110010100101
++
)
{
O110100000011
[
l110010100101
]
=
l110010100101
|
l110011100011
;
O110010001111
.
O110011000110
(
O110100000011
,
l110010100101
+
01
)
;
l110011101001
(
)
;
}
}
int
main
(
)
{
unsigned
l110010100101
;
for
(
l110010100101
=
0
;
l110010100101
<
0620
;
l110010100101
++
)
O110011100110
[
l110010100101
]
.
O110011100100
=
l110010100101
*
02
;
memcpy
(
l110011100101
,
O110011100110
,
sizeof
(
l110011100101
)
)
;
l110011110000
=
03
;
l110011110001
(
)
;
printf
(
"0 nodes\n"
)
;
l110011101101
(
)
;
O110011110100
(
)
;
printf
(
"1 node\n"
)
;
insert
(
01
)
;
insert
(
01
)
;
l110011101001
(
)
;
O110011110100
(
)
;
remove
(
02
)
;
remove
(
02
,
true
)
;
l110011101101
(
)
;
printf
(
"2 nodes less slant\n"
)
;
insert
(
02
)
;
insert
(
02
)
;
insert
(
01
)
;
insert
(
01
)
;
l110011101001
(
)
;
O110011110100
(
)
;
remove
(
02
)
;
remove
(
02
,
true
)
;
insert
(
01
)
;
l110011101001
(
)
;
remove
(
04
)
;
remove
(
04
,
true
)
;
l110011101001
(
)
;
remove
(
02
)
;
l110011101101
(
)
;
printf
(
"2 nodes greater slant\n"
)
;
insert
(
01
)
;
insert
(
01
)
;
insert
(
02
)
;
insert
(
02
)
;
l110011101001
(
)
;
O110011110100
(
)
;
remove
(
04
)
;
remove
(
04
,
true
)
;
insert
(
02
)
;
l110011101001
(
)
;
remove
(
02
)
;
remove
(
02
,
true
)
;
l110011101001
(
)
;
remove
(
04
)
;
l110011101101
(
)
;
l110011110000
=
0620
;
printf
(
"%u nodes\n"
,
l110011110000
)
;
l110011110001
(
)
;
O110011110101
(
03
,
07
)
;
O110011110101
(
015
,
07
)
;
printf
(
"all trees depth 3\n"
)
;
O110100000010
(
03
)
;
printf
(
"all trees depth 4\n"
)
;
O110100000010
(
04
)
;
printf
(
"all trees depth 5\n"
)
;
O110100000010
(
05
)
;
printf
(
"build test\n"
)
;
O110100000100
(
)
;
printf
(
"SUCCESS!\n"
)
;
return
(
0
)
;
}