資料結構-樹

一、回顧基本概念

樹

每個結點有零或多個子節點，沒有父結點的結點後稱為根結點，除了根結點每個子結點可以分為多個不相交的子樹。

結點層次：根結點為第一層，其子結點為第二層，依次遞推

結點深度：從根結點向下累加

結點高度：從葉結點向上累加

樹的高度：為結點最大層數，圖中為5

森林：互不相交的樹的集合（把根節點去掉就是森林了）

二叉樹

每個結點最多有兩棵子樹，且結點有左右之分。二叉樹的左子樹和右子樹也是二叉樹。根據二叉樹的狀态又有幾個特殊的子樹。

斜二叉樹

這也是後續要盡量避免的情形，失去了樹的意義。

滿二叉樹

高度

，則結點為

2h-1

的樹為滿二叉樹，也就是每一層都是滿的。

完全二叉樹

不一定滿，隻有最後一層可能不滿，且不會有間隔。

二叉查找樹

别名：二叉搜尋樹、二叉排序樹、BST

一個結點A，左邊結點要麼為空，要麼小于結點A；右邊結點要麼為空，要麼大于結點A。沒有鍵值相等的結點。

上圖就是一個二叉查找樹。

平衡二叉樹

特殊的二叉搜尋樹，一個結點左右子樹高度差不超過1。上圖其實還是一個平衡二叉樹。

二、二叉樹的周遊

存儲方式

二叉樹的存儲有如下方法：

數組：适合完全二叉樹，普通的二叉樹（可能是斜二叉樹）空間浪費大。

父結點指針、子結點指針。本文選用子結點指針。

class Node {
int data;
Node left;
Node right;
}

前、中、後序周遊

先序：考察到一個節點後，即刻輸出該節點的值，并繼續周遊其左右子樹。(根左右)

中序：考察到一個節點後，将其暫存，周遊完左子樹後，再輸出該節點的值，然後周遊右子樹。(左根右)

後序：考察到一個節點後，将其暫存，周遊完左右子樹後，再輸出該節點的值。(左右根)

以二叉查找樹為例。BST首先應該有根結點和插入方法。二叉查找樹插入：小于目前結點插入左邊，否則右邊。

public class BST {
// 根結點
Node root = null;
// 插入二叉搜尋樹
public boolean insert(int data) {
if(root==null) {
root = new Node(data);
return true;
        }
Node n = root;
while (true) {
if (data<n.data) {="" if(n.left="=null)" n.left="new" node(data);="" return="" true;="" }="" else="" n="n.left;" if(data="=" n.data)="" bst沒有鍵值相等的="" false;="" if(n.right="=null)" n.right="new" ```="" 周遊接口，選擇前中後序周遊。="" ```java="" public="" void="" traverse(string="" method)="" switch="" (method)="" case="" "preorder":="" preordertraverse(root);="" break;="" "postorder":="" postordertraverse(root);="" "inorder":="" inordertraverse(root);="" default:="" system.out.println("preorder、postorder、inorder，輸入無效，按preorder非遞歸周遊");="" preordertraverse();="" 測試插入：="" static="" main(string[]="" args)="" bst="" bst();="" bst.insert(3);="" bst.insert(6);="" bst.insert(9);="" bst.insert(2);="" bst.insert(1);="" bst.insert(10);="" bst.insert(7);="" bst.traverse("inorder");="" 1="" 2="" 3="" 6="" 7="" 9="" 10="" 如圖：="" ![image-20211020113408623](https:="" gitee.com="" hqinglau="" img="" raw="" master="" 20211020113408.png)="" ####="" 前序周遊="" 考察到一個節點後，即刻輸出該節點的值，并繼續周遊其左右子樹。(根左右)="" 遞歸方法比較明了，如下：="" private="" preordertraverse(node="" n)="" if(n="=null)" return;="" system.out.println(n.data);="" preordertraverse(n.left);="" preordertraverse(n.right);="" 非遞歸方法：輸出一個結點的值後，要周遊其左子樹，完了之後還要回來周遊它的右子樹，是以應該有個棧存放周遊過的結點。="" 非遞歸方法：="" preordertraverse()="" if(root="=null)" stack<node=""> stack = new Stack<>();
System.out.println(root.data); // 輸出
stack.push(root); // 壓棧，周遊左子樹，完了彈出棧，周遊右子樹
Node cur = root;
while(true) {
if(cur.left!=null) {
System.out.println(cur.left.data);
stack.push(cur.left);
cur = cur.left;
        }
else {
do {
if(stack.empty()) {
return;
                }
cur = stack.pop().right;
            } while (cur==null);
System.out.println(cur.data);
stack.push(cur);
        }
    }
}

如圖：

中序周遊

考察到一個節點後，将其暫存，周遊完左子樹後，再輸出該節點的值，然後周遊右子樹。(左根右)

遞歸方法：

private void inOrderTraverse(Node n) {
if(n==null) {
return;
    }
inOrderTraverse(n.left);
System.out.println(n.data);
inOrderTraverse(n.right);
}

非遞歸方法：

private void inOrderTraverse() {
if(root==null) {
return;
    }
Stack<node> stack = new Stack<>();
stack.push(root); // 壓棧，周遊左子樹，列印目前結點，完了彈出棧，周遊右子樹
Node cur = root;
while(true) {
if(cur.left!=null) {
stack.push(cur.left);
cur = cur.left;
        }
else {
do {
if(stack.empty()) {
return;
                }
Node n = stack.pop();
System.out.println(n.data);
cur = n.right;
            } while (cur==null);
stack.push(cur);
        }
    }
}

後序周遊

private void postOrderTraverse(Node n) {
if(n==null) {
return;
    }
postOrderTraverse(n.left);
postOrderTraverse(n.right);
System.out.println(n.data);
}

層序周遊

用隊列存一層的結點。讀的時候從頭依次讀取，左右子結點依次存取。

public void levelOrderTraverse() {
if(root==null) {
return;
    }
Queue<node> stack = new LinkedList<>();
stack.add(root); // 壓棧，周遊左子樹，完了彈出棧，周遊右子樹

int lastLayer = 1;
int n = 0;
while(!stack.isEmpty()) {
for(int i=0;i<lastlayer;i++) {="" node="" system.out.println(node.data);="" if(node.left!="null)" n++;="" stack.add(node.left);="" }="" if(node.right!="null)" stack.add(node.right);="" lastlayer="n;" n="0;" ```="" ##="" 三、二叉搜尋樹="" ###="" 二叉搜尋樹="" ####="" 插入="" 見第二節的存儲方式部分。="" 删除="" 如要删除6結點="" <img="" src="https://gitee.com/hqinglau/img/raw/master/img/20211020160635.png" alt="image-20211020160635608" style="zoom:80%;">

按照遞歸思路比較容易，找到了就處理，找不到就配置設定給子函數處理。找到之後，如果是左樹為空或右樹為空，直接挂上，都不為空需要找到右子樹的最小結點，指派給根結點，然後删除最小結點。

```java
private Node remove(Node r, int data) {
if(r==null) return null;
if(data>r.data) {
r.right = remove(r.right,data);
    } else if(data<r.data) {="" r.left="remove(r.left,data);" }="" else="" root="" 的data="=" data="" if(r.left="=null)" r="r.right;" if="" (r.right="=" null)="" 把右子樹最小結點提到根結點，然後删除這個最小結點="" node="" minnode="r.right;" while(minnode.left!="null)" r.data="minNode.data;" r.right="remove(r.right,minNode.data);" return="" r;="" ```="" ####="" 查找="" 小往左子樹找，大往右子樹找。最大查找時間為樹的高度。="" ###="" 平衡二叉樹="" 普通二叉搜尋樹問題：極端情況會退化成線性。="" ![image-20211020133555445](https:="" gitee.com="" hqinglau="" img="" raw="" master="" 20211020133555.png)="" 平衡二叉樹在修改時借助**旋轉操作**，左右子樹高度差不超過1，避免了這一問題。如圖所示，要在該樹種插入9，會破壞平衡：="" ![image-20211020163051980](https:="" 20211020163052.png)="" 旋轉="" ![image-20211020164728884](https:="" 20211020164728.png)="" 左旋：以**右子樹結點為軸**，動左邊的x結點，旋轉過程接收y的左子樹作為右結點。右旋同理。="" 上圖中，左旋之後，a的深度+1，c的深度-1。是以：**可以通過合适的左旋和右旋操作，調整二叉樹的深度。**="" ll插入="" 對的左兒子的左子樹進行一次插入（左左）：根結點右旋="" ![image-20211020165340908](https:="" 20211020165340.png)="" lr插入="" lr問題，對根結點左兒子右子樹的插入問題：="" <img="" src="https://gitee.com/hqinglau/img/raw/master/img/20211020172401.png" alt="image-20211020172401514" style="zoom:80%;">

#### RR插入

LL插入的鏡像問題，右邊可能過深，對整體來一次左旋。

#### RL插入

LR問題的鏡像問題，先對右子樹右旋，再整體左旋。

#### 代碼實作

按正常插入後調整。

```java
public class AVL {
Node root;

public int getHeight(Node r) {
if (r == null) return 0;
return Math.max(getHeight(r.left), getHeight(r.right)) + 1;
    }

public Node rotateLeft(Node r) {
Node t = r.right;
r.right = t.left;
t.left = r;
return t;
    }

public Node rotateRight(Node r) {
Node t = r.left;
r.left = t.right;
t.right = r;
return t;
    }

public void insert(int data) {
root = insert(root,data);
Node left = root.left;
Node right = root.right;
if(left!=null) {
if(getHeight(left.left)-getHeight(left.right)>=2) {
root.left =  rotateRight(left);
            } else if(getHeight(left.right)-getHeight(left.left)>=2) {
root.left = rotateLeft(left);
            }
        }
if(right!=null) {
if(getHeight(right.left)-getHeight(right.right)>=2) {
root.right=rotateRight(right);
            } else if(getHeight(right.right)-getHeight(right.left)>=2) {
root.right=rotateLeft(right);
            }
        }
if(getHeight(left)-getHeight(right)>=2) {
root=rotateRight(root);
        }  else if(getHeight(right)-getHeight(left)>=2) {
root=rotateLeft(root);
        }
    }

public Node insert(Node r, int data) {
if (r == null) {
return new Node(data);
        }
if (data > r.data) {
r.right = insert(r.right, data);
        } else if (data < r.data) {
r.left = insert(r.left, data);
        }
return r;
    }
}

四、紅黑樹簡述

有了平衡二叉樹，為何還要紅黑樹？

AVL插入時，幾乎都需要旋轉操作維持平衡。紅黑樹犧牲嚴格的平衡，換取插入/删除時的性能。

紅黑樹規則

規則一：結點非黑即紅

規則二：根結點為黑色

規則三：葉結點的子結點（null）為黑色

規則四：紅色結點的子結點為黑色

規則五：每個結點到null結點的所有路徑，包含相同數目的黑色結點（相同的黑色高度）

如上圖中

到

nil

結點，黑色結點數都是2。

這5條限制保證了：從根結點到葉子結點的最長路徑，不會超過最短路徑的兩倍。由規則5具有相同的黑色高度，最短路徑就全是黑色，最長路徑黑紅相間，而紅色子結點為黑色，即不大于最短路徑的兩倍。

三種變換

插入後不破壞規則，不需要旋轉變色，破壞規則需要調整。

變色

插入結點一般選擇紅色，因為黑色由于規則五：相同黑色高度問題，很難調整。紅紅相連問題可通過變色和旋轉解決。

左旋

和之前的平衡二叉樹左旋、右旋是一樣的。

資料結構-樹

一、回顧基本概念

樹

二叉樹

斜二叉樹

滿二叉樹

完全二叉樹

二叉查找樹

平衡二叉樹

二、二叉樹的周遊

存儲方式

前、中、後序周遊

中序周遊

後序周遊

層序周遊

四、紅黑樹簡述

紅黑樹規則

三種變換

變色

左旋

右旋

繼續閱讀

nginx location中斜線的位置的重要性

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method