The extends keyword is used when class/interface A extends the functionality of another class/interface B . In the case of interfaces, A is not an implementation, but rather an expanded-upon contract. An extension has access to all of the public members of its superclass, its constructor is accessed through super() , and any members of the superclass can be accessed with super.
public class A extends B {
public A () {
// ...
}
// -- Equivalent to -- //
public A() {
super();
// ...
}
}
Data structure where every node $X$ is stored in a tree with the property that every node with key less than the key of $X$ is in the left subtree of $X$ and its right subtree otherwise.
Such an ordering property is said to be complete (any element contained can be compared), transitive, and antisymmetric (no two elements are equal in comparison).
Any binary search tree can be characterized by how “bushy” it is. A bushy BST has height $\Theta (\log N)$ (most nodes have 2 or no children) and a spindly BST has height $\Theta(N)$ (most nodes have exactly one child).
A spindly tree degenerates back into a linked list, making a BST’s operations much slower. This course discusses two self-balancing variations of the BST data structure which avoid this pitfall.
Generalization of a BST where each node stores a sequence, with length up to $L$, of keys that divide its subtrees.
Balancing Invariants. A B-Tree is well-formed if each node has at most $L$ elements and $L+1$ children. This establishes the following invariants: all leaves are the same distance from the root and all non-leaves with $k$ items must have $k+1$ children.
When a full sequence is inserted into, the second element is promoted to the parent sequence and the initial sequence is split such that every element is between any two elements in the parent sequence.
The height of a B-Tree of order $L$ is $\Theta (\log N)$ under the balancing invariants and searching through each sequence is linear in $L$. The time complexity of contains and insert thus remain logarithmic. Handling different node types and node splitting is an implementation nightmare, so it is usually more common to see the following variant.
BST which preserves the structure of a 2-3 tree, a B-Tree of order $2$, by using red links to join 2 nodes that would otherwise be in the same parent sequence.