CPSC 319 Lecture Notes - Lecture 8: Binary Search Tree, Binary Tree, Crazy Eights

• School: University of Calgary
• Department: Computer Science
• Course: CPSC 319
• Professor: Leonard Manzara

Document Summary

Searches and insertions are most efficient when a binary tree is well-balanced. Binary trees may become unbalanced after insertions and deletions. In the worst case, the tree degenerates into a linked list. There are several variants of ordered binary trees that remain well-balanced after insertions and deletions: avl trees are one example. Definition: is the height of the right subtree minus the height of the left subtree: x]t]#2s # = _!8 /s!8 / # where n is some node in the tree. Adel"son-vel"skii and e. m. landis: developed in 1962. Definition: is an ordered binary tree where every node has a balance of -1, 0 or +1. Note that the differences between the subtrees can never exceed 1. Must add a balance field to the node class used for binary search trees: private int data; private node parent, left, right; private int balance; public class node {