专栏首页老沙课堂数据结构与算法(九)二叉搜索树的删除操作

数据结构与算法(九)二叉搜索树的删除操作

1、二叉搜索树的删除操作

介绍

关于二叉搜索树的删除操作,先弄清如何找到前驱节点和后继节点

前驱节点(predecessor)

介绍

•前驱节点:中序遍历时的前一个节点•如果左子树存在,从该节点的左子节点的最右的节点。•如果左子树 == null && 父节点!= null 父节点为父节点遍历,一直到节点关系发生改变。如下图所示。•如果左子树 == null && 父节点== null ,没有前驱节点。

代码

public Node<E> findPredecessorNode(E element) {
  return findPredecessorNode(node(element));
}

private Node<E> findPredecessorNode(Node<E> element) {
  if (element.left != null) {
    Node<E> node = element.left;
    while (node.right!= null) {
      node = node.right;
    }
    return node;
  }

  while (element.parent != null && element == element.parent.left) {
    element = element.parent;
  }
  return element.parent;
}

后继节点(succeessor)

•前驱节点:中序遍历时的后一个节点•如果右子树存在,从该节点的左子节点的最左的节点。•如果右子树 == null && 父节点!= null 父节点为父节点遍历,一直到节点关系发生改变。•如果右子树 == null && 父节点== null ,没有后继节点。

删除节点

叶子节点

•直接删除

度为1的节点

•用子节点替换既可

度为2的节点

•找到前驱或者后继节点的值,并替换原节点。•他的前驱、后继节点的度只可能是0或者是1。

private void remove(Node<E> node) {
  if (node == null) return;
  size--;

  // 度为2的节点
  if (node.twoChildren()) { 
    // 找到后继节点
    Node<E> s = findSucceessorNode(node);
    // 用后继节点的值覆盖原节点的值
    node.element = s.element;

    node = s;
  }

  // 删除的node节点  (node的度必然是1或者0) 如果是0 replacement为null
  Node<E> replacement = node.left != null ? node.left : node.right;

  // 度为1
  if (replacement != null) {
    // 更改parent
    replacement.parent = node.parent;
    // 更改parent的 chil
    if (node.parent == null) { // node是度为1的节点并且是根节点
      root = replacement;
    } else if (node == node.parent.left) {
      node.parent.left = replacement;
    } else { // node == node.parent.right
      node.parent.right = replacement;
    }
  } else if (node.parent == null) { // node是叶子节点并且是根节点
    root = null;
  } else { // node是叶子节点
    if (node == node.parent.left) {
      node.parent.left = null;
    } else { 
      node.parent.right = null;
    }
  }
}

2、根据遍历结果重构二叉树

•中序遍历+ 前/后序遍历 •可以确定一颗唯一二叉树•前序遍历+ 后序遍历•如果他是一颗真二叉树(Proper Binary Tree) ,结果是唯一的。•其他情况 不唯一。

List<Integer> perorder = Arrays.asList(5,1,2,4,3,9);
List<Integer> inorder = Arrays.asList(2,1,4,5,9,3);


private  Node<E> RefactoringTree(List<E> perorderList, List<E> inorderList) {
  if (perorderList.size() == 0|| inorderList.size() == 0) {
    return null;
  }
  E element = perorderList.get(0);

  Node<E> root = new Node<>(element, null);
  perorderList = perorderList.subList(1, perorderList.size());
  int index = inorderList.indexOf(element);
  List<E> leftInorderList = inorderList.subList(0, index);
  List<E> rightInorderList = inorderList.subList(index + 1, inorderList.size());

  List<E> leftperOrderList = perorderList.subList(0, leftInorderList.size());
  List<E> rightperOrderList = perorderList.subList(leftperOrderList.size(), perorderList.size());

  root.left = RefactoringTree(leftperOrderList, leftInorderList);
  root.right = RefactoringTree(rightperOrderList, rightInorderList);
  return  root;
}

本文分享自微信公众号 - 老沙课堂(gh_f73a6b772d4f),作者:沙睿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法(十一)B树

    •1个节点可以存储超过2个元素、可以拥有超过2个子节点•拥有二叉搜索树的一些特质(小的子节点在左面 大的子节点在右面)•平衡,每个节点的所有子树高度一致•比较矮

    老沙
  • 数据结构与算法(十二) 红黑树

    •节点是有颜色的Red/Black•根节点必须是Black•叶子节点必须是Black•红黑树的叶子节点会自动将度为0 或者度为1的节点的度自动补充为2,补充的节...

    老沙
  • 数据结构与算法(六) 二叉树遍历

    •任意一个节点的值都大于其左子树的值•任意一个节点的值都小于其右子树的值•他的左右子树也是一颗二叉搜索树•二叉搜索树可以大大提高效率(搜索和添加删除时间复杂度都...

    老沙
  • 【算法】二叉树中找到一个节点的后继节点,前继节点

    该结构比普通二叉树节点结构多了一个指向父节点parent指针。 假设有一 棵Node类型的节点组成的二叉树,树中每个节点的parent指针都正确地指向自己的父...

    MapleYe
  • 统计学习方法:K近邻

    K近邻(k-nearest neighbors)算法是一个简单、直观的算法。它没有显式的学习过程,但是物理意义与思路都非常容易理解。

    统计学家
  • 程序员面试金典 - 面试题 02.03. 删除中间节点

    实现一种算法,删除单向链表中间的某个节点(除了第一个和最后一个节点,不一定是中间节点),假定你只能访问该节点。

    Michael阿明
  • 在二叉树中找到一个节点的后继节点

    该结构比普通二叉树节点结构多了一个指向父节点的parent指针。 假设有一 棵Node类型的节点组成的二叉树, 树中每个节点的parent指针都正确地指向自己的...

    大学里的混子
  • Java集合详解6:这次,从头到尾带你解读Java中的红黑树

    《Java集合详解系列》是我在完成夯实Java基础篇的系列博客后准备开始写的新系列。

    Java技术江湖
  • AbstractQueuedSynchronizer 源码分析

    AQS是通过CHL队列来实现锁请求阻塞列表的。可以通过acquire(int arg)来分析,当前线程竞争锁时的流程,然后再通过release(int arg)...

    技术蓝海
  • Kubernetes网络揭秘:一个HTTP请求的旅程

    客座撰稿人:Karen Bruner,StackRox技术专员。原文可以在这里找到。

    CNCF

扫码关注云+社区

领取腾讯云代金券