一、栈
先进后出
二、队列
先进先出
三、数组
查询快，增加修改慢
四、链表
查询慢，增加修改慢
五、二叉树
节点：
查找二叉树
二叉查找树的特点
-
二叉查找树,又称二叉排序树或者二叉搜索树
-
每一个节点上最多有两个子节点
-
左子树上所有节点的值都小于根节点的值
-
右子树上所有节点的值都大于根节点的值
二叉查找树添加节点规则
-
小的存左边
-
大的存右边
-
一样的不存
数据结构(二叉树)遍历方式
- 前序遍历:当前节点，左子节点，右子结点
- 中序遍历:左子节点，当前节点，右子结点
- 后序遍历:左子节点，右子结点，当前节点
- 层序遍历:一层一层的去遍历
平衡二叉树
特点
-
二叉树左右两个子树的高度差不超过1
-
任意节点的左右两个子树都是一颗平衡二叉树
平衡二叉树旋转
-
旋转触发时机
-
当添加一个节点之后,该树不再是一颗平衡二叉树
-
-
左旋
-
确定支点:从添加的节点开始，不断的往父节点找不平衡的节点
以不平衡的点作为支点
将根节点的右侧往左拉
原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点
-
右旋
-
确定支点:从添加的节点开始，不断的往父节点找不平衡的节点
以不平衡的点作为支点
就是将根节点的左侧往右拉
原先的左子节点变成新的父节点，并把多余的右子节点出让，给已经降级的根节点当左子节点
平衡二叉树旋转的四种情况
左左
-
左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡
-
如何旋转: 直接对整体进行右旋即可
左右
-
左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡
-
如何旋转: 先在左子树对应的节点位置进行左旋,再对整体进行右旋
右右
-
右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡
-
如何旋转: 直接对整体进行左旋即可
右左
-
右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡
-
如何旋转: 先在右子树对应的节点位置进行右旋,再对整体进行左旋
红黑树
红黑树的特点
红黑树的增删改查性能都很好
-
平衡二叉B树
-
每一个节点可以是红或者黑
-
红黑树不是高度平衡的,它的平衡是通过"自己的红黑规则"进行实现的
节点
红黑规则
- 每一个节点是红色的，或者是黑色的
- 根节点必须是黑色
- 叶节点是黑色的
- 两个红色节点不能相连
- 任意节点到所有后代叶节点的简单路径上，黑色节点数量相同;
红黑树结构图
红黑树添加节点的默认颜色
-
添加节点时,默认为红色,效率高
红黑树添加节点后如何保持红黑规则
-
根节点位置
-
直接变为黑色
-
-
非根节点位置
-
父节点为黑色
-
不需要任何操作,默认红色即可
-
-
父节点为红色
-
叔叔节点为红色
-
将"父节点"设为黑色,将"叔叔节点"设为黑色
-
将"祖父节点"设为红色
-
如果"祖父节点"为根节点,则将根节点再次变成黑色
-
-
叔叔节点为黑色
-
将"父节点"设为黑色
-
将"祖父节点"设为红色
-
以"祖父节点"为支点进行旋转
-
-
-
实现代码
public class RBTree {
class Node {
int val, color;
Node left, right;
}
// 使用NIL节点来充当叶节点
Node NIL;
Node root;
public RBTree() {
NIL = new Node();
NIL.val = -1;
NIL.color = 1;
NIL.left = NIL.right = NIL;
root = NIL;
}
// 创建节点
private Node getNewNode(int val) {
Node p = new Node();
p.val = val;
p.color = 0;
p.left = p.right = NIL;
return p;
}
//判断有没有红色孩子
private boolean has_red_child(Node tree) {
return tree.left.color == 0 || tree.right.color == 0;
}
//左旋
private Node left_rotate(Node tree) {
Node temp = tree.right;
tree.right = temp.left;
temp.left = tree;
return temp;
}
//右旋
private Node right_rotate(Node tree) {
Node temp = tree.left;
tree.left = temp.right;
temp.right = tree;
return temp;
}
//寻找前驱
private Node preNode(Node tree) {
Node p = tree.left;
while (p.right != null) {
p = p.right;
}
return p;
}
//删除
public void erase(int val) {
root = erase(root, val);
}
private Node erase(Node tree, int val) {
tree = __erase(tree, val);
tree.color = 1;
return tree;
}
private Node __erase(Node tree, int val) {
if (tree == NIL) return tree;
if (val < tree.val) {
tree.left = __erase(tree.left, val);
} else if (val > tree.val) {
tree.right = __erase(tree.right, val);
} else {
if (tree.left == NIL || tree.right == NIL) {
Node temp = tree.left == NIL ? tree.right : tree.left;
temp.color += tree.color;
tree = temp;
return tree;
} else {
Node temp = preNode(tree);
tree.val = temp.val;
tree.left = __erase(tree.left, temp.val);
}
}
return erase_maintion(tree);
}
//删除调整
private Node erase_maintion(Node tree) {
if (tree.left.color != 2 && tree.right.color != 2) return tree;
// 兄弟为红，旋转树，新根节点转为黑，原根节点转为红
if (has_red_child(tree)) {
int flag = 0;
tree.color = 0;
if (tree.left.color == 0) {
tree = right_rotate(tree);
flag = 1;
} else {
tree = left_rotate(tree);
}
tree.color = 1;
if (flag == 1) tree.right = erase_maintion(tree.right);
else tree.left = erase_maintion(tree.left);
return tree;
}
// 兄弟为黑色并且没有红色子节点,子节点减黑，根节点加黑
if (tree.left.color == 1 && !has_red_child(tree.left)
|| tree.right.color == 1 && !has_red_child(tree.right)) {
tree.color += 1;
tree.left.color -= 1;
tree.right.color -= 1;
return tree;
}
// 兄弟节点为黑并且有红色子节点
// |-- 左子树为黑色
// |-- 左子树的右子树为红色且左子树节点为黑 LR
// |-- 子树小左旋，新节点转黑，原节点转红,进入LL形态
// |-- 左子树的左子树为红色 LL
// |-- 整树右旋，新节点改为原根节点的颜色，原根节点已经新叔叔节点转为黑色
// |-- 右子树为黑色
// |-- 右子树的左子树为红色且右子树节点为黑 RL
// |-- 子树小右旋，新节点转黑，原节点转红,进入RR形态
// |-- 右子树的右子树为红色 RR
// |-- 整树左旋，新节点改为原根节点的颜色，原根节点已经新叔叔节点转为黑色
if (tree.left.color == 1) {
tree.right.color = 1;
if (tree.left.left.color != 0) {
tree.left.color = 0;
tree.left = left_rotate(tree.left);
tree.left.color = 1;
}
tree.left.color = tree.color;
tree = right_rotate(tree);
} else {
tree.left.color = 1;
if (tree.right.right.color != 0) {
tree.right.color = 0;
tree.right = right_rotate(tree.right);
tree.right.color = 1;
}
tree.right.color = tree.color;
tree = left_rotate(tree);
}
tree.left.color = 1;
tree.right.color = 1;
return tree;
}
//添加
public void insert(int val) {
root = insert(root, val);
}
private Node insert(Node tree, int val) {
tree = __insert(tree, val);
tree.color = 1;
return tree;
}
private Node __insert(Node tree, int val) {
if (tree == NIL) {
return getNewNode(val);
}
if (val < tree.val) {
tree.left = __insert(tree.left, val);
} else if (val > tree.val) {
tree.right = __insert(tree.right, val);
}
return insert_maintain(tree);
}
//添加调整
private Node insert_maintain(Node tree) {
if (!has_red_child(tree)) return tree;
//节点双红
if (tree.left.color == 0 && tree.right.color == 0) {
if (!has_red_child(tree.left) && !has_red_child(tree.right)) return tree;
tree.color = 0;
tree.left.color = tree.right.color = 1;
return tree;
}
if (tree.left.color == 0 && !has_red_child(tree.left)) return tree;
if (tree.right.color == 0 && !has_red_child(tree.right)) return tree;
// 左子树失衡
if (tree.left.color == 0) {
if (tree.left.right.color == 0) {
tree.left = left_rotate(tree.left);
}
tree = right_rotate(tree);
} else {
if (tree.right.left.color == 0) {
tree.right = right_rotate(tree.right);
}
tree = left_rotate(tree);
}
tree.color = 0;
tree.left.color = tree.right.color = 1;
return tree;
}
//打印输出
public void preorder() {
preorder(root, root.val, 0);
}
private void preorder(Node tree, int val, int flag) {
if (tree == NIL) return;
if (flag == 0) {
System.out.printf("%d is root, color is %s\n", val, tree.color == 0 ? "red" : "black");
} else {
System.out.printf("%d is %d's %s child, color is %s\n"
, tree.val, val, flag == 1 ? "right" : "left", tree.color == 0 ? "red" : "black");
}
preorder(tree.left, tree.val, -1);
preorder(tree.right, tree.val, 1);
}
}