二叉搜索树也叫二叉查找树或者二叉排序树, 它要么是一颗空树, 要么满足以下几点:
1. 若任意节点的左子树不空, 则左子树上所有节点的值均小于它的根节点的值.
2. 若任意节点的右子树不空, 则右子树上所有节点的值均大于它的根节点的值.
3. 任意节点的左, 右子树也分别为二叉搜索树.
4. 没有键值相等的节点.
image
二叉搜索树的实现
1. 二叉搜索树的存储结构
- public class BinarySearchTree {
- public static Node root;
- public BinarySearchTree(){
- this.root = null;
- }
- }
- class Node{
- int data;
- Node left;
- Node right;
- public Node(int data){
- this.data = data;
- left = null;
- right = null;
- }
- }
2. 二叉搜索树的插入
a. 循环二分查找到需要插入的地方.
b. 假如插入的值小于当前的值, 并且当前左节点为空, 那么左节点就指向新节点.
c. 假如插入的值大于当前的值, 并且当前右节点为空, 那么右节点就指向新节点.
- public void insert(int id){
- Node newNode = new Node(id);
- if(root == null){
- root = newNode;
- return;
- }
- Node current = root;
- Node parent = null;
- while(true){
- parent = current;
- if(id <current.data){
- current = current.left;
- if(current == null){
- parent.left = newNode;
- return;
- }
- } else {
- current = current.right;
- if(current == null){
- parent.right = newNode;
- return;
- }
- }
- }
- }
3. 二叉搜索树的删除
a. 当删除节点为叶子节点时, 直接删除节点.
b. 当删除节点只有左子树时, 重接左子树.
c. 当删除节点只有右子树时, 重接右子树.
d. 当删除节点既有左子树, 又有右子树时, 先找一个可以替换删除节点的节点. 由于二叉树的性质, 左子树的值小于根节点的值, 右子树的值大于根节点的值. 所以右子树的最左的节点就是替换删除的节点, 然后在重接右子树.
第 d 点的图例:
image
- public boolean delete(int id) {
- Node parent = root;
- Node current = root;
- boolean isLeftChild = false;
- while (current.data != id) {
- parent = current;
- if (current.data> id) {
- isLeftChild = true;
- current = current.left;
- } else {
- isLeftChild = false;
- current = current.right;
- }
- if (current == null) {
- return false;
- }
- }
- // 删除的节点既没左节点, 也没右节点
- if (current.left == null && current.right == null) {
- if (current == root) {
- root = null;
- }
- if (isLeftChild == true) {
- parent.left = null;
- } else {
- parent.right = null;
- }
- }
- // 删除的节点只有左节点
- else if (current.right == null) {
- if (current == root) {
- root = current.left;
- } else if (isLeftChild) {
- parent.left = current.left;
- } else {
- parent.right = current.left;
- }
- }
- // 删除的节点只有右节点
- else if (current.left == null) {
- if (current == root) {
- root = current.right;
- } else if (isLeftChild) {
- parent.left = current.right;
- } else {
- parent.right = current.right;
- }
- }
- // 删除的节点既有左节点, 又有右节点
- else if (current.left != null && current.right != null) {
- // 找到右子树的最左节点
- Node successor = getSuccessor(current);
- if (current == root) {
- root = successor;
- } else if (isLeftChild) {
- parent.left = successor;
- } else {
- parent.right = successor;
- }
- successor.left = current.left;
- }
- return true;
- }
- public Node getSuccessor(Node deleleNode) {
- Node successsor = null;
- Node successsorParent = null;
- Node current = deleleNode.right;
- while (current != null) {
- successsorParent = successsor;
- successsor = current;
- current = current.left;
- }
- if (successsor != deleleNode.right) {
- successsorParent.left = successsor.right;
- successsor.right = deleleNode.right;
- }
- return successsor;
- }
4. 二叉搜索树的查找
- public boolean find(int id) {
- Node current = root;
- while (current != null) {
- if (current.data == id) {
- return true;
- } else if (current.data> id) {
- current = current.left;
- } else {
- current = current.right;
- }
- }
- return false;
- }
总结
由于它是一颗有序的树, 就可以进行折半查找, 每一次查找, 假如不是匹配的值, 都可以排除一半的值. 所以一般的时间复杂度是 O(log n). 假如这棵树退化为斜树, 就差不多是线性表了, 它的时间复杂度就是 O(n).
虽然二叉搜索树的最坏时间复杂度是 O(n), 但通过一些改进可以把最坏时间复杂度降至 O(log n), 比如 AVL 树, 红黑树等. 红黑树不需要绝对的平衡, 所以插入和删除效率上要高, 在 JDK1.8 中哈希表存储大于等于 8 个节点的链表就是采用的红黑树.
所以二叉搜索树在查找上是非常快的, 在一些需要很高查询效率上推荐使用.
来源: http://www.jianshu.com/p/3b787e000f76