BST二叉搜索树

概述

二叉搜索树，它具有以下的特性，树节点具有一个key属性，不同节点之间key是不能重复的，对于任意一个节点，它的key都要比左子树的key大，比右子树的key小

实现

创建节点

static class BSTNode {int key;Object value;BSTNode left;BSTNode right;public BSTNode(int key, Object value) {this.key = key;this.value = value;}public BSTNode(int key, Object value, BSTNode left, BSTNode right) {this.key = key;this.value = value;this.left = left;this.right = right;}}

查找节点

利用二叉树的性质

public Object get(int key) {BSTNode node = root;while (node != null) {if (node.key < key) {node = node.right;} else if (node.key > key) {node = node.left;} else {return node.value;}}return null;}

增加节点

同样利用二叉树的性质，但是需要记录要增加的节点的父节点

public void put(int key, Object value) {BSTNode node = root;BSTNode parent = null;while (node != null) {parent = node;if (key < node.key) {node = node.left;} else if (key > node.key) {node = node.right;} else {//直接修改node.value = value;return;}}if (parent == null) {root = new BSTNode(key, value);} else if (key > parent.key) {parent.right = new BSTNode(key, value);} else {parent.left = new BSTNode(key, value);}}

查找后驱值

在后面的AVL，以及红黑树中删除节点是，我们经常会需要求一个节点的后驱节点

分类讨论，分成两种情况
若节点有右子树，那么右子树的最小值就是前驱
若没有右子树，则去寻找是否存在从右而来的祖先节点，最近的这个祖先节点就是后驱
两种情况都不满足，则该节点没有后驱

public Object predecessor(int key) {BSTNode ancestorFromRight = null;BSTNode node = root;while (node != null) {if (key < node.key) {ancestorFromRight = node;node = node.left;} else if (key > node.key) {node = node.right;} else {break;}}//没有该节点if (node == null) {return null;}if (node.right != null) {return min(node.right);}return ancestorFromRight == null ? null : ancestorFromRight.value;}public Object min(BSTNode node) {if (node == null) {return null;}while (node.left != null) {node = node.left;}return node.value;}

根据关键词删除

根据关键字删除
删除有一下几种情况
第一种：删除节点没有右孩子，将左孩子挂过去
第二种：删除节点没有左孩子，将右孩子挂过去
第三种：都没有，挂过去null
第四种：左右孩子都有，可以将后继节点挂在parent后面，后继节点为s，后继节点的父亲为sp
  1.将如果sp就是要删除的节点
  2.sp不是删除节点，需要将s的后代给sp

public Object delete(int key) {BSTNode node = root;BSTNode parent = null;while (node != null) {if (key < node.key) {parent = node;node = node.left;} else if (key > node.key) {parent = node;node = node.right;} else {break;}}if (node == null) {return null;}if (node.left == null) {//情况1shift(parent, node, node.right);//情况2} else if (node.right == null) {shift(parent, node, node.left);} else {BSTNode s = node.right;BSTNode sParent = node;while (s.left != null) {sParent = s;s = s.left;}if (sParent != node) {//将后驱节点的孩子挂在后驱节点父亲的后面shift(sParent, s, s.right);s.right = node.right;}//后驱节点一定没有左孩子，所以可以直接的挂靠shift(parent, node, s);s.left = node.left;}return node.value;}/** 托孤方法** */private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {if (parent == null) {root = child;} else if (deleted == parent.left) {parent.left = child;} else {parent.right = child;}}

找到树中所有小于key的节点的value

我们可以通过一个中序遍历实现，对于一个二叉搜索树来说，中序遍历的结果，恰好是从小到大排序的

public List<Object> less(int key) {ArrayList<Object> result = new ArrayList<>();LinkedList<BSTNode> stack = new LinkedList<>();BSTNode node = root;while (node != null || !stack.isEmpty()) {if (node != null) {stack.push(node);node = node.left;} else {BSTNode min = stack.pop();if (min.key < key) {result.add(min.value);} else {break;}node = min.right;}}return result;}