Skip to Main Content
Beginning Java Data Structures and Algorithms
book

Beginning Java Data Structures and Algorithms

by James Cutajar
July 2018
Beginner content levelBeginner
202 pages
5h 4m
English
Packt Publishing
Content preview from Beginning Java Data Structures and Algorithms

Balanced Binary Search Trees

The performance of a binary search tree is proportional to its height. This is because the search and insert operations start from the root and proceed down the tree one node at a time, doing a key comparison at each step. The taller the tree, the more steps are needed to accomplish this. Thus, if we determine the maximum possible height of a binary tree in relation to its input, we can find out the worst runtime complexity.

If we insert keys in a binary tree, by always adding on the right child of the parent node, we end up with a tree similar to the one shown on the left-hand side of Figure 3.12. In this diagram, only the right child pointers on each node are being used. We end up with a tree of height n, where ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Java 9 Data Structures and Algorithms

Java 9 Data Structures and Algorithms

Debasish Ray Chawdhuri
Object-Oriented Data Structures Using Java, 4th Edition

Object-Oriented Data Structures Using Java, 4th Edition

Nell Dale, Daniel T. Joyce, Chip Weems

Publisher Resources

ISBN: 9781789537178Supplemental Content