Skip to content
GitLab
Explore
Sign in
Primary navigation
Search or go to…
Project
E
ex08-verifyavl-public
Manage
Activity
Members
Labels
Plan
Issues
0
Issue boards
Milestones
Wiki
Code
Merge requests
1
Repository
Branches
Commits
Tags
Repository graph
Compare revisions
Snippets
Build
Pipelines
Jobs
Pipeline schedules
Artifacts
Deploy
Releases
Package Registry
Model registry
Operate
Environments
Terraform modules
Monitor
Incidents
Analyze
Value stream analytics
Contributor analytics
CI/CD analytics
Repository analytics
Model experiments
Help
Help
Support
GitLab documentation
Compare GitLab plans
Community forum
Contribute to GitLab
Provide feedback
Keyboard shortcuts
?
Snippets
Groups
Projects
This is an archived project. Repository and other project resources are read-only.
Show more breadcrumbs
cse332-22wi
ex08-verifyavl-public
Merge requests
!1
An error occurred while fetching the assigned milestone of the selected merge_request.
Update VerifyAVL.java
Code
Review changes
Check out branch
Download
Patches
Plain diff
Open
Update VerifyAVL.java
sxu4/ex08-verifyavl-public:sxu4-master-patch-90741
into
master
Overview
0
Commits
1
Pipelines
0
Changes
1
Open
Isaac Xu
requested to merge
sxu4/ex08-verifyavl-public:sxu4-master-patch-90741
into
master
2 years ago
Overview
0
Commits
1
Pipelines
0
Changes
1
Expand
0
0
Merge request reports
Compare
master
master (HEAD)
and
latest version
latest version
698784f8
1 commit,
2 years ago
1 file
+
50
−
3
Inline
Compare changes
Side-by-side
Inline
Show whitespace changes
Show one file at a time
src/main/java/verifyavl/VerifyAVL.java
+
50
−
3
Options
@@ -2,8 +2,55 @@ package verifyavl;
public
class
VerifyAVL
{
public
static
boolean
verifyAVL
(
AVLNode
root
)
{
/* TODO: Edit this with your code */
throw
new
IllegalStateException
();
if
(
root
==
null
)
{
return
true
;
}
boolean
isBst
=
verifyBst
(
root
.
left
,
root
.
right
,
root
);
int
hDiff
=
verifyBalance
(
root
);
boolean
isBalanced
=
true
;
if
(
hDiff
>
1
)
{
isBalanced
=
false
;
}
if
((!
isBst
||
!
isBalanced
)
||
(!
verifyAVL
(
root
.
left
)
||
!
verifyAVL
(
root
.
right
)))
{
return
false
;
}
return
true
;
}
/* TODO: Add private methods if you want (recommended) */
}
\ No newline at end of file
private
static
boolean
verifyBst
(
AVLNode
left
,
AVLNode
right
,
AVLNode
root
)
{
if
(
left
!=
null
&&
left
.
key
>
root
.
key
)
{
return
false
;
}
else
if
(
right
!=
null
&&
right
.
key
<
root
.
key
)
{
return
false
;
}
return
true
;
}
private
static
int
verifyBalance
(
AVLNode
root
)
{
int
leftH
=
getLeftTotalH
(
root
.
left
);
int
rightH
=
getRightTotalH
(
root
.
right
);
if
(
root
.
left
!=
null
)
{
leftH
+=
root
.
left
.
height
;
}
if
(
root
.
right
!=
null
)
{
rightH
+=
root
.
right
.
height
;
}
return
Math
.
abs
(
leftH
-
rightH
);
}
private
static
int
getLeftTotalH
(
AVLNode
root
)
{
if
(
root
==
null
)
{
return
0
;
}
return
root
.
height
+
getLeftTotalH
(
root
.
left
);
}
private
static
int
getRightTotalH
(
AVLNode
root
)
{
if
(
root
==
null
)
{
return
0
;
}
return
root
.
height
+
getRightTotalH
(
root
.
right
);
}
}
Loading