平衡二叉树
之前讲过树,二叉树,二叉排序树,现在说说这个平衡二叉树,平衡二叉树是一个平衡的二叉排序树,关键在于平衡,它的意思是其中每一个节点的左子树和右子树的高度差不多都是1。
为什么要平衡呢?还是为了提高查找速度,举个例子有一个数组 [3,2,1,4,5,6,7,10,9,8],如果按照二叉排序树的算法生成之后应该是图1的结果,这样其实对于查找是不利的,举个例子,如果你要找节点8,
你得找7次,但是如果是图2这种结构,则只需要3次。
下面看一下图:
最后贴一个PHP实现的代码:
树节点类:
1 | class Node |
这里涉及到几个算法,比较难理解:
左旋和右旋
1 | /** |
左平衡旋转和右平衡旋转
1 | /** |
最后是插入算法:
1 | public function insertAvl(&$root, int $key, string $data, bool &$taller = false) |