什麼是平衡二叉查找樹

#頭條創作挑戰賽#

平衡樹

平衡樹的定義

  平衡二叉搜尋樹（英語：Balanced Binary Tree）是一種結構平衡的二叉搜尋樹，即葉節點高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

• 先畫出一棵樹備用 ，後面都用這棵樹進行分析。
• 先給出結論，這不是一顆平衡樹根據定義，每一個葉節點的高度差的絕對值不超過1，左右子樹均滿足這個條件j 高度 1，j 左節點 高度0，右節點 高度0，左右高度相差0，j 節點是平衡的h 高度2，h 左節點 j 高度1，右節點 高度0，左右高度相差1，h 節點是平衡的g 高度1，g 左節點 高度0，右節點 高度0，左右高度相差0，g 節點是平衡的e 高度3，e 左節點 g 高度1，右節點 h 高度2，左右高度相差1，e 節點是平衡的b 高度4，b 左節點 e 高度3，右節點 高度0，左右高度相差3，b 節點不是平衡的啊，已經有節點不平衡了，那這棵樹也不平衡了

怎麼判斷是平衡樹呢？

  通過上面的分析，我們可以先做出一個節點是否是平衡樹的判斷，并且記錄一下這個節點的高度資訊，之後一層一層判斷，一直到整棵樹判斷結束為止。

  可是我不知道最深的節點是誰啊，我怎麼才能知道從 j 開始呢？

這個時候其實就用到我們的遞歸邏輯了，遞歸基本流程就是先進去再出來，那照這個邏輯的話，我們隻需要在遞歸的出來部分 寫上判斷邏輯和記錄高度資訊然後傳回就可以了嘛！

• 假設我們有這麼一個類Info，隻有兩個屬性，isBalanced、height；分别表示是否平衡、高度，這個類就用于傳回的資訊
• 假設我們有這麼一個方法recursive，參數就是頭節點head，方法裡面寫邏輯，這個實作遞歸調用
• recursive 隻要head不為空，繼續
• recursive 遞歸調用recursive，參數為head的左 傳回一個左節點的Info對象 leftInfo
• recursive 遞歸調用recursive，參數為head的右 傳回一個右節點的Info對象 rightInfo
• 吼吼，這就進去了，接下來就是判斷和高度咯
• recursive isBalanced就是leftInfo是平衡的，且rightInfo是平衡的，且leftInfo和rightInfo的高度差的絕對值小于等于1
• recursive height就是 （leftInfo的高度，rightInfo的高度）的最大值 再加上自己 ==》max(l,r) + 1
• 傳回新Info對象

  好了，邏輯理出來了，下面寫代碼

public static class Info {
		public boolean isBalanced;
		public int height;

		public Info(boolean i, int h) {
			isBalanced = i;
			height = h;
		}
	}
	
	public static Info recursive(TreeNode head) {
		if (head == null) {
			return new Info(true, 0);
		}
		Info leftInfo = recursive(head.left);
		Info rightInfo = recursive(head.right);
		boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced
				&& Math.abs(leftInfo.height - rightInfo.height) <= 1;
		int height = Math.max(leftInfo.height, rightInfo.height) + 1;
		return new Info(isBalanced, height);
	}
           

力扣原題：110. 平衡二叉樹

/(ㄒoㄒ)/~~

看樣子還是太low了

搜尋樹

搜尋樹的定義

  二叉查找樹（Binary Search Tree），（又：二叉搜尋樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質的二叉樹： 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 它的左、右子樹也分别為二叉排序樹。二叉搜尋樹作為一種經典的資料結構，它既有連結清單的快速插入與删除操作的特點，又有數組快速查找的優勢；是以應用十分廣泛，例如在檔案系統和資料庫系統一般會采用這種資料結構進行高效率的排序與檢索操作。

• 老規矩先畫出一棵樹備用 ，後面都用這棵樹進行分析。
• 先給結論，這是一顆二叉搜尋樹2 節點，左右節點為空，不管1 節點，左節點為空，不管，右節點是 2 大于1，滿足規則3 節點，左節點，1，2都小于3，右節點 4 大于3 ，滿足規則5 節點，左節點 1，2，3，4都小于5，右節點 5，7，8，9大于5，滿足規則6、7、8、9同理，都滿足規則

怎麼判斷是搜尋樹呢？

中序驗證

  上面的例子有沒有看出什麼規律？

不知道大家是否還記得中序周遊的規則：先左再頭再右

有不記得或不清晰的小夥伴可以看我的另一篇【好記性不如爛筆頭】二叉樹的周遊方式

總結： 這其實這不就是中序周遊的結果是遞增的嗎，1，2，3，4，5，6，7，8，9

這個邏輯就比較清晰了，我完全可以先中序列印，然後判斷是否是有序遞增不就完了

代碼如下：

public static void main(String[] args) {
		TreeNode head = new TreeNode(5);
		head.left = new TreeNode(3);
		head.left.left = new TreeNode(1);
		head.left.left.right = new TreeNode(2);
		head.left.right = new TreeNode(4);

		head.right = new TreeNode(6);
		head.right.right = new TreeNode(8);
		head.right.right.left = new TreeNode(7);
		head.right.right.right = new TreeNode(9);
		List<Integer> list = new ArrayList<>();
		recursive3(head, list);
		if (isIncreasing(list)) {
			System.out.print("是二叉搜尋樹！");
		} else {
			System.out.print("不是二叉搜尋樹！");
		}
	}

	public static void recursive3(TreeNode head, List<Integer> list) {
		if (head == null) {
			return;
		}
		recursive3(head.left, list);
		System.out.print(head.val + " ");
		list.add(head.val);
		recursive3(head.right, list);
	}

	public static boolean isIncreasing(List<Integer> list) {
		for (int i = 0; i < list.size() - 1; i++) {
			if (list.get(i) >= list.get(i + 1)) {
				return false;
			}
		}
		return true;
	}
           

力扣原題：98. 驗證二叉搜尋樹

這個性能也太低了吧，有沒有好一點的方法啊?

進階驗證

  好家夥，上一個也太拉了，既然遞歸可以得到資訊，就沒必要拿出來再判斷了，直接在遞歸裡判斷不就完事了嗎?

理一下規則：

• 左小于頭，頭小于右呗
• 對于左邊來說，頭就是最大值max
• 對于右邊來說，頭就是最小值min
• 規則不就出來了
• 左邊的max < 頭 且 右邊的min > 頭

大緻思路：

• 假設我有個類Info，記錄max、min、是否是搜尋樹isB，記錄資訊用
• 假設我有個方法recursive4，參數就是TreeNode，傳回Info
• recursive4 如果節點是空的，傳回空呗
• recursive4 遞歸調用recursive4，參數head.left，傳回leftInfo
• recursive4 遞歸調用recursive4，參數head.right，傳回rightInfo
• 預設max = min = head.val
• 如果leftInfo不為空，max = max(leftInfo.max,max ); min = min(leftInfo.min,min );
• 如果leftInfo不為空，max = max(leftInfo.max,max ); min = min(leftInfo.min,min );
• 吼吼，這樣我就得到了 這個節點的最大值max 和最小值min
• 預設isB = true
• 如果leftInfo或rightInfo 不是搜尋樹isB=false，isB =false，沒啥說的，直接return new Info吧
• 走到這裡
• 判斷左邊的max是不是真的小于目前值 leftB
• 判斷右邊的min是不是真的大于目前值 right B
• 兩個判斷有一個為false，isB就是false
• return new info

  好了，開始寫代碼

public static class Info {
		public Boolean isB;
		public int max;
		public int min;
		
		public Info(boolean isB, int max,int min) {
			this.isB = isB;
			this.max = max;
			this.min = min;
		}
	}

    public static Info recursive4(TreeNode head) {
		if (head == null) {
			return null;
		}
		Info leftInfo = recursive4(head.left);
		Info rightInfo = recursive4(head.right);

		int max = head.val, min = head.val;

		if (leftInfo != null) {
			max = Math.max(leftInfo.max, max);
			min = Math.min(leftInfo.min, min);
		}
		if (rightInfo != null) {
			max = Math.max(rightInfo.max, max);
			min = Math.min(rightInfo.min, min);
		}
		boolean isB = true;
		if (leftInfo != null && !leftInfo.isB) {
			return new Info(false, max, min);
		}
		if (rightInfo != null && !rightInfo.isB) {
			return new Info(false, max, min);
		}
		boolean leftB = leftInfo == null ? true : leftInfo.max < head.val;
		boolean rightB = rightInfo == null ? true : rightInfo.min > head.val;
		if (!leftB || !rightB) {
			isB = false;
		}
		return new Info(isB, max, min);
	}
           

搞定，嘿嘿

平衡二叉搜尋樹

  那就是 是平衡樹又是二叉搜尋樹呗，上面的判斷邏輯都為true呗，這個代碼我就不貼了。

總結

覺得有用的話給我點個贊吧！