2019-11-05

数据结构 二叉树

words: 5k    views:    time: 25min

算法设计

---

前面介绍线性数据结构时提到，如果数据本身有序，那么可以用二分法来降低查找的时间复杂度，但是在线性结构上实现二分法总有一些局限，比如链表不好定位中间元素，而数组又免不了拷贝成本。

因此，有人提出了树这种结构，树本身也是一种链式数据结构，但它巧妙地解决了链式数据只能从头或者从尾开始查找的问题，而是从中间开始向两边查找。不管是下文要介绍的二叉树，还是后面的Avl树、红黑树或者B树，其基本思想都是二分法，区别只在于通过不同的规则来维持树的平衡，以便使查找的复杂度更接近于二分法。

1. 定义

树：定义树的一种自然的方式是递归，树由根节点及其子树构成，而每一个子树又有自己的根节点与子树。

二叉树：二叉树在树的基础上加了一个限定，对于任意节点，至多只能有两个子树。

二叉查找树：二叉查找树又在二叉树的基础上加了一个限定，对于任意节点X，它的左子树中的所有节点的值都小于X的值，而右子树中的所有节点的值都大于X的值。

本文讨论的就是二叉查找树，以下简称为二叉树。

相关定义：
阶：节点的子树个数，所以二叉树就是一个二阶树。
叶子节点：没有子树的节点，即阶为零。
节点高度：对任意节点x，其高度为叶子节点到x节点的路径长度。树的高度就是叶子节点到根节点的高度。
节点深度：对任意节点x，其深度为根节点到x节点的路径长度。树的深度就是根节点到叶子节点的深度。
满二叉树：所有叶子节点都在同一层，而且其他层任意节点都有两个子节点，从形象上看就像一个等腰三角形。

2. 分析实现

这里主要分析几个常见的操作，比如查找、插入、删除以及迭代，其他的操作都可以在此基础上进行实现。

2.1. 查找

根据树的特性，可以采用递归的方式来实现（如果树的深度太深，则存在耗尽栈空间的风险）。如果是空树，则直接返回false；否则从树根开始比较，如果大于就向左递归，否则向右递归，直至找到等于的节点返回true或者最后节点为空返回false为止。

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/structure/tree/BinaryTreeSet.java

public boolean contains(Object o){
    return contains((E)o, getRoot());
}

private boolean contains(E e, Node<E> node){
    if(isEmptyNode(node)){
        return false;
    }
    
    int compare = e.compareTo(node.element);
    if(compare < 0){
        return contains(e, node.left);
    }else if(compare > 0){
        return contains(e, node.right);
    }else{
        return true;
    }
}

2.2. 插入

先忽略节点重复的问题，在实现插入时，可以先与2.1一样进行查找，如果找到值相等的节点，可以进行覆盖，否则最后结束的位置一定是个空节点，也就是待插入的位置，即插入的节点一定为叶子节点。

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/structure/tree/BinaryTreeSet.java

public boolean add(E e){
    root = add(e, getRoot());
    return true;
}

private Node<E> add(E e, Node<E> node){
    if(isEmptyNode(node)){
        size++;
        return new Node<>(e);
    }
    
    int compare = e.compareTo(node.element);
    if(compare < 0){
        node.left = add(e, node.left);
    }else if(compare > 0){
        node.right = add(e, node.right);
    }else{
        node.element = e;
    }
    return node;
}

2.3. 删除

对于要删除的节点X，考虑几种情形：

1. X是一片树叶，则可以直接删除；
2. X只有一个子节点，则可以让X的父节点指向X的儿子，即绕过X就可以了；
3. X有两个子节点，根据二叉树的特性：任意节点肯定大于它左边的节点，而小于它右边的节点。那么，如果要删除节点X，可以用X左子树的最大节点（称为X的前驱）代替X，然后转化为对前驱节点的删除；或者用X右子树的最小节点（称为X的后继）代替X，然后转化为对后继节点的删除。这样便可以将删除情形转换成 1 或 2。

• 示例

依次插入10, 11, 9, 5, 2, 1, 8, 6, 4, 3，然后删除5

使用前驱节点4的替代并删除，转化为删除情形2

或者使用后继节点6替带并删除，转化为情形1

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/structure/tree/BinaryTreeSet.java

public boolean remove(Object o){
    root = remove((E)o, root);
    return true;
}

private Node<E> remove(E e, Node<E> node){
    if(isEmptyNode(node)){
        return node;
    }
    
    int compare = e.compareTo(node.element);
    if(compare < 0){
        node.left = remove(e, node.left);
    }else if(compare > 0){
        node.right = remove(e, node.right);
    }else if(node.left != null && node.right != null){  //情形3
        node = removeLeftMax(node); //or node = removeRigthMin(node);
        size--;
    }else{  //情形1或2
        node = (node.left != null) ? node.left : node.right;
        size--;
    }
    return node;
}

protected Node<E> removeLeftMax(Node<E> node){
    if(node.left.right == null){  //leftMax = node.left
        Node<E> right = node.right;
        node = node.left;
        node.right = right;
    }else{
        Node<E> right = node.right;
        Node<E> left = node.left;
        
        node = removeMax(node.left);
        node.right = right;
        node.left = left;
    }
    return node;
}

private Node<E> removeMax(Node<E> node){ 
    if(node.right != null && node.right.right == null){
        Node<E> max = node.right;
        node.right = max.left;
        return max;
    }
    return removeMax(node.right);
}

protected Node<E> removeRigthMin(Node<E> node){
    if(node.right.left == null){ //rightMin = node.right
        Node<E> left = node.left;
        node = node.right;
        node.left = left;
    }else{
        Node<E> right = node.right;
        Node<E> left = node.left;
        node = removeMin(node.right);
        node.right = right;
        node.left = left;
    }
    return node;
}

private Node<E> removeMin(Node<E> node){ 
    if(node.left != null && node.left.left == null){
        Node<E> min = node.left;
        node.left = min.right;
        return min;
    }
    return removeMin(node.left);
}

2.4. 迭代

简单的可以利用递归将树转化为列表，然后将迭代实现委托给列表

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/structure/tree/BinaryTreeSet.java

public Iterator<E> iterator() {
    return toList().iterator();
}

public List<E> toList() {
    List<E> list = new ArrayList<>(size);
    link(getRoot(), list);
    return list;
}

private void link(Node<E> node, List<E> list){
    if(isEmptyNode(node)){
        return;
    }
    link(node.left, list);
    list.add(node.element);
    link(node.right, list);
}

上面的迭代虽然可以实现，但如果每次迭代前都要先将整棵树递归一遍显然难以接受，所以希望能够直接基于树进行迭代。而要基于树迭代势必要向上查找，因此需要在节点中记住parent节点，这个可以借鉴jdk中TreeMap的实现。

• 向后迭代

java.util.TreeMap

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) { //若存在右子树，则next必然是右子树最小即最左节点
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else { 
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) { //如果ch=p.right，则p必然已经遍历过，那么向上回溯，直至ch=p.left
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

• 向前迭代

java.util.TreeMap

static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.left != null) { //同样若存在左子树，则prev必然是左子树最大即最右节点
        Entry<K,V> p = t.left;
        while (p.right != null)
            p = p.right;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.left) { //如果ch=p.left，则p必然已经遍历过，那么向上回溯，直至ch=p.right
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

2.4. 打印

为了方便画出树状图，可以打印每层的具体节点，后面讨论avl树和红黑树时都可以这样搞

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/structure/tree/BinaryTreeSet.java

public void print() {
    Map<Integer, List<Node<E>>> map = new LinkedHashMap<>();
    build(getRoot(), map, 0);
    for(List<Node<E>> list : map.values()){
        System.out.println(list); 
    }
}

private void build(Node<E> node, Map<Integer, List<Node<E>>> map, int ht){
    if(isEmptyNode(node)){
        return;
    }

    List<Node<E>> list = map.get(ht);
    if(list == null){
        list = new ArrayList<>();
        map.put(ht, list);
    }
    list.add(node);
    build(node.left, map, ht + 1);
    build(node.right, map, ht + 1);
}

3. MultiTreeMap

前面讨论线性数据结构时提过，在链表上实现二分法得不偿失，而二叉树很自然地解决了这个问题，但是二叉树不好处理重复元素，因此有一个想法：即在二叉树的结构上再维护一个链表。其实这种想法已经在很多地方都有体现，比如在后面要讨论的B树与B+树，以及LinkedHashMap与HashMap的实现。

这里可以先定义一个接口，先初步用二叉树实现一下，后面讨论红黑树时再进行实现，那么就相当于一个允许重复元素的TreeMap，并且可以更容易地实现迭代或者范围查询。

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/structure/tree/MultiTreeMap.java

public interface MultiTreeMap<K, V> extends Map<K, V>, Iterable<Entry<K, V>>{

    List<V> getList(Object key);

    List<V> removeList(Object key);
    
    Set<K> keySet(boolean reverse);
    
    Set<K> keySet(K from, boolean fromInclusive, K to, boolean toInclusive, boolean reverse);
    
    Collection<V> values(boolean reverse);
    
    Collection<V> values(K from, boolean fromInclusive, K to, boolean toInclusive, boolean reverse);
    
    Set<Entry<K, V>> entrySet(boolean reverse);
    
    Set<Entry<K, V>> entrySet(K from, boolean fromInclusive, K to, boolean toInclusive, boolean reverse);

    void printTree();
}

实现思路：

对于查找，直接在树中进行，如果是范围迭代，首先在树中确定首尾节点，然后通过链表进行遍历。

对于插入，首先在树中查找node，如果树中已存在，则直接在链表中链接为node.next；否则如果在树中插入为node.left，则在链表中链接为node.prev；如果在树中插入为node.right，则在链表中链接为最后一个重复node的next。

对于删除，首先在树中查找node，如果没有则直接返回；如果存在且链表中有重复的，则用node.next的值替换node的值，然后删除node.next；否则分别从树和链表中删除node。

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/structure/tree/BinaryTreeMultiMap.java

public class BinaryTreeMultiMap<K extends Comparable<? super K>, V> implements MultiTreeMap<K, V> {

    protected Node<K, V> header;

    protected Node<K, V> nil;

    protected int size;

    protected final boolean deduplication;

    protected final boolean asc;

    public BinaryTreeMultiMap(){
        this(true, true);
    }

    public BinaryTreeMultiMap(boolean deduplication, boolean asc){
        this.deduplication = deduplication;
        this.asc = asc;
        init();
    }

    protected void init(){
        nil = new Node<K, V>(null, null, false, null, null);
        nil.left = nil;
        nil.right = nil;
        header = new Node<K, V>(null, null, false, nil, nil);
        header.next = nil;
        nil.prev = header;
    }

    // ... ...

    @Override
    public V put(K key, V value) { 
        if(isEmpty()){
            Node<K, V> node = new Node<>(key, value, false, nil, nil);
            header.right = node;
            node.parent = header;
            linkIn(node, header, true);
            return null;
        }else{
            return put(key, value, header.right);
        }
    }

    private V put(K key, V value, Node<K, V> node){
        int cmp = key.compareTo(node.getKey());
        if(cmp < 0){
            if(node.left != nil){
                return put(key, value, node.left);
            }else{
                Node<K, V> created = new Node<>(key, value, false, nil, nil);
                node.left = created;
                created.parent = node;
                linkIn(created, node, false);
                return null;
            }
        }else if(cmp > 0){ 
            if(node.right != nil){
                return put(key, value, node.right);
            }else{
                Node<K, V> created = new Node<>(key, value, false, nil, nil);
                node.right = created;
                created.parent = node;
                //node在链表中可能存在等值的节点
                while((node = node.next).isRepeat); 
                linkIn(created, node, false);
                return null;
            }
        }else if(deduplication){ //覆盖
            V old = node.value;
            node.key = key;
            node.value = value;
            return old;
        }else{ //插入链表, Tree保持不变
            while((node = node.next).isRepeat); 
            V old = node.prev.value;
            linkIn(new Node<>(key, value, true, nil, nil), node, false);
            return old;
        }
    }

    protected void linkIn(Node<K, V> newNode, Node<K, V> node, boolean linkNext){
        if(linkNext){
            newNode.prev = node;
            newNode.next = node.next;
            node.next.prev = newNode;
            node.next = newNode;
        }else{
            newNode.next = node;
            newNode.prev = node.prev;
            node.prev.next = newNode;
            node.prev = newNode;
        }
        size++;
    }

    protected void linkOut(Node<K, V> node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }

    @Override
    public V remove(Object key) {
        Node<K, V> node = get(key, header.right);
        if(node == nil){
            return null;
        }

        V value = node.value;
        Node<K, V> next = node.next;
        if(next.isRepeat){ 
            linkOut(next); 
            node.key = next.key;
            node.value = next.value;
        }else{
            linkOut(node); 
            remove(node);
        }
        return value;
    }

    protected void remove(Node<K, V> node){
        Node<K, V> left = node.left;
        Node<K, V> right = node.right;
        Node<K, V> parent = node.parent;
        if(left == nil){
            replaceChild(parent, node, right);
        }else if(right == nil){
            replaceChild(parent, node, left);
        }else{
            Node<K, V> removed = removeLeftMax(node);
            replaceChild(parent, node, removed);
            removed.right = node.right;
            removed.right.parent = removed;
            if(removed != node.left){
                removed.left = node.left;
                removed.left.parent = removed;
            }
        }
    }

    protected void replaceChild(Node<K, V> parent, Node<K, V> oldChild, Node<K, V> newChild){
        newChild.parent = parent;
        if(parent.right == oldChild){
            parent.right = newChild;
        }else{
            parent.left = newChild;
        }
    }

    //removeRightMin(BinaryNode<K, V> node)
    private Node<K, V> removeLeftMax(Node<K, V> node){
        Node<K, V> left = node.left;
        if(left.right == nil){
            node.left = left.left;
            left.left.parent = node;
            return left;
        }

        Node<K, V> right = left.right;
        while(right.right != nil){
            left = right;
            right = right.right;
        }
        left.right = right.left;
        right.left.parent = left;
        return right;
    }

    private Node<K, V> getHigher(K key, Node<K, V> node, Node<K, V> higher, boolean includeSelf){
        int cmp = node.getKey().compareTo(key);
        if(cmp == 0){
            if(includeSelf){
                return node;
            }
            Node<K, V> right = node.right; 
            if(right == nil){
                return higher;
            }
            int cmpRight = right.getKey().compareTo(key);
            if(cmpRight > 0){
                if(right.left == nil){ //right已经是边界， 找不到更接近的
                    return right;
                }
                return getHigher(key, right.left, right, includeSelf);
            }else{ //=0
                if(right.right == nil){
                    return higher; 
                }
                return getHigher(key, right.right, higher, includeSelf);
            }
        }else if(cmp < 0){// right 
            Node<K, V> right = node.right;
            if(right == nil){
                return higher;
            }
            int cmpRight = right.getKey().compareTo(key);
            if(cmpRight == 0){
                if(includeSelf){ 
                    return right;
                }
                if(right.right == nil){
                    return higher; 
                }
                return getHigher(key, right.right, higher, includeSelf);
            }else if(cmpRight < 0){
                if(right.right == nil){
                    return higher; 
                }
                return getHigher(key, right.right, higher, includeSelf);
            }else{ // >0
                if(right.left == nil){ //right已经是边界， 找不到更接近的
                    return right;
                }
                return getHigher(key, right.left, right, includeSelf);
            }
        }else{ // left 
            Node<K, V> left = node.left;
            if(left == nil){
                return node;
            }
            int cmpLeft = left.getKey().compareTo(key);
            if(cmpLeft == 0){
                if(includeSelf){ 
                    return left;
                }
                if(left.right == nil){
                    return node; 
                }
                return getHigher(key, left.right, node, includeSelf);
            }else if(cmpLeft < 0){
                if(left.right == nil){
                    return node; 
                }
                return getHigher(key, left.right, node, includeSelf);
            }else{
                if(left.left == nil){
                    return left;
                }
                return getHigher(key, left.left, left, includeSelf);
            }
        }
    }

    @SuppressWarnings({ "rawtypes" })
    private ListIterator getIterator(K from, boolean fromInclusive, K to, boolean toInclusive, int type, boolean reverse){
        Node<K, V> head = header;
        Node<K, V> tail = nil;
        if(from != null){
            head = getHigher(from, header.right, nil, fromInclusive);
            if(head == nil){
                return createIterator(nil.prev, header.next, type, reverse);
            }
            if(to == null || to.compareTo(from) < 0){
                return createIterator(head.prev, nil, type, reverse);
            }

            tail = getHigher(to, header.right, nil, toInclusive);
            if(tail == nil){
                return createIterator(head.prev, nil, type, reverse);
            }else if(toInclusive){
                if(to.compareTo(tail.getKey()) == 0){
                    //找到的是第一个max, 定位到最后一个max的next
                    while((tail = tail.next).isRepeat);
                }
                return createIterator(head.prev, tail, type, reverse);
            }else{
                tail = tail.prev;
                if(tail == header){
                    return createIterator(head.prev, tail.next, type, reverse);
                }
                //找到的是最后一个max的next, 定位到第一个max
                if(to.compareTo(tail.getKey()) == 0){
                    if(tail.isRepeat){
                        while((tail = tail.prev).isRepeat);
                    }
                    return createIterator(head.prev, tail, type, reverse);
                }
                return createIterator(head.prev, tail.next, type, reverse); //tail < max
            }
        }else if(to != null){
            tail = getHigher(to, header.right, nil, toInclusive);
            if(tail == nil){
                if(toInclusive){
                    //includeMax=true -> tail.prev < max
                    return createIterator(header, nil, type, reverse);
                }else{
                    tail = tail.prev;
                    if(tail == header){
                        return createIterator(header, tail.next, type, reverse);
                    }
                    //找到的是最后一个max的next, 定位到第一个max
                    if(to.compareTo(tail.getKey()) == 0){
                        if(tail.isRepeat){
                            while((tail = tail.prev).isRepeat);
                        }
                        return createIterator(header, tail, type, reverse);
                    }
                    return createIterator(header, tail.next, type, reverse); //tail < max
                }
            }else{
                if(toInclusive){
                    //找到的是第一个max, 定位到最后一个max的next
                    if(to.compareTo(tail.getKey()) == 0){
                        while((tail = tail.next).isRepeat);
                    }
                    return createIterator(header, tail, type, reverse);
                }else{
                    tail = tail.prev;
                    if(tail == header){
                        return createIterator(header, tail.next, type, reverse);
                    }
                    //找到的是最后一个max的next, 定位到第一个max
                    if(to.compareTo(tail.getKey()) == 0){
                        if(tail.isRepeat){
                            while((tail = tail.prev).isRepeat);
                        }
                        return createIterator(header, tail, type, reverse);
                    }
                    return createIterator(header, tail.next, type, reverse); //tail < max
                }
            }
        }else{
            throw new IllegalArgumentException();
        }
    }

    @SuppressWarnings("rawtypes")
    private ListIterator createIterator(Node<K, V> prev, Node<K, V> next, int type, boolean reverse){
        if(type == 1){
            return new NodeIterator(prev, next, reverse);
        }else if(type == 2){
            return new KeyIterator(prev, next, reverse);
        }else{
            return new valueIterator(prev, next, reverse);
        }
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return entrySet(false);
    }
    
    @Override
    public Set<Entry<K, V>> entrySet(boolean reverse) {
        return new EntrySet(new NodeIterator(header, nil, reverse));
    }

    @SuppressWarnings("unchecked") 
    @Override
    public Set<Entry<K, V>> entrySet(K from, boolean fromInclusive, K to, boolean toInclusive, boolean reverse) {
        return new EntrySet(getIterator(from, fromInclusive, to, toInclusive, 1, reverse));
    }
    
    // ... ...

    private class NodeIterator extends AbstractIterator<Entry<K, V>>{

        public NodeIterator(Node<K, V> head, Node<K, V> tail, boolean reverse) {
            super(head, tail, reverse);
        }

        @Override
        protected boolean hasHead() {
            if(current == null){
                current = head;
            }
            return current.next != tail;
        }

        @Override
        protected boolean hasTail() {
            if(current == null){
                current = tail;
            }
            return current.prev != head;
        }

        @SuppressWarnings("unchecked")
        @Override
        public Entry<K, V> next() {
            if(initSize != size){
                throw new ConcurrentModificationException();
            }
            if(reverse != asc){
                return current = current.next;
            }else{
                return current = current.prev;
            }
        }

        @SuppressWarnings("unchecked")
        @Override
        public Entry<K, V> previous() {
            if(initSize != size){
                throw new ConcurrentModificationException();
            }
            if(reverse != asc){
                return current = current.prev;
            }else{
                return current = current.next;
            }
        }

        @SuppressWarnings("unchecked")
        @Override
        public void remove() {
            if(current == null || current == head || current == tail){
                return;
            }
            linkOut(current);
            if(!current.isRepeat){
                BinaryTreeMultiMap.this.remove(current);
            }
            initSize = size;
        }
    }

    private abstract class AbstractIterator<E> implements ListIterator<E> {

        //这里简单处理下, 用size代替modCount来判断迭代期间是否发生修改，检测不到ABA问题
        protected int initSize;

        protected boolean reverse;

        @SuppressWarnings("rawtypes")
        protected Node head;

        @SuppressWarnings("rawtypes")
        protected Node tail; 

        @SuppressWarnings("rawtypes")
        protected Node current;

        @SuppressWarnings("rawtypes")
        public AbstractIterator(Node head, Node tail, boolean reverse){
            this.initSize = size;
            this.head = head;
            this.tail = tail;
            this.reverse = reverse;
        }

        @Override
        public boolean hasNext() {
            if(reverse != asc){ //!reverse == asc
                return hasHead();
            }else{
                return hasTail();
            }
        }

        @Override
        public boolean hasPrevious() {
            if(reverse != asc){
                return hasTail();
            }else{
                return hasHead();
            }
        }

        protected abstract boolean hasHead();

        protected abstract boolean hasTail();

        @Override
        public int nextIndex() {
            // TODO Auto-generated method stub
            throw new UnsupportedOperationException();
        }

        @Override
        public int previousIndex() {
            // TODO Auto-generated method stub
            throw new UnsupportedOperationException();
        }

        @Override
        public void set(E e) {
            // TODO Auto-generated method stub
            throw new UnsupportedOperationException();
        }

        @Override
        public void add(E e) {
            // TODO Auto-generated method stub
            throw new UnsupportedOperationException();
        }
    }

    static class Node<K, V> implements Entry<K, V> {

        protected K key;

        protected V value;

        protected boolean isRepeat;

        protected Node<K, V> left;

        protected Node<K, V> right;

        protected Node<K, V> parent;

        protected Node<K, V> prev;

        protected Node<K, V> next;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
        }

        public Node(K key, V value, boolean isRepeat, Node<K, V> left, Node<K, V> right){
            this.key = key;
            this.value = value;
            this.isRepeat = isRepeat;
            this.left = left;
            this.right = right;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V value) {
            // TODO Auto-generated method stub
            throw new UnsupportedOperationException();
        }

        @Override
        public String toString() {
            return "{" + key + " , " + value + "}";
        }
    }
}

4. 二叉树的高度

记树的高度为 $H$，节点数为 $N$，那么最好的情况是满二叉树，这时有 $N = 1 + 2 + 2^2 +…+ 2^{H-1} = 2^H - 1$，即 $H = \log_{2} {(N+1)}$，而最差的情况则是退化成链表，即 $H = N$。后面要讨论的avl树和红黑树都是想办法在二叉树的基础上加一些约束规则，使其尽量接近满二叉树，以便降低数的高度。

另外，还可以简单推导一下，如果是满 $M$ 叉数（比如后面要讨论的B树以及B+树），那么每个节点最多有 $M$ 个子节点，每个子节点最多包含 $M-1$ 个元素，那么有：$N = (M-1)(1 + M + M^2 +…+ M^(H-1)) = M^H - 1$，即 $H = \log_{M} ({N+1})$

参考：

1. 《算法导论》
2. 《数据结构与算法分析》

数据结构 AVL树 数据结构 线性结构

算法设计