vv13
博客订阅

二叉查找树

在计算机科学中,树是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合,把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它是由n(n>0)个有限节点组成一个具有层次关系的集合。

树结构本身可以用来描述很多事物,比如公司组织架构、家谱等,在计算机中应用就更广泛了,比如浏览器书签、文件系统、语法树、思维导图等等,除了描述事物,树还有一个作用是用于索引和查找的,它的形式特别多,诸如二叉树、平衡树、红黑树等。

它具有以下的特点:

  • 根节点:一棵树有且仅有一个根节点,如图上的A
  • 父节点:根节点没有父节点,除此以外每个节点都有且仅有一个父节点
  • 子节点:树每个节点有零个或多个子节点,如B、C为A的子节点,D、E、F为B的子节点
  • 树叶:,D、E、F、G、H这些没有子节点的节点,称之为树叶
  • 兄弟节点:具有相同父节点
  • 层次与深度:树是分层结构,从上到下,分别为第1层、第2层、……,而最大层数即为树的深
  • 度:节点用于子树的数目
  • 边:两个节点的连线

二叉树

所谓二叉树,与树最大的区别就是,每个节点最多只能有2个子节点,称之为左节点和右节点。二叉树有5种基本形态:

除此之外,二叉树还有2种基本类型:

  • 完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树
  • 满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树

二叉查找树

二叉查找树(BinarySearchTree,BST)是一种特殊的二叉树,它也被叫做二叉搜索树、有序二叉树或排序二叉树,具有以下特性:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。

BST 算法查找时间依赖于树的拓扑结构。最佳情况是 O(log­2n),而最坏情况是 O(n)

实现一个二叉查找树

在此用JavaScript的基本语法来实现了,首先定义可用于描述二叉树的基本数据结构:

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

function BinarySearchTree() {
  this.root = null;
}

在此会实现以下方法:

还有一些有用的方法:计算最大最小值、获取树的高度、获取节点数目在此就不一一列举了,有兴趣的话可以自己实现以下。

insert

对于插入节点操作,核心判断逻辑为一个递归操作,具体步骤为:

  1. 判断节点是否为空,若为空则直接复制,否则进行下一步;
  2. 插入值是否大于当前节点值,若大于则应该插入到节点右侧,将当前节点的右子树进行第1步的判断;
  3. 插入值是否小于当前节点值,若小于则应该插入到节点左侧,将当前节点的左子树进行第1步的判断;
  4. 若插入之与当前节点值相等,任意选择步骤2或者步骤3。
BinarySearchTree.prototype.insert = function(value) {
  var newNode = new Node(value);
  if (this.root === null) {
    this.root = newNode;
  } else {
    BinarySearchTree.insertNode(this.root, newNode);
  }
};

BinarySearchTree.insertNode = function(node, newNode) {
  if (node.value > newNode.value) {
    if (node.left === null) {
      node.left = newNode;
    } else {
      BinarySearchTree.insertNode(node.left, newNode);
    }
  } else {
    if (node.right === null) {
      node.right = newNode;
    } else {
      BinarySearchTree.insertNode(node.right, newNode);
    }
  }
};

search

二叉查找树的最小值在最左边,最大值在最右边,因此在搜索的时候,只需要确定方向,然后直到找到值或指针为null时停止:

BinarySearchTree.prototype.search = function(value) {
  return BinarySearchTree.searchNode(this.root, value);
};

BinarySearchTree.searchNode = function(node, value) {
  if (node === null) {
    return null;
  } else if (node.value === value) {
    return node;
  } else if (node.value < value) {
    return BinarySearchTree.searchNode(node.right, value);
  } else {
    return BinarySearchTree.searchNode(node.left, value);
  }
};

使用非递归的方式也未尝不可:

BinarySearchTree.searchNodeNoRecursion = function(node, value) {
  var result = null;
  while (node) {
    if (node.value === value) {
      result = node;
      break;
    } else if (node.value < value) {
      node = node.right;
    } else {
      node = node.left;
    }
  }
  return result;
};

remove

删除节点的操作相对会复杂一点,在此画了一张流程图:

以下是使用递归方法来实现的删除节点方法,好处在于不用储存父节点与指针方向,每次进行查找操作的同时,也会进行赋值操作:

// 删除指定值
BinarySearchTree.prototype.remove = function(value) {
  this.root = BinarySearchTree.removeNode(this.root, value);
  reutrn this.root
};

BinarySearchTree.removeNode = function(node, value) {
  if (node === null) {
    return null;
  } else if (node.value < value) {
    node.right = BinarySearchTree.removeNode(node.right, value);
    return node;
  } else if (node.value > value) {
    node.left = BinarySearchTree.removeNode(node.left, value);
    return node;
  } else {
    if (node.left === null && node.right === null) {
      return null;
    } else if (node.left === null) {
      return node.right;
    } else if (node.right === null) {
      return node.left;
    } else {
      var minRightNode = node.right;
      while (minRightNode !== null && minRightNode.left !== null) {
        minRightNode = minRightNode.left;
      }
      node.value = minRightNode.value;
      node.right = BinarySearchTree.removeNode(node.right, minRightNode.value);
      return node;
    }
  }
};

还有一种方法是使用常规的方法,先使用search的思路找到节点,同时记录父节点以及指针方向,再对节点进行修改操作:

BinarySearchTree.removeNodeBySearch = function(node, value) {
  var searchNode = node
  var parent = null
  var arrow = null
  while (searchNode) {
    if (searchNode.value === value) {
      break;
    } else if (node.value < value) {
      parent = node
      searchNode = searchNode.right;
      arrow = 'right'
    } else {
      parent = searchNode
      searchNode = searchNode.left;
      arrow = 'left'
    }
  }
  if (!searchNode) return node
  if (searchNode.left === null && searchNode.right === null) {
    parent[arrow] = null
  } else if (searchNode.left === null) {
    parent[arrow] = searchNode.right
  } else if (searchNode.right === null) {
    parent[arrow] = searchNode.left
  } else {
    var minRightNode = searchNode.right;
    while (minRightNode !== null && minRightNode.left !== null) {
      minRightNode = minRightNode.left;
    }
    searchNode.value = minRightNode.value;
    searchNode.right = BinarySearchTree.removeNodeBySearch(searchNode.right, minRightNode.value);
  }
  return node;
}

深度优先遍历DFS

preOrderTraverse

前序遍历,指先访问根,然后访问子树的遍历方式:

BinarySearchTree.prototype.preOrderTraverse = function(cb) {
  BinarySearchTree.preOrderTraverseNode(this.root, cb);
};
BinarySearchTree.preOrderTraverseNode = function(node, cb) {
  if (node === null) return;
  cb(node.value);
  BinarySearchTree.preOrderTraverseNode(node.left, cb);
  BinarySearchTree.preOrderTraverseNode(node.right, cb);
};

inOrderTraverse

中序遍历,指先访问左(右)子树,然后访问根,最后访问右(左)子树的遍历方式:

BinarySearchTree.prototype.inOrderTraverse = function(cb) {
  BinarySearchTree.inOrderTraverseNode(this.root, cb);
};
BinarySearchTree.inOrderTraverseNode = function(node, cb) {
  if (node === null) return;
  BinarySearchTree.inOrderTraverseNode(node.left, cb);
  cb(node.value);
  BinarySearchTree.inOrderTraverseNode(node.right, cb);
};

postOrderTraverseNode

后序遍历,指先访问子树,然后访问根的遍历方式:

BinarySearchTree.prototype.postOrderTraverse = function(cb) {
  BinarySearchTree.postOrderTraverseNode(this.root, cb);
};
BinarySearchTree.postOrderTraverseNode = function(node, cb) {
  if (node === null) return;
  BinarySearchTree.postOrderTraverseNode(node.left, cb);
  BinarySearchTree.postOrderTraverseNode(node.right, cb);
  cb(node.value);
}

广度优先遍历BFS

breadthFirstTraverse

简单来说,BFS在二叉树中的搜索,即沿着层级从左向右进行遍历,直到所有节点均被访问,它也被称为盲目的搜索法。在此的实现主要借助于数组,将数组作为队列使用,具体方法如下:

  1. 将根节点放入数组中;
  2. 从队列取出一个第一个节点,并将其存在的左子树与右子树一次放到队列最后;
  3. 重复步骤2直到队列为空。
BinarySearchTree.prototype.breadthFirstTraverse = function(cb) {
  BinarySearchTree.breadthFirstTraverseNode(this.root, cb);
};

BinarySearchTree.breadthFirstTraverseNode = function(node, cb) {
  var queue = [node];
  var popNode = null;
  while (queue.length) {
    popNode = queue.shift();
    if (!popNode) break;

    cb(popNode);
    if (popNode.left) {
      queue.push(popNode.left);
    }
    if (popNode.right) {
      queue.push(popNode.right);
    }
  }
};

可视化

由于整个程序是一个抽象的分层结构,因此可视化是十分必要的一项工作。在canvas与svg之前没有过多犹豫,果断选择后者,因为这类图表注重的是节点增删改查,而且本身也不会有什么动画。

经过一番折腾,最终选用d3-hierarchy这个库,它用于分层数据的可视化,创建节点连接图、领接矩阵图等。

首先需要使用Hierarchy API创建分层数据结构,通过上几个章节我们构造出的二叉树的数据结构大致为:

{
  value: 1,
  left: {
    value: 2,
    left: {
      value: 4,
      left: null,
      right: null
    },
    right: null
  },
  right: {
    value:3,
    left: null,
    right: null
  }
}

而Hierarchy的结构为:

{
  "name": "Eve",
  "children": [
    {
      "name": "Cain"
    },
    {
      "name": "Seth",
      "children": [
        {
          "name": "Enos"
        },
        {
          "name": "Noam"
        }
      ]
    },
  ]
}

因此我们需要将二叉树的结构转化为上述结构才行,好在d3.hierarchy(data[, children])的第二个参数就是子元素构造器,它允许函数返回空或是子元素数组。而二叉树每个节点有左子树和右子树之分,而Hierarchy的父元素可以有任意个子元素,因此我们在转化时,若二叉树某个节点只有右子树,当它传入chilren构造器时,将它返回[{}, d.right],此时数组的第一个元素代表左子树,第二个代表右子树,空对象仅仅是为了占位,在可视化的时候我们将其排除在外即可。

最终使用d3.tree()将转化好的分层结构进行布局即可,我们就拥有了一个具有坐标点的二叉树。

值得一提的是,最开始我使用的d3进行控制的dom,语法十分繁琐,也不是很通用,而后采用了React进行dom的控制,d3只负责数据与逻辑层,它们简直是绝配,所以现阶段若再遇到这种可视化的工作,我一定会选用React与D3.js。

完整的二叉树实现代码与可视化程序在这里可以找到。