Tree Data Structure
tenji edited this page Jun 16, 2022
·
10 revisions
- 二叉树
- 二叉查找树(二分查找树,二叉搜索树,Binary Search Tree)
- 平衡二叉树(Balanced Binary Tree)
- 平衡二叉查找树
- AVL 树
- 红黑树
- 完全二叉树(Complete Binary Tree)
- 满二叉树(Full Binary Tree)
- 多路查找树
- B 树(B- 树、B_ 树)
- B+ 树
- 2-3 树
- 2-3-4 树
- 堆
- 二叉堆(Binary Heap)
- 小顶堆
- 大顶堆
- 二顶堆(Binomial Heap)
- 优先队列
- 斐波那契堆
- 二叉堆(Binary Heap)
二叉查找树也可叫做二分查找树。它不仅可以查找数据,还可以高效地插入、删除数据。每个节点的 key 值大于左子节点,小于右子节点。
二叉查找树有两个属性:
- 所有节点都比左子树中的节点大
- 所有节点都小于右子树中的节点
通过这两个属性,可以推断出以下结论:
- 二叉查找树最小的节点位于最顶端节点的最左边子树行的末尾
- 二叉查找树的最大节点位于最顶端节点的最右边的子树行的末尾
相对而言,二叉查找树添加元素比删除元素逻辑要简单很多:
- 待插入节点比根节点小,则插入左子树;
- 待插入节点比根节点大,则插入右子树;
public TreeNode insertIntoBST(TreeNode root, int val) {
// 当前节点为空,直接插入当前节点
if (root == null) {
return new TreeNode(val);
}
// 值比根节点小,插入左子树
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
}
// 值比根节点大,插入右子树
if (val > root.val) {
root.right = insertIntoBST(root.right, val);
}
return root;
}
需要分以下几种情况处理:
- 无左子树,无右子树;
- 无左子树,有右子树;
- 有左子树,无右子树;
- 有左子树,有右子树;
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val == key) {
if (root.left == null && root.right == null) {
// 情况一:无左子树,无右子树,直接删除节点即可
return null;
} else if (root.left == null) {
// 情况二:无左子树,有右子树,则右子树上移
return root.right;
} else if (root.right == null) {
// 情况三:有左子树,无右子树,则左子树上移
return root.left;
} else {
// 情况四:有左子树,有右子树,则搜索右子树中最小的节点,并将待删除节点左子树下移
TreeNode curNode = root.right;
while (curNode.left != null) {
curNode = curNode.left;
}
curNode.left = root.left;
return root.right;
}
}
if (root.val > key) {
root.left = deleteNode(root.left, key);
}
if (root.val < key) {
root.right = deleteNode(root.right, key);
}
return root;
}
- 在二叉树的基础上,要求两个子树的高度差不能超过1;
- 每次增删都会通过一次或多次旋转来平衡二叉树;
调整平衡的基本思想:
当在二叉排序树中插入一个节点时,首先检查是否因插入而破坏了平衡,若破坏,则找出其中的最小不平衡二叉树,在保持二叉排序树特性的情况下,调整最小不平衡子树中节点之间的关系,以达到新的平衡。所谓最小不平衡子树,指离插入节点最近且以平衡因子的绝对值大于 1 的节点作为根的子树。
堆是一种非线性结构,可以把堆看作一棵二叉树,也可以看作一个数组,即:堆就是利用完全二叉树的结构来维护的一维数组。
每个结点的值都小于或等于其左右孩子结点的值。
每个结点的值都大于或等于其左右孩子结点的值。
关于优先队列,请参考:PriorityQueue 源码解析