二叉樹
基本概念
常見術語
-
結點： 包含一個資料元素及若干指向子樹的分支
-
結點的度：含有孩子結點的個數
-
結點的層次：由根結點開始，根結點層次為 0
-
樹的深度：由根結點開始，根結點深度為 0
-
樹的高度：由葉子結點向根結點，取最大值，葉子結點高度為 0
-
葉子結點（終端結點）：沒有孩子結點
-
分支結點（非終端結點）：有孩子結點
-
根結點：沒有父親結點
-
子樹：一個分支結點及其后輩組成子樹
-
父親結點、孩子結點、兄弟結點
-
前輩、后輩
鏈表、樹和圖
鏈表是特殊的樹，樹是特殊的圖
- 單鏈表結點有兩個 next 指標，稱為樹
- 樹的結點指向了其前輩結點，稱為圖
二叉樹
一個樹滿足：
- 每個結點的孩子結點數不大于 2
- 每個結點的孩子次序不能任意顛倒
則稱為二叉樹，其左邊孩子結點稱為左孩子，右邊孩子結點稱為右孩子
數學性質
- 高度為 h（>=0）的二叉樹，至少有 h+1 個結點，至多有 \(2^{h+1}-1\) 個結點
- 含有 n（n>=1）個結點的二叉樹，高度至多為 n-1；至少為 \(logn\)
滿二叉樹
除了葉結點外每一個結點都有左右子葉且葉結點都處在最底層的二叉樹，即每一層結點樹都達到最大
完全二叉樹
- 除了最下面一層，其他層結點數達到最大，并且最下面一層的結點都在該層最左邊的二叉樹
- 在滿叉樹的基礎上，在最底層從右往左刪去若干結點，得到的都是完全二叉樹
平衡二叉樹
-
樹的左右子樹的高度差不超過1的數，空樹也是平衡二叉樹的一種
-
具有下列性質的二叉樹
- 它的左子樹和右子樹都是平衡二叉樹
- 左子樹和右子樹的高度之差不超過 1
二叉樹操作
創建二叉樹
public class TreeNode {
TreeNode left;
TreeNode right;
Object value;
}
遍歷二叉樹
前序、中序、后序遍歷每個結點最多被訪問兩次，時間復雜度為 O(n)
層序遍歷每個結點被訪問一次，時間復雜度為 O(n)
-
前序遍歷
public List<Integer> preOrder() { List<Integer> values = new ArrayList<>(); values.add((int) value); if (left != null) values.addAll(left.preOrder()); if (right != null) values.addAll(right.preOrder()); return values; } -
中序
public List<Integer> inOrder() { List<Integer> values = new ArrayList<>(); if (left != null) values.addAll(left.inOrder()); values.add((int) value); if (right != null) values.addAll(right.inOrder()); return values; } -
后序遍歷
public List<Integer> postOrder() { List<Integer> values = new ArrayList<>(); if (left != null) values.addAll(left.postOrder()); if (right != null) values.addAll(right.postOrder()); values.add((int) value); return values; } -
層序遍歷
public List<TreeNode> layerOrder() { List<TreeNode> values = new ArrayList<>(); values.add(this); for (int i = 0; i < values.size(); i++) { TreeNode node = values.get(i); if (node.left != null) values.add(node.left); if (node.right != null) values.add(node.right); } return values; }
結點數目
public int nodeNum() {
int count = 0;
if (value != null) count = 1;
if (left != null) {
count += left.nodeNum();
}
if (right != null) {
count += right.nodeNum();
}
return count;
}
輸出葉結點
public List leafNode() {// 前序
List<Integer> values = new ArrayList<>();
if (left == null && right == null) values.add((int) value);
if (left != null) values.addAll(left.leafNode());
if (right != null) values.addAll(right.leafNode());
return values;
}
葉結點數目
public int leafNodeNum() {// 前序
int count = 0;
if (left == null && right == null) count++;
if (left != null) count += left.leafNodeNum();
if (right != null) count += right.leafNodeNum();
return count;
}
輸出高度
public int getHeight() {
int l = 0, r = 0;
if (left != null) l = left.getHeight();// 左子樹高度
if (right != null) r = right.getHeight();// 右子樹高度
return (Math.max(l, r));
}
列印二叉樹
-
橫向列印
public void printTree(int layer) { if (right != null) right.printTree(layer + 1); for (int i = 0; i < layer; i++) System.out.print("-|-"); System.out.println(value); if (left != null) left.printTree(layer + 1); }
二叉搜索樹
也叫二叉排序樹、二叉查找樹
性質
-
二叉搜索樹，要么是一顆空樹，要么具有以下性質
- 若任意結點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值
- 若任意結點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值
- 任意結點的左、右子樹也分別為二叉查找樹
- 沒有鍵值相等的結點
-
中序遍歷得到有序數列
創建
public class TreeNode {
TreeNode left;
TreeNode right;
Object value;// 默認 null
}
驗證
判斷二叉樹是不是二叉搜索樹
-
中序遍歷，判斷是否得到有序數列
public boolean isValid() { List<Integer> list = inOrder();// 中序遍歷結果 for (int i = 0; i < list.size() - 1; i++) { if (list.get(i) >= list.get(i + 1)) return false; } return true; } -
遞回判斷大小關系是否合理
public boolean isValid() { boolean l = true, r = true; if (left != null && (int) value <= (int) left.value) return false; if (right != null && (int) value >= (int) right.value) return false; if (right != null) r = right.isValid(); if (left != null) l = left.isValid(); return r && l; }
插入結點
public void add(Object o) {
if (value =https://www.cnblogs.com/pgjett/p/= null) value = o;
else if ((int) value - (int) o > 0) {// 小的放左邊
left = (null == left) ? new TreeNode() : left;
left.add(o);// 遞回
} else if ((int) value - (int) o < 0) {// 大的放右邊
right = (null == right) ? new TreeNode() : right;
right.add(o);// 遞回
}
}
查找結點
-
遞回方式
public TreeNode find(int i) { if (value =https://www.cnblogs.com/pgjett/p/= null) return null; if ((int) value == i) return this; if (left != null && i < (int) value) return left.find(i); if (right != null && i > (int) value) return right.find(i); return null; } -
回圈方式
public TreeNode findByLoop(int i) { TreeNode node = this; while (node != null) { if (i > (int) node.value) node = node.right; else if (i < (int) node.value) node = node.left; else return node; } return null; }
洗掉結點
- 要洗掉的結點沒有子結點，則直接將父親結點指向該結點的指標置為 null
- 要洗掉的結點有一個子結點，則直接將父親結點的指標指向其子結點
- 要洗掉的結點有兩個子結點，找到該結點右子樹最小結點，替換該結點，并洗掉該最小結點
public void delete(int i) {
TreeNode pre = null;// 父親結點
TreeNode node = this;
while (node != null && (int) node.value != i) {
pre = node;
if (i > (int) node.value) node = node.right;
else if (i < (int) node.value) node = node.left;
}
if (node == null) return;// 沒找到要洗掉的結點
if (pre != null) {
// 要洗掉的結點無子結點
if (node.right == null && node.left == null) {
if (pre.left == node) pre.left = null;
else pre.right = null;
return;
}
// 要洗掉的結點有一個子結點
if (node.right == null && node.left != null) {
if (pre.left == node) pre.left = node.left;
else pre.right = node.left;
return;
} else if (node.right != null && node.left == null) {
if (pre.left == node) pre.left = node.right;
else pre.right = node.right;
return;
}
// 要洗掉的結點有兩個或以上的結點
if (node.right != null && node.left != null) {
TreeNode rightMin = node.right;
while (rightMin.left != null) rightMin = rightMin.left;
delete((int) rightMin.value);
if (pre.left == node) pre.left = rightMin;
else pre.right = rightMin;
rightMin.left = node.left;
rightMin.right = node.right;
return;
}
} else {
// 要洗掉的是根節點
TreeNode rightMin = node.right;
while (rightMin.left != null) rightMin = rightMin.left;
delete((int) rightMin.value);
this.value=https://www.cnblogs.com/pgjett/p/rightMin.value;
return;
}
}
性能分析
- 二叉樹操作時間復雜度與高度成正比，平衡二叉樹的高度近似 \(long_2n\)
- 極度不平衡的二叉搜索樹，退化成鏈表，查找復雜度為 \(O(n)\)
- 平衡二叉搜索樹查找、插入、洗掉時間復雜度為 \(O(logn)\)
紅黑樹
概念
- 紅黑樹，也叫 Red-Black Tree，R-B Tree
- 并不完全符合平衡二叉樹定義，是一種不嚴格的平衡二叉樹
- 要滿足以下要求
- 根節點是黑色的，每個葉子節點都是黑色的空節點（NIL），也就是說，葉子節點不存盤資料
- 任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的
- 每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點
性能分析
平衡二叉樹的初衷是為了解決二叉搜索樹動態更新導致的性能退化
紅黑樹是一種近似平衡的二叉樹，可以讓性能退化不會太嚴重
-
紅黑樹的高度
graph TB root((黑))-->b11((黑)) root((黑))-->b12((黑)) b11((黑))-->r21((紅)) b11((黑))-->r22((紅)) b12((黑))-->b23((黑)) b12((黑))-->b24((黑)) r21((紅))-->b31((黑)) r21((紅))-->b32((黑)) r22((紅))-->b33((黑)) r22((紅))-->b34((黑)) Root((黑))-->B11((黑)) Root((黑))-->B12((黑)) B11((黑))-->B21((黑)) B11((黑))-->B22((黑)) B11((黑))-->B23((黑)) B11((黑))-->B24((黑)) B12((黑))-->B25((黑)) B12((黑))-->B26((黑))- 如果將紅黑樹中所有紅結點去掉，其子結點淪為其父節點的孩子
- 二叉樹變成四叉樹，同等結點個數，四叉樹高度比二叉樹小，也就是小于 \(log_2n\)
- 當把紅色結點添加回去，由于規定紅色結點不能相鄰，有一個紅結點就要有一個黑結點將它隔開，紅黑樹中包含最多黑結點的路徑長度不超過 \(log_2n\)，因此加入紅結點后，高度不超過 \(2log_2n\)
紅黑樹高度近似為 \(2long_2n\)
-
紅黑樹的高度只比高度平衡的 AVL 樹的高度 \(log_2n\) 大了一倍
在性能上，下降得并不多，實際上紅黑樹的性能更好
查找、插入、洗掉時間復雜度都為 \(O(logn)\)， 很多編程語言中的 Map 型別都是通過紅黑樹來實作的
AVL 樹是一種高度平衡的二叉樹，查找效率非常高，但是為了維持高度平衡,每次插入、洗掉都要做調整，比較耗時，對于有頻繁的插入、洗掉操作的資料集合，不適合使用 AVL 樹
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/88243.html
標籤：其他