Package com.zybooks.dsaj.searchtree

Class TreeMap.BalanceableBinaryTree<K,V>

java.lang.Object

com.zybooks.dsaj.tree.AbstractTree<E>

com.zybooks.dsaj.tree.AbstractBinaryTree<E>

com.zybooks.dsaj.tree.LinkedBinaryTree<Entry<K,V>>

com.zybooks.dsaj.searchtree.TreeMap.BalanceableBinaryTree<K,V>

Type Parameters:

K - The key type (keys must be unique and comparable)

V - The value type

All Implemented Interfaces:

BinaryTree<Entry<K,V>>, Tree<Entry<K,V>>, Iterable<Entry<K,V>>

Enclosing class:

TreeMap<K,V>

protected static class TreeMap.BalanceableBinaryTree<K,V>
extends LinkedBinaryTree<Entry<K,V>>

A specialized version of the LinkedBinaryTree class with additional mutators to support binary search tree operations, and a specialized node class that includes an auxiliary instance variable for balancing data.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	TreeMap.BalanceableBinaryTree.BSTNode<E>	A specialized version of Node that includes an auxiliary int for balancing algorithms

Nested classes/interfaces inherited from class com.zybooks.dsaj.tree.LinkedBinaryTree

LinkedBinaryTree.Node<E>

Field Summary

Fields inherited from class com.zybooks.dsaj.tree.LinkedBinaryTree

root

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	BalanceableBinaryTree()

Method Summary

Modifier and Type	Method	Description
protected LinkedBinaryTree.Node<Entry<K,V>>	createNode(Entry<K,V> e, LinkedBinaryTree.Node<Entry<K,V>> parent, LinkedBinaryTree.Node<Entry<K,V>> left, LinkedBinaryTree.Node<Entry<K,V>> right)	Factory function to create a new node storing element e.
int	getAux(Position<Entry<K,V>> p)
Position<Entry<K,V>>	restructure(Position<Entry<K,V>> x)	Performs a trinode restructoring of Position x with its parent/grandparent.
void	rotate(Position<Entry<K,V>> p)	Rotates Position p above its parent.
void	setAux(Position<Entry<K,V>> p, int value)

Methods inherited from class com.zybooks.dsaj.tree.LinkedBinaryTree

addLeft, addRight, addRoot, attach, left, parent, remove, right, root, set, size, validate

Methods inherited from class com.zybooks.dsaj.tree.AbstractBinaryTree

children, inorder, numChildren, positions, sibling

Methods inherited from class com.zybooks.dsaj.tree.AbstractTree

breadthfirst, depth, height, isEmpty, isExternal, isInternal, isRoot, iterator, postorder, preorder

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface com.zybooks.dsaj.tree.Tree

isEmpty, isExternal, isInternal, isRoot, iterator

Constructor Details

BalanceableBinaryTree

protected BalanceableBinaryTree()

Method Details

getAux

public int getAux(Position<Entry<K,V>> p)

setAux

public void setAux(Position<Entry<K,V>> p,
 int value)

createNode

protected LinkedBinaryTree.Node<Entry<K,V>> createNode(Entry<K,V> e,
 LinkedBinaryTree.Node<Entry<K,V>> parent,
 LinkedBinaryTree.Node<Entry<K,V>> left,
 LinkedBinaryTree.Node<Entry<K,V>> right)

Description copied from class: LinkedBinaryTree

Factory function to create a new node storing element e.

Overrides:

createNode in class LinkedBinaryTree<Entry<K,V>>

rotate

public void rotate(Position<Entry<K,V>> p)

Rotates Position p above its parent. Switches between these configurations, depending on whether p is a or p is b.

          b                  a
         / \                / \
        a  t2             t0   b
       / \                    / \
      t0  t1                 t1  t2

Caller should ensure that p is not the root.

restructure

public Position<Entry<K,V>> restructure(Position<Entry<K,V>> x)

Performs a trinode restructoring of Position x with its parent/grandparent. Returns the Position that becomes the root of the restructured subtree. Assumes the nodes are in one of the following configurations:

     z=a                 z=c           z=a               z=c
    /  \                /  \          /  \              /  \
   t0  y=b             y=b  t3       t0   y=c          y=a  t3
      /  \            /  \               /  \         /  \
     t1  x=c         x=a  t2            x=b  t3      t0   x=b
        /  \        /  \               /  \              /  \
       t2  t3      t0  t1             t1  t2            t1  t2

The subtree will be restructured so that the node with key b becomes its root.

           b
         /   \
       a       c
      / \     / \
     t0  t1  t2  t3

Caller should ensure that x has a grandparent.