prev:[[start gitlet]]
next:[[61B-part5-2-hashing]]
disjoint sets: see [[Algs1.5_UnionFind]]

Abstract Data Types

it is defined only by its operations, not by its implementation.
for example: stack is defined by its operation: push(int x) and int pop(), not by its implementation (Array or LinkedList)

Collections

One of the most important interfaces in Java.
Maps, Lists, Sets are inherianted from it.

Maps

example:

1
2
3
4
5
6
7
Map<String, Integer> m = new TreeMap<>();
String[] text = {"sumomo", "mo", "momo", "mo",
                 "momo", "no", "uchi"};
for (String s : text) {
   int currentCount = m.getOrDefault(s, 0);
   m.put(s, currentCount + 1);
}

the contents:

sumomo 1
mo 2
momo 2
no 1
uchi 1
Basic ideas behind the TreeMaps and TreeSets: BST (Binary Search Tree)

BSTs (Binary Search Trees)

The search in single linked list is very slow in Java.
![[LinkedList.png]]
To optimize it:

  • Skip list (won’t be discussed): Add (random) express lanes
    ![[SkipList.png]]
  • Move pointer to middle and flip left links. It is faster!
    ![[BST0.png]]
    How to make it even faster? – think of the recursion!
    ![[BST1.png]]
    just do the middle search recursively, and then get the result.

definitions

Tree

consists of:

  • A set of nodes.
  • A set of edges that connect those nodes.
  • Constraint: There is exactly one path between any two nodes.

Binary tree

a tree that a parent have 0/1/2 kids

BST

Ordering must be complete, transitive, and antisymmetric. Given keys p and q:

  • Exactly one of p ≺ q and q ≺ p are true.
  • p ≺ q and q ≺ r imply p ≺ r.

Operations

Finding

If searchKey equals T.key, return.

  • If searchKey ≺ T.key, search T.left.
  • If searchKey ≻ T.key, search T.right.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    static BST find(BST T, Key sk) {
       if (T == null)
          return null;
       if (sk.equals(T.key))
          return T;
       else if (sk ≺ T.key)
          return find(T.left, sk);
       else
          return find(T.right, sk);
    }

Insert

  • find: do nothing
  • didn’t find: create the key with appropriate link.
  • Never implement like this:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // right code
    static BST insert(BST T, Key ik) {
      if (T == null)
        return new BST(ik);
      if (ik ≺ T.key)
        T.left = insert(T.left, ik);
      else if (ik ≻ T.key)
        T.right = insert(T.right, ik);
      return T;
    }

    //wrong code 
    static BST insert(BST T, Key ik) {
    	if (T.left == null)
    		T.left = new BST(ik);
    	else if (T.right == null)
    		T.right = new BST(ik);
    }

Delete

Just remember the ultimate goal: maintain BST ability!

B Trees (Balanced search trees)

Some basic terms in trees:

  • depth: the number of links between a node and the root.
  • height: the lowest depth of a tree.
  • average depth: average of the total depths in the tree. You calculate this by taking $$∑𝑖=0𝐷𝑑𝑖𝑛𝑖𝑁​N​​∑​i=0​D​​d​i​​n​i​​​​$$ where d​i​​ is depth and n​i​​ is number of nodes at that depth.
    The worst case of BSTs are O(N). (exactly the same case as linked lists!)
    (In most case, the complexity of a algorithm is represented by its worst one.)
    However, it have been proven that when inserting data randomly, the tree are intended to be grow to the better case (~O(logN)).
    But in real world, the data didn’t come in a time usually. They always comes in different times.

Avoiding imbalance

So, a crazy idea is that we never add leaves on our bottom!
![B- tree] (oi-wiki.org/ds/images/b-tree-1.svg) The Problem: if you end with the idea, multiple linked lists will come again!
Solution: set limit to the leaves, and move the elements onto their parents when the limit is reached.
![insert 1](23tree-insert3b.png (283×363) (princeton.edu)](https://algs4.cs.princeton.edu/33balanced/images/23tree-insert3b.png))
![23tree-split](23tree-split.png (210×436) (princeton.edu)](https://algs4.cs.princeton.edu/33balanced/images/23tree-split.png))
But, what if it is no longer a BST when the number have been moved?
split it into left and right part!
If anyone is longer than the certain limit, the number in the middle left or the center will be push up!
we can see that through the operation, the tree have reached perfect balance.
B Trees of L=3 is also called “2-3-4 trees”
To simulate the B Trees, you can look at this website
We can garantee that our trees are bushy!
Overall height: $$log_(L+1)N-log_2N$$
So, the complexity: logN

Red-black Trees

Rotation

disadvantage of the B trees: it is complex to implement

1
2
3
4
5
6
7
8
9
10
public void put(Key key, Value val) { 
	Node x = root; 
	while (x.getTheCorrectChild(key) != null) 
	{ 
		x = x.getTheCorrectChildKey(); 
		if (x.is4Node()) x.split(); 
	} 
	if (x.is2Node()) x.make3Node(key, val); 
	else if (x.is3Node()) x.make4Node(key, val); 
}

tree rotation
![[Tree_rotation.png]]
rotateLeft(G): let x be the right child of G, and make G the new left child of x.
overall rotation
![[Pasted image 20240421103400.png]]

required: Self-balance!
Rotation can balance the tree while preserving tree property.
its code implementation needs one of the nodes are temparily stored.

AVL trees (not required)

平衡因子=右子树高度-左子树高度
if (|平衡因子|>1) rotation!
insert & delete are similar to BSTs.
演示

Red-black trees

how to represent a 2-3 tree as a BST? – rotate!

one possible way: conecting node

but sides are wasted!
![[Pasted image 20240421104317.png]]

another way: to use a “connected edge”

For convenience, the connected edge are signed as red, and others are black.
In code implementation, we can represent the color of edge in the child node.
![[Pasted image 20240421104718.png]]
using the left connected edge as the 2-3 trees are LLRB(left leaning red black tree).
search operations are the same as BSTs!

properties

  1. 和2-3树一一对应！（if the corresponding 2-3 trees are illegal, the LLRB is illegal）
  2. no node have 2 red links.
  3. every path from root to a leaf have the same number of black links.
  4. complexity: O(logN) (if maximum height of the corresponding 2-3 tree is H, the one of LLRB is 2H+1)

construction

first construct a 2-3 tree, and then modify it into LLRB🤣

  • first put in like BST.
  • using Rotation to ensure the corresponding relationship (maintaining balance).
    detailed construction rules:
  1. always use red side when inserting.
  2. insert it into the right side: LeftRotation
  3. produces adjacent red edges after inserting: RightRotation
  4. 2 red edges in one node: flip

implementation

1
2
3
4
5
6
7
8
9
10
11
private Node put(Node h, Key key, Value val) {
	if (h == null) { return new Node(key, val, RED); }
	int cmp = key.compareTo(h.key);
    if (cmp < 0)      { h.left  = put(h.left,  key, val); }
    else if (cmp > 0) { h.right = put(h.right, key, val); }
    else              { h.val   = val;                    }
	if (isRed(h.right) && !isRed(h.left))      { h = rotateLeft(h);  }
	if (isRed(h.left)  &&  isRed(h.left.left)) { h = rotateRight(h); }
	if (isRed(h.left)  &&  isRed(h.right))     { flipColors(h);      } 
	return h;
}