lec4-Specific Trees
1. binary search trees 二叉搜索树
1.1. 二叉搜索树的定义
- 对于任意一个节点，左子树上的所有 element 都小于根节点的 element，右子树节点都大于
- element 相同的节点是不存在的
- 这样来看，中序遍历就是有顺序的遍历
1.2. （indexed BST）带索引的二叉搜索树
int leftSize; // 左子树的节点数加一
- 这是添加的关键成员变量
- 想想怎么用递归方法找到 kth 的数字（左子树的所有节点就是所有小于根的节点）
1.3. BST的增删查
1.3.1. find
private BinaryNode find(Comparable x, BinaryNode t){
if(t == null) return null;
if(x.compareTo(t.element) < 0)
return find(x, t.left);
if(x.compareTo(t.element) > 0)
return find(x, t.right);
else // x == t.element
return t;
}
- 这里就是简单的递归思想，也是BST几乎所有算法都会用到的套路
BinaryNode findMin() // 可以递归做，也可以循环做
BinaryNode findMax()
1.3.2. insert
private BinaryNode insert(Comparable x, BinaryNode t){
if(t == null) return new BinaryNode(x, null, null);
else if(x.compareTo(t.element) < 0){
t.left = insert(x, t.left); //这里就是认为左子树做好了处理，可以直接使用t.left
}else if(x.compareTo(t.element) > 0){
t.right = insert(x, t.right);
}else ;// 这里表示已经重复，可以报错等等，不需要处理
return t; // 已经做好处理了，就可以返回了
}
1.3.3. remove
- 这里要分三种情况进行讨论
- 删除叶子节点
直接删除 - 删除有一条分支节点
直接删除，但是要连接好上下 - 删除有两条分支节点
先取出前驱或者后继来取代这个节点，然后在对应的子树上删除前驱或者后继
也就是要(findMin(),findMax())
- 删除叶子节点
private BinaryNode remove(Comparable x, BinaryNode t){
if(t == null) return t;
else if(x.compareTo(t.element) < 0)
t.left = remove(x, t.left);
else if(x.compareTo(t.element) > 0)
t.right = remove(x, t.right);
else{ // 只有找到了这个节点，才可以进入下一步三种情况的讨论！！！
if(t.left != null && t.right != null){ // 第一种情况，两个分支
t.element = findMin(t.right).element; //找出后继
t.right = remove(t.element, t.right);
}else if(t.left != null){
t = t.left;
}else if(t.right != null){
t = t.right;
}else{ // 直接删掉
t = null;
}
}
return t;
}
查询，插入，删除需要的时间复杂度都是 O（h），为了增加层数，我们有了AVL树
2. AVL Tree（平衡二叉搜索树）
2.1. AVL树的定义
- AVL树是一棵二叉搜索树
- 每一个节点都满足： 左右子树高度差不超过1
- 可以维护树高或者是 balance 来看
- 可以证明，树高与节点数成对数关系
2.2. AVL树的增删查
2.2.1. 查询
- 查询与BST完全一致
2.2.2. 插入
- 左外侧太高的时候：
对根节点，右旋转 - 左内侧太高的时候：
对根节点，先左旋转（这样就变成了左外侧的情况），后右旋转
private AVLNode insert(Comparable x, AVLNode t){
if(t == null)
t = new AVLNode(x, null, null);
else if(x.compareTo(t.element) < 0){
t.left = insert(x, t.left); // 注意！这里表示的是，左侧已经成功插入了平衡的子树
if(height(t.left) - height(t.right) == 2){
if(x.compareTo(t.left.element) < 0){ // 我想要插入的数字，成功插到了左子树的外侧？内侧？
t = rotateWithLeftChild(t); // 注意：这里的意思是，左外侧要做的操作，实际上也是右旋转
// t = rightRotate(t);
}else
t = doubleWithLeftChild(t); // 双旋转
}
}else if(x.compareTo(t.element) > 0){
if(height(t.right) - height(t.left) == 2){
if(x.compareTo(t.right.element) > 0){
t = rotateWithRightChild(t);
}else{
t = doubleWithRightChild(t);
}
}
}else
;
t.height = max(height(t.left), height(t.right)) + 1;
return t;
}
private static AVLNode rotateWithLeftChild(AVLNode k2){ // 注意，这里是右旋转！ 也就是原来的根会往右下角跑
AVLNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max(height(k2.left), height(k2.right)) + 1;
k1.height = max(height(k1.left), height(k1.right)) + 1;
return k1; // 返回的是树根！树根一定会变化！
}
private static AVLNode doubleWithLeftChild(AVLNode k3){
k3.left = rotateWithRightChild(k3.left);
k3 = rotateWithLeftChild(k3);
return k3;
// 一个记忆的技巧：后面的一定是右旋转，因为前面一步会变成左外侧情况！
}
2.2.3. 删除
- 课件中只提到需要递归进行平衡维护，但是没有给出代码
- 方法上大体与二叉搜索树一致，但是需要
2.3. 算法复杂度分析
- 高度为0的AVL树，节点数最少是1；
- 高度为1的AVL树，节点数最少是2；
- 高度为2的AVL树，节点数最少是4；
- 递推公式：
N
h
=
N
h
−
1
+
N
h
−
2
+
1
N_h = N_{h-1} + N_{h-2} + 1
Nh=Nh−1+Nh−2+1
这是比较直观的，根对应1， 还需要两个尽可能小的AVL树作为左右子树，而且这两棵子树的高度差不超过1 - N h + 1 N_h + 1 Nh+1满足斐波那契数列，我们可以知道，节点数与层数成对数关系；
3. m阶搜索树 - 无代码要求
4. B树（平衡的m阶搜索树）- 无代码要求
- 插入看上溢出，删除看下溢出；
4.1. 插入
4.2. 删除
- 关键是要认准节点的个数
- 根节点：最少2个分支，1个key
- 其他节点：最少
(
n
/
2
)
上取整
(n/2)上取整
(n/2)上取整 个分支，但是key数目要比分支数少一个
5阶B树：最少3个分支，2个元素
- 尝试向左右兄弟去借，如果借的到，那么就是
父亲下来，兄弟上去 - 两边都借不到，那就合并：
父亲下来在中间，兄弟合并为一个节点 - 同时这件事情，需要递归向上去做