不断的学习,我们才能不断的前进
一个好的程序员是那种过单行线马路都要往两边看的人

数据结构面试

讲讲平衡二叉树、红黑树、B+树、B-树?

平衡二叉树

  • 结点的左右子树高度不差不超过1
  • 结点的左右子树也是平衡二叉树

红黑树的性质

  1. 节点是红色或黑色。
  2. 根节点是黑色。
  3. 每个叶子节点都是黑色的空节点(NIL节点)。
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树在插入或者删除结点时,会进行变色或者旋转来满足条件。

平衡二叉树与红黑树

  • 平衡二叉树比红黑树更加平衡,但AVL树在插入和删除的时候也会存在大量的旋转操作
  • 插入删除比较多的时候选择红黑树;查找比较多的时候选择平衡二叉树。
  • 红黑树没有严格要求,左右孩子高度之差小于1。

B-树/B树
是一种多路搜索树(并不是二叉的),每个结点的里面包含多个元素:

  1. 定义任意非叶子结点最多只有M个儿子;且M>2;
  2. 根结点的儿子数为[2, M];
  3. 除根结点以外的非叶子结点的儿子数为[M/2, M]
  4. 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
  5. 非叶子结点的关键字个数=指向儿子的指针个数-1;
  6. 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
  7. 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树。
  8. 所有叶子结点位于同一层;
    B树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点。
    特性: 任何一个关键字出现且只出现在一个结点中;除了根节点以外的非叶结点至少含有M/2个儿子。

B+树
B-树的一种变体,为所有的叶子结点增加来一个链表指针:

  • 非叶子结点只起索引的作用,叶子结点起存储的作用。
  • 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;

手写红黑树


import java.util.LinkedList;
import java.util.Queue;

/**
 * 创建红黑树的步骤:
 * 1. 创建红黑树,定义颜色
 * 2. 创建红黑树结点,定义parent、left、right 指针、颜色
 * 3. 定义辅助方法:parentOf、isRed、setRed、setBlack、inOrderPrint
 * 4. 左旋右旋方法:leftRotate、rightRotate
 * 5. 插入结点方法: insert
 * 6. 插入后修复结点的方法: insertFixUpz
 * @param <K>
 * @param <V>
 */
class RBTree<K extends Comparable<K>, V> {
	private static boolean RED = true;
	private static boolean BLACK = false;
	private RBNode root = null;

	/**
	 * 获取当前结点父节点
	 * @param node
	 * @return
	 */
	private RBNode parentOf(RBNode node) {
		if (node != null) {
			return node.parent;
		}
		return null;
	}

	private boolean isRed(RBNode node) {
		if (node != null) return node.color == RED;
		return false;
	}

	private boolean isBlack(RBNode node) {
		if (node != null) return node.color == BLACK;
		return false;
	}

	public void inOrderPrint(){
		inOrderPrint(this.root);
	}
	public void levelPrint(){
		levelPrint(this.root);
	}
	/**
	 * 层次遍历
	 * @param node
	 */
	private void levelPrint(RBNode node) {
		Queue<RBNode> queue=new LinkedList<>();
		queue.offer(node);
		while (!queue.isEmpty()){
			int n=queue.size();
			for(int i=0;i<n;i++){
				RBNode t=queue.poll();
				if(t==null) System.out.println("#");
				else {
					String s = t.getColor() ? "RED" : "BLACK";
					System.out.println("key:" + t.key + ", value: " + t.value+", color: "+ s);
					queue.offer(t.left);
					queue.offer(t.right);
				}

			}
		}
	}
	/**
	 * 中序遍历
	 * @param node
	 */
	private void inOrderPrint(RBNode node) {
		if (node != null) {
			inOrderPrint(node.left);
			String s = node.getColor() ? "RED" : "BLACK";
			System.out.println("key:" + node.key + ", value: " + node.value+", color: "+ s);
			inOrderPrint(node.right);
		}
	}

	/**
	 * 从当前结点root开始左旋,变成 自己右孩子 的左孩子,步骤:
	 * 1. 获取root的右结点: y=root.right
	 * 2. 将y的左子结点赋值给root.right, 并设置y左子结点的父结点为root: root.right=y.left; y.left.parent=root;
	 * 3. 将root结点赋值给y的左结点,并修改y的父节点的x的父节点: y.left=root; y.parent=x.parent; x.parent=y
	 * @param root
	 */
	private void leftRotate(RBNode root) {
		RBNode y = root.right;
		// 第一步将root的右结点,指向y的左结点,将y的左结点的父结点指向root
		root.right = y.left;
		if (y.left != null) {
			y.left.parent = root;
		}
		// 第二步 当root结点的父结点不为null,更新y的parent结点指向root的parent结点,修改parent的子结点指向y
		if (root.parent != null) { // 需要判断root在parent的左孩子 还是右孩子
			y.parent = root.parent;
			if (root == root.parent.left) {
				root.parent.left = y;
			} else {
				root.parent.right = y;
			}
		} else {
			y.parent = null;
			this.root = y;

		}
		// 将root的父节点指向y,y的左子结点指向root
		root.parent = y;
		y.left = root;

	}

	/**
	 * 从当前结点开始右旋,当前root结点变成左子结点 的 右结点
	 * @param root
	 */
	private void rightRotate(RBNode root) {
		RBNode y = root.left;
		// 第一步将root的左结点,指向y的右结点,将y的右结点的父结点指向root
		root.left = y.right;
		if (y.right != null) {
			y.right.parent = root;
		}
		// 第二步 当root结点的父结点不为null,更新y的parent结点指向root的parent结点,修改parent的子结点指向y
		if (root.parent != null) { // 需要判断root在parent的左孩子 还是右孩子
			y.parent = root.parent;
			if (root == root.parent.left) {
				root.parent.left = y;
			} else {
				root.parent.right = y;
			}
		} else {
			y.parent = null;
			this.root = y;

		}
		// 将root的父节点指向y,y的右子结点指向root
		root.parent = y;
		y.right = root;
	}

	/**
	 * 插入k,V值
	 * @param k
	 * @param v
	 */
	public void insert(K k, V v) {
		RBNode node = new RBNode(k, v, RED);
		insert(node);
	}

	/**
	 * 插入或者更新一个RBNode 结点
	 * @param node
	 */
	private void insert(RBNode node) {
		RBNode parent = null;
		RBNode cur = this.root;
		while (cur != null) {
			parent = cur;
			int cmp = cur.key.compareTo(node.key);
			if (cmp < 0) {
				cur = cur.right;
			} else if (cmp > 0) cur = cur.left;
			else {
				cur.setValue(node.getValue());// 更新
				return;
			}

		}
		if (parent != null) {
			int cmp1 = parent.key.compareTo(node.key);
			if (cmp1 < 0) {
				parent.right = node;
			} else {
				parent.left = node;
			}
			node.parent = parent;

		} else {
			this.root=node;

		}
		insertFixUp(node);// 插入后修复红黑树
	}

	/**
	 * 插入后修复红黑树,变色或者旋转:
	 *  场景1:红黑树为空树,插入后将根结点染色为黑色
	 *  场景2:插入结点的key已经存在,不需要改变
	 *  场景3:插入结点的父节点为黑色,不需要改变
	 *  情景4:插入结点的父节点为红色:需要额外的处理
	 *      4.1: 叔叔结点存在,并且为红色:将 叔叔、爸爸结点染色为黑色,爷爷结点为红色,以爷爷结点为当前结点,开始递归。
	 *      4.2: 叔叔结点不存在,或者颜色为黑色,父结点为爷爷结点的左子树
	 *          4.2.1: 插入结点为父结点的左子结点 LL情况: 将爸爸结点染色为黑色,爷爷结点为红色,以爷爷结点右旋
	 *          4.2.2: 插入结点为父结点的右子结点 LR情况: 以爸爸结点开始左旋,变成4.2.1情景,然后以爸爸结点开始递归
	 *      4.3: 叔叔结点不存在,或者颜色为黑色,父结点为爷爷结点的右子树
	 *          4.3.1: 插入结点为父结点的左子结点 RL情况: 以爸爸结点开始右旋,变成4.3.2情景,然后以爸爸结点开始递归
	 * 	        4.3.2: 插入结点为父结点的右子结点 RR情况: 将爸爸结点染色为黑色,爷爷结点为红色,以爷爷结点左旋
	 * @param node
	 */
	public void insertFixUp(RBNode node){
		this.root.setColor(BLACK); // 强制根结点为黑色,
		RBNode parent=null,grandParent=null, uncle=null;

		if((parent=parentOf(node))!=null && isRed(parent)){ // 父节点是红色,一定存在爷爷结点

			if((grandParent=parentOf(parent)).left==parent){ // 爸爸结点为爷爷结点的左子节点
				if((uncle=grandParent.right)!=null && isRed(uncle)){ // 4.1
					uncle.setColor(BLACK);
					parent.setColor(BLACK);
					grandParent.setColor(RED);
					insertFixUp(grandParent);
				}else{ //4.2
					if(node==parent.left){// 4.2.1 LL 父子双红的情况
						parent.setColor(BLACK);
						grandParent.setColor(RED);
						rightRotate(grandParent);
					}else{ // 4.2.2 LR情况
						leftRotate(parent);
						insertFixUp(parent);
					}
				}

			}else{
				if((uncle=grandParent.left)!=null && isRed(uncle)){ // 4.1
					uncle.setColor(BLACK);
					parent.setColor(BLACK);
					grandParent.setColor(RED);
					insertFixUp(grandParent);
				}else{ // 4.3
					if(node==parent.left){// 4.3.1 RL
						rightRotate(parent);
						insertFixUp(parent);
					}else{ // 4.3.2 RR 父子双红情况
						parent.setColor(BLACK);
						grandParent.setColor(RED);
						leftRotate(grandParent);
					}
				}
			}
		}

	}


	static class RBNode<K extends Comparable<K>, V> {
		K key;
		V value;
		RBNode<K, V> parent;
		RBNode<K, V> left;
		RBNode<K, V> right;
		boolean color;


		public RBNode(K k, V v, boolean color) {
			this.color = color;
			this.key = k;
			this.value = v;
		}

		public RBNode(RBNode<K, V> parent, RBNode<K, V> left, RBNode<K, V> right, boolean color) {
			this.parent = parent;
			this.left = left;
			this.right = right;
			this.color = color;
		}

		public RBNode<K, V> getLeft() {
			return left;
		}

		public RBNode<K, V> getRight() {
			return right;
		}


		public V getValue() {
			return value;
		}

		public void setValue(V value) {
			this.value = value;
		}

		public void setLeft(RBNode<K, V> left) {
			this.left = left;
		}

		public void setRight(RBNode<K, V> right) {
			this.right = right;
		}

		public void setColor(boolean color) {
			this.color = color;
		}
		public boolean getColor() {
			return this.color;
		}
	}

}

public class HandWriteRedBlackTree {
	public static void main(String[] args) {
		RBTree root=new RBTree();
		for(int i=1;i<10;i++){
			root.insert(i,i);
		}
		root.levelPrint();
	}

}


目录